# All possible solutions to the Matrix Equation (free variables appearing)

I am attempting to solve a system of linear equations using LinearSolve[] . In my case, the number of unknowns are more than constraints. I learnt that LinearSolve does not give me all solutions. However, I am also unable to use Solve[] to get all possible solutions.

Here is my example:

InpMatrix={
{1,0,0,0,0,0,0,0,0,0,0,0},
{15,4,0,0,0,0,0,0,0,0,0,0},
{90,48,16,0,0,0,0,0,0,0,0,0},
{270,216,144,16,0,0,0,0,0,0,0,0},
{405,432,432,0,16,0,0,0,0,0,0,0},
{243,324,432,0,0,16,0,0,0,0,0,0},
{16,0,0,0,0,0,256,0,0,0,0,0},
{0,0,0,-16,-16,-16,47104,1024,0,0,0,0}
};

synd={{0},{0},{0},{0},{0},{0},{256},{1024}};

In[217]:= sol = LinearSolve[InpMatrix, synd]

Out[217]= {{0}, {0}, {0}, {0}, {0}, {0}, {1}, {-45}, {0}, {0}, {0}, {0}}


However, the solution I am looking for should be:

{{0}, {0}, {0}, {0}, {0}, {0}, {1}, {-45}, {0}, {30}, {15}, {0}}


Hence I tried to use Solve[] in the following way:

Solve[InpMatrix.var == synd, var]


But it gives me an error saying:

Solve::nsmet: This system cannot be solved with the methods available to Solve. >>

Solve[{
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{15, 4, 0, 0, 0, 0, 0, 0,  0, 0, 0, 0},
{90, 48, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{270, 216, 144, 16, 0, 0, 0, 0, 0, 0, 0, 0},
{405, 432, 432, 0, 16, 0, 0,  0, 0, 0, 0, 0},
{243, 324, 432, 0, 0, 16, 0, 0, 0, 0, 0, 0},
{16, 0, 0, 0, 0, 0, 256, 0, 0, 0, 0, 0},
{0, 0, 0, -16, -16, -16, 47104, 1024, 0, 0, 0, 0}
}.var == {{0}, {0}, {0}, {0}, {0}, {0}, {256}, {1024}}, var]


Could anyone kindly help me with correctly using Solve[] or any other functionality that yields all posible solutions ? Preferably I would general solution, a symbolic form with free variables.

-
The "solution you are looking for" clearly is not a solution: when you left-multiply it by InpMatrix, you do not obtain synd. Have you perhaps mixed up the roles of the solution and synd? –  whuber Mar 3 '13 at 18:57
@whuber Sorry, but it doesn't seem to me that {{0}, {0}, {0}, {0}, {0}, {0}, {1}, {-45}, {0}, {30}, {15}, {0}} isn't a solution. Try this if you wish: InpMatrix.{{0}, {0}, {0}, {0}, {0}, {0}, {1}, {-45}, {0}, {30}, {15}, {0}} == synd . It gives True . –  Pavithran Iyer Mar 3 '13 at 19:10
You're right; I tried exactly that but introduced a typo. I stand corrected. Have you looked into NullSpace? It can be used to produce all solutions to LinearSolve once you have a single one. E.g., test it with InpMatrix.({0, 0, 0, 0, 0, 0, 1, -45, 0, 0, 0, 0} + {x1, x2, x3, x4}.NullSpace[InpMatrix]) Notice that the output of NullSpace shows in this case that you can freely vary the last four coefficients. –  whuber Mar 3 '13 at 19:18
Check the documentation for Solve? It wants an explicit list of variables. Coding error here, so too localized seems reasonable. –  Daniel Lichtblau Mar 4 '13 at 3:54

By pen-and-paper, the solution, consisting of a column vector defined by $\{x_1, ... x_{12}\}$, has $x_9, x_{10}, x_{11}, x_{12}$ as free parameters, and the following equations: $$16 x_1 + 256 x_7 = 256$$ $$-16(x_4+x_5+x_6)+47104x_7 + 1024 x_8 = 1024$$ There are also 6 other equations (all of which have zero $x_7$ and $x_8$ terms), and all of those equations are homogenous. Thus, all values of $x_1, ... x_6$ are constrained to 0 and we are left with a system where there exists only one solution, the one that, MMA's LinearSolve provided, $x_7 = 1$ and $x_8 = -45$.

I naievly thought that MaxExtraConditions would give all the solutions in Solve, but it did not because the dot multiplication in MMA creates 8 equations, not 12, and Solve therefore ignores the last four.

Nonetheless, for the solution $x_s = x_p + x_n$, Solve still finds the particular solution for $A.x_p = b$.

Adding the parameterized NullSpace gives the full answer:

sol = First@
Block[{var = Array[x, Length@First@InpMatrix]},
Solve[InpMatrix.List /@
var == {{0}, {0}, {0}, {0}, {0}, {0}, {256}, {1024}}, var,
MaxExtraConditions -> All]];
full = Array[x, Length[First@InpMatrix]] /. sol
(* {0, 0, 0, 0, 0, 0, 1, -45, x[9], x[10], x[11], x[12]} *)


And your four free parameters are $x_9, ... x_{12}$.

In fact, by using the form Array[x, Length[First@InpMatrix]] /. sol, all fixed parameters are given their appropriate values and all free parameters (which either show up and are replaced appropriately by the rules from Solve or stay in their x[_] form are likewise given. Thus, full represents the complete ($x_p + x_n$) solution.

-
Your application of Solve gives a set of solutions with four free parameters, x[9], x[10], x[11], and x[12]. That's the complete set of all solutions. –  whuber Mar 3 '13 at 23:12
Oh. My mistake. I see what my issue is. The rank is 8, and there in fact only is four free parameters. –  VF1 Mar 3 '13 at 23:17

The documentation page explicitely says :

For underdetermined systems,  LinearSolve will return one of the possible solutions;
Solve will return a general solution.


So in our case LinearSolve yields only one solution, even though there are infinitely many of them.

With Solve thre are two issues :

• Solve interprets var as a number, not just a vector, that's why you couldn't get the correct solution.
• working with Solve we encounter the full dimensional component problem (related issues you could find here : What is the difference between Reduce and Solve ?) because of the null space (see NullSpace) of InpMatrix is a linear (vector) 4-dimensional subspace of the domain vector space.

Concerning the first issue we can see e.g. adding this option MaxExtraConditions -> All :

Solve[ InpMatrix.var == synd, var, MaxExtraConditions -> All]

{}


compare it with e.g. the output of

Solve[ InpMatrix.var == synd, var]


To resolve the problem one should set e.g. :

var = {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12};


We get the warning exactly because of the full component problem, even with MaxExtraConditions -> All :

var /. Solve[ InpMatrix.var == synd, var, MaxExtraConditions -> All]

Solve::svars: Equations may not give solutions for all "solve" variables. >>

{{0, 0, 0, 0, 0, 0, 1, -45, a9, a10, a11, a12}}


So this vector { 0, 0, 0, 0, 0, 0, 1, -45, 0, 30, 15, 0} certainly belongs to the formal space expressed with this solution {{0, 0, 0, 0, 0, 0, 1, -45, a9, a10, a11, a12}} even though it is a full-dimensional (4-dimentional affine subspace), not just some exceptional points (12-dimensional vectors) in it. The reason of the warning is that replacement rules basically cannot represent full-dimensional components, and this is the case here. It is perfectly appropriate in general even though it is not harmful here. To emphasize the issue see :

Solve[ Floor[x] == 2, x, Reals]

Solve::fulldim: The solution set contains a full-dimensional component;
use Reduce for complete solution information. >>

{{}}


of course this works well :

Reduce[ Floor[x] == 2, x, Reals]

2 <= x < 3


The warning above suggest to use Reduce because boolean formulae are capable to express full-dimensional componets, so here is also another possibility, ensuring there is only one solution (expressing infinitely many ones since a9, a10, a11, a12 need not be specified) :

Reduce[ InpMatrix.var == synd, var]

a1 == 0 && a2 == 0 && a3 == 0 && a4 == 0 && a5 == 0 && a6 == 0 && a7 == 1 && a8 == -45


Moreover you might find useful NullSpace :

NullSpace[InpMatrix]

 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}}


This means that every vector of the form { 0, 0, 0, 0, 0, 0, 0, 0, a, b, c, d} yields 0 (in the eight-dimensional target vector space) if one acts on it with InpMatrix, i.e.

InpMatrix.{0, 0, 0, 0, 0, 0, 0, 0, a, b, c, d}

{0, 0, 0, 0, 0, 0, 0, 0}

-
Sorry, I am more confused. How come Solve[] is saying there are no solutions ? Clearly by inspection we can see that there is atleast one solution. Isn't it so? Please correct me if I am wrong. –  Pavithran Iyer Mar 3 '13 at 18:54
@Artes but the vector {0,0,0,0,0,0,1,-45,0,0,0,0} does give synd... That is, synd is not in the null space of InpMatrix. –  VF1 Mar 3 '13 at 18:58
@Artes,VF1 Yes, and so is this too a solution: {{0}, {0}, {0}, {0}, {0}, {0}, {1}, {-45}, {0}, {30}, {15}, {0}} . Sure I agree with you that there are no solutions of the type {0, 0, 0, 0, 0, 0, 0, 0, a, b, c, d} . My problem is to find all possible solutions, not necessarily of the particular type which you had mentioned. I am not sure how useful it would be to find the NullSpace[] of InpMatrix because the vector on the Right Side of the Matrix Equation is not a zero vector. –  Pavithran Iyer Mar 3 '13 at 19:00
@VF1 Thanks for the feedback, I've just corrected it. –  Artes Mar 3 '13 at 19:28
Pavithran, the null space is critical to finding all solutions, because every solution can be obtained as any particular solution (where the RHS is not necessary zero) plus some element of the null space. If this is not perfectly clear, please consult any textbook on linear algebra. –  whuber Mar 3 '13 at 22:46