# How can I find whether a given algebraic expresion T can be obtained as linear combination from a set S (with number coeficients)

We might take:

s = {(x-y)^2, x*y+z};
e = (x+y)^2 + 4*z;


and linearDecompose[e,s] could give {1,4} for example.

I know Solve with universal quantifiers over all free variables would do it:

Solve[ForAll[{x,y,z},s.{q1,q2} == e], {q1,q2}]


But is this the "right" way to do it? Does it get inefficient in time and memory as the number of variables increases?

Is there a more specialized function for this purpose or will Solve work with high efficiency?

• In[19]:= SolveAlways[e == {c1, c2}.s, {x, y}] Out[19]= {{c1 -> 1, c2 -> 4}} So that's one way. Now SolveAlways is a bit dated and not the most efficient function in general, but it should do quite well when the underlying problem is linear, as this is. – Daniel Lichtblau May 9 at 15:18

s = {(x - y)^2, x*y + z};
e = (x + y)^2 + 4*z;


You can also use PolynomialReduce:

{q, r} = PolynomialReduce[e, s, {x, y, z}]

 {{1, 4}, 0}

e == q.s + r // Expand

 True

ClearAll[linDecomp]
linDecomp = If[VectorQ[#, NumericQ] && #2 === 0, #, {}] & @@
PolynomialReduce[##, Variables@#] &;

linDecomp[e, s]

 {1, 4}

linDecomp[e, s + (x + y)^3]

 {}

• This is good but...in a "bad" case, one might add e.g. (x+y)^3 to both polynomials in s. That would make for trouble. – Daniel Lichtblau May 9 at 15:20
• why would that be? – user3257842 May 9 at 17:51
• It would fail to give the desired result because no division would take place. – Daniel Lichtblau May 9 at 21:48