# Reduce set of symbolic equations to linearly independent subset

Given a set of symbolic equations $f_i(x_1,x_2,...,x_n)=0$ in several variables, for example

f1=x+y-z;
f2=x-y+z;
f3=3x-y+z;


I would like to apply a function LinIndep[{f1,f2,f3}] such that the output reduces the system to only a set of linearly independent functions. So, for the above the output might be:

LinIndep[{f1,f2,f3}]


{x+y-z,x-y+z}

It is OK if the function finds a different set of linearly independent functions. The point is to reduce the number of equations. I know that GroebnerBasis does this. However, a Groebner basis calculation does more than I need to do here and becomes really slow for bigger equations with symbolic coefficients. All I want is literally check for linear dependence and truncate the set accordingly. Is there a way to do this efficiently?

• If all your equations are linear, you can construct the coefficient matrix and use RowReduce. But you say you may have symbolic coefficients: in this case the linear dependencies are not given. For instance, {f1, f2} = {x + y, x + a*y} are dependent if a == 1 and independent otherwise. – Marius Ladegård Meyer Oct 6 '15 at 19:48
• The symbolic coefficients are expected to be such that linear dependence, if present, would be valid for all possible parameter values. – Kagaratsch Oct 6 '15 at 19:53
• In:= DeleteCases[ RowReduce[ CoefficientArrays[{f1, f2, f3}, {x, y, z}][]], {0 ..}].{x, y, z} Out= {x, y - z} – Daniel Lichtblau Oct 6 '15 at 20:05
• @DanielLichtblau wow, this works great! I wonder, what is this double point notation you used in there {0 ..}? – Kagaratsch Oct 6 '15 at 22:07
• It just means Repeated. Used in Mathematica pattern matching. You can see this by checking the full form: FullForm[0 ..]. – Daniel Lichtblau Oct 6 '15 at 23:12

You could try the following, although I have tested it only with your example, so it would be interesting to explore its robustness further.

Clear[linIndep]
linIndep[list_List] :=
Module[
{coeffarray, reduced},
coeffarray = CoefficientArrays[list, Variables[list]][];
reduced = LatticeReduce[coeffarray];
reduced.Variables[list]
]

list = {x + y - z, x - y + z, 3 x - y + z};
linIndep[list]

(* Out: {x + y - z, -x + y - z} *)