# Finding maximal subset of linearly independent functions

I've got a set of functions in one variable. I wish to find the basis of the corresponding spanning set

Example: $$\left\{1,\frac{1}{1-\sqrt{x}},\frac{1}{1-x},\frac{\sqrt{x}}{1-x}\right\}$$ may reduce to $$\left\{1,\frac{1}{1-\sqrt{x}},\frac{1}{1-x}\right\}.$$

Sure, I can sample the functions over some set of points $x_i$ and reduce the problem to same problem with vectors, but I have a big set (19 functions) and exact basis computation using QRDecomposition takes long and inexact is not very robust.

• Spanning over what base field? – Daniel Lichtblau May 9 '15 at 20:59
• Over reals. Or i don't understand the question – uranix May 9 '15 at 21:11
• I was wondering because it is not obvious to me how to write sqrt(x)/(1-x) as a linear combination of the other three. – Daniel Lichtblau May 9 '15 at 21:19
• Ah, sorry. Here it is $$\frac{\sqrt{x}}{1-x} = \frac{1 + \sqrt{x}}{1 - x} - \frac{1}{1 - x} = \frac{1}{1 - \sqrt{x}}- \frac{1}{1 - x}$$ – uranix May 9 '15 at 21:22

Here is an approach that might work out. Use GroebnerBasis to set up all polynomial relations, then reduce to see where there may be linear dependencies. We use surrogate variables to define algebraic relations for roots and reciprocals, so sx stands in for sqrt(x) below, and similar for the reciprocal variables xr1 and sxr2. We also use new variables to denote the basis elements, and give their defining polynomials in terms of the prior variables.

polys = {sx^2 - x, xr1*(1 - x) - 1, sxr2*(1 - sx) - 1, b1 - 1,
b2 - sxr2, b3 - xr1, b4 - sx*xr1};
gb = GroebnerBasis[polys, {sxr2, xr1, sx, x, b1, b2, b3, b4}]

(* Out[3]= {-b3 + b3^2 - b4^2,
b2 - b3 - b4, -1 + b1, -1 + b3 - b4^2 + b4^2 x,
1 - b3 + b3 x, -b4 + sx + b4 x, -b3 + xr1, -b3 - b4 + sxr2} *)


Now we reduce all the basis variables.

PolynomialReduce[{b1, b2, b3, b4},
gb, {sxr2, xr1, sx, x, b1, b2, b3, b4}][[All, 2]]

(* Out[4]= {1, b3 + b4, b3, b4} *)


So b2 is written as a linear combination of b3 and b4.

To use this approach in general you might need to have a term ordering that minimizes degree at least for the basis variables. Else you could get nonlinear algebraic relations that might, in a different term ordering, become linear. At least I think that could happen.

• Interesting, but might be very slow for set of ~20 functions. For now I'm just using QR decomposition with 1000 digits on a set of ~100 points. That is pretty quick and seems to work ok. – uranix May 9 '15 at 22:20
• Good method. You might instead consider NullSpace (use a few more points than functions, maybe 5-10 or so). Can do with exact or approximate arithmetic. Also you can row reduce the result to canonicalize the relations. – Daniel Lichtblau May 11 '15 at 14:45