5
$\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?

Improve this question
$\endgroup$
5
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 23:12

1 Answer 1

Reset to default
4
$\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} *)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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