When doesn't this algorithm for solving for multiple variables using only $3$ linear equations work?

Question

Say we've got the following $3$ linear equations: $$2a+3b+5c+7d+11e=106$$ $$13a+17b+19c+23d+29e=341$$ $$31a+37b+41c+43d+47e=635$$ Now, we've got three definitions of $a$: $$a=\dfrac{3b+5c+7d+11e-106}{2}=\dfrac{17b+19c+23d+29e-341}{13}=\dfrac{37b+41c+43d+47e-635}{31}$$ We can now combine these in $3$ different ways: $$\dfrac{3b+5c+7d+11e-106}{2}=\dfrac{17b+19c+23d+29e-341}{13}$$ $$\dfrac{17b+19c+23d+29e-341}{13}=\dfrac{37b+41c+43d+47e-635}{31}$$ $$\dfrac{3b+5c+7d+11e-106}{2}=\dfrac{37b+41c+43d+47e-635}{31}$$ Which turns into: $$5b+27c+45d+85e=696$$ $$46b+56c+154d+288e=2316$$ $$19b+73c+131d+247e=2016$$ And... the $a$ has disappeared. We can keep on going, until we can determine the value of $e$, after which we can work our way up. The solution will be: $$a=1,b=2,c=3,d=4,e=5$$ In many cases this algorithm works, I've even written a Python program for it. But in some cases it doesn't. A result will come up that doesn't satisfy all equations (I've also verified a few of those by hand, so it's not the program)

Questions:

1) Why do I get incorrect results?

2) Is there an easy way to see whether a system will give me incorrect results?

3) Clearly, if I only have $3$ equations, but more than $3$ variable, there is an infinite amount of solutions I miss. At what step do I 'lose' information?

Answer 1

When you have a linear system with $m$ equations and $n$ unknowns, and $m<n$, then it means - in general - that you can solve it for $m$ of the unknowns as a function of the remaining ones, which therefore assume the role of parameters. That is you end up in solving the $m \times m$ system: $$ \left( {\begin{array}{*{20}c} {c_{\,1,1} } & {c_{\,1,2} } & \cdots & {c_{\,1,m} } \\ {c_{\,2,1} } & {c_{\,2,2} } & \cdots & {c_{\,2,m} } \\ \vdots & \vdots & \ddots & \vdots \\ {c_{\,m,1} } & {c_{\,m,2} } & \cdots & {c_{\,m,m} } \\ \end{array}} \right)\left( {\begin{array}{*{20}c} {x_{\,1} } \\ {x_{\,2} } \\ \vdots \\ {x_{\,m} } \\ \end{array}} \right) = \left( {\begin{array}{*{20}c} {a_{\,1} - c_{\,1,m + 1} x_{\,m + 1} - \; \cdots \; - c_{\,1,n} x_{\,n} } \\ {a_{\,2} - c_{\,2,m + 1} x_{\,m + 1} - \; \cdots \; - c_{\,2,n} x_{\,n} } \\ \vdots \\ {a_{\,m} - c_{\,m,m + 1} x_{\,m + 1} - \; \cdots \; - c_{\,m,n} x_{\,n} } \\ \end{array}} \right) $$ (Alternatively, you may think to complete the equations by adding $x_{m+1}=x_{m+1}, \cdots \;,x_n=x_n$).

Now, this system to be solvable is subject to the same conditions as for any square system. In particular, if the LHS matrix $\mathbf C$ does not have full rank, then it might have or not solutions depending on the rank of the complete Matrix.
That also means that not for whichever choice of the $m$ variables (and thus of $n-m$ parameters ) you might have solutions.
If you can choose the $m$ variables so that the corresponding matrix $C$ has full rank, then you can solve for those variables with the remaining as parameters.

That premised, for the example you give, the matrix looks to have full rank for any choice of the variables so that there is no problem in solving it as said above.

Concerning the operations you did, in principle those are ok, as they just correspond to row reduction.
However there are two irregular passages:

• when you deduce $a$, there is a sign typo, as you actually are deducing $-a$ (although that does not affect the following comparisons).
• when doing row-reduction, i.e. replacing a row by a suitable linear combination with other rows , you cannot do that for all the rows (otherwise for sure you'll make variables disappear!).

Answer 2

This won't work when a couple of equations directly contradict each other. For example, $a+b = 4$ and $2a+2b = 9$. (Note the LHS of the second one is double that of the first one, but RHS is not...)

UPDATE

Linear systems fall into 3 classes:

1. with a unique solution;
2. with infinitely many solutions;
3. With no solutions.

If your system is of the 3rd kind, your algorithm won't find any; this happens when the equations contradict each other.

Otherwise, there is a solution to the system. Your method will find some solution, but not necessarily characterize all solutions when they exist. In this sense, Gaussian Elimination is much preferable...