4
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Marius Ladegård Meyer Oct 6 '15 at 19:48
  • $\begingroup$ The symbolic coefficients are expected to be such that linear dependence, if present, would be valid for all possible parameter values. $\endgroup$ – Kagaratsch Oct 6 '15 at 19:53
  • 2
    $\begingroup$ In[955]:= DeleteCases[ RowReduce[ CoefficientArrays[{f1, f2, f3}, {x, y, z}][[2]]], {0 ..}].{x, y, z} Out[955]= {x, y - z} $\endgroup$ – Daniel Lichtblau Oct 6 '15 at 20:05
  • $\begingroup$ @DanielLichtblau wow, this works great! I wonder, what is this double point notation you used in there {0 ..}? $\endgroup$ – Kagaratsch Oct 6 '15 at 22:07
  • 1
    $\begingroup$ It just means Repeated. Used in Mathematica pattern matching. You can see this by checking the full form: FullForm[0 ..]. $\endgroup$ – Daniel Lichtblau Oct 6 '15 at 23:12
3
$\begingroup$

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]][[2]];
    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} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.