3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Technically speaking, you must have $n$ equations to solve for $n$ different variables... $\endgroup$ – Simply Beautiful Art Nov 8 '16 at 15:40
  • $\begingroup$ @SimpleArt I know, but this method also works sometimes. I'm asking when it won't. $\endgroup$ – Mastrem Nov 8 '16 at 15:41
  • $\begingroup$ I should think this will work when your original system is not inconsistent, in which case you have found a solution (from the 2 dimensional subspace of solutions). If your system is inconsistent then you will have no solution. Consistency can be checked using row reduction. $\endgroup$ – Paul Nov 8 '16 at 15:46
  • $\begingroup$ My guess is that if the system of equation has at least one solution, this algorithm produces a solution. However, there are systems that don't have a solution. $\endgroup$ – Omnomnomnom Nov 8 '16 at 15:46
3
$\begingroup$

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!).
$\endgroup$
2
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ More generally, it seems that what matters is whether the original system is consistent $\endgroup$ – Omnomnomnom Nov 8 '16 at 15:48
  • $\begingroup$ Okay, I understand that. but apart from these cases, does a consistent system imply a correct solution? $\endgroup$ – Mastrem Nov 8 '16 at 15:48
  • $\begingroup$ @Mastrem see update $\endgroup$ – gt6989b Nov 8 '16 at 15:52
  • $\begingroup$ So If there is a solution, I'll get one. That's nice to know. thank you. I added an extra question to my post; do you know at what step I lose information? $\endgroup$ – Mastrem Nov 8 '16 at 15:55
  • $\begingroup$ If you start with b instead of a I should think you would get a different solution. Then there is starting with c, d, e or a+b and so on at first or subsequent steps. So your first step 'a = ' is dictating the form of the final solution. $\endgroup$ – Paul Nov 9 '16 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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