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

Question

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.

Answer 1

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.

Answer 2

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}