23
$\begingroup$

I am currently learning matlab and linear algebra side by side and I stumbled upon this example from mathworks

A = [1 2 0; 0 4 3];
b = [8; 18];
x = A\b

x = 3×1

     0
4.0000
0.6667

which in my mind translates to

$$ A = \left[ \begin{matrix} 1 & 2 & 0 \\ 0 & 4 & 3 \end{matrix}\right] B = \left[ \begin{matrix} 8 \\ 18 \end{matrix}\right] x = \left[ \begin{matrix} a \\ b \\ c \end{matrix}\right] $$

$$ Ax = \left[ \begin{matrix} 1 & 2 & 0 \\ 0 & 4 & 3 \end{matrix}\right] \times \left[ \begin{matrix} a \\ b \\ c \end{matrix}\right] = \left[ \begin{matrix} a + 2b \\ 4b + 3c \end{matrix}\right] $$

which boils down to $$ \left[ \begin{matrix} a + 2b \\ 4b + 3c \end{matrix}\right] = \left[ \begin{matrix} 8\\ 18 \end{matrix}\right] \Rightarrow \begin{matrix}a + 2b = 8 \\4b + 3c = 18\end{matrix} $$

which is an equation with 3 unknown (a, b and c) with two equations, which is impossible! Yes there is a solution $$ x = \left[ \begin{matrix} 0 \\ 4 \\ 2/3 \end{matrix}\right] $$

How can I solve an impossible equation (three unknown and two equations) using linear algebra?

$\endgroup$
12
  • 91
    $\begingroup$ It is not impossible to solve this equation system , the solution is just not unique. $\endgroup$
    – Peter
    Nov 25, 2019 at 13:34
  • 53
    $\begingroup$ This is just one of many solutions. $\endgroup$
    – Hagen von Eitzen
    Nov 25, 2019 at 13:34
  • 9
    $\begingroup$ Relevant info (for those who don't look at the page you linked to): this example appears under the heading Least-Squares Solution of Underdetermined System. $\endgroup$
    – Hans Lundmark
    Nov 25, 2019 at 14:45
  • 3
    $\begingroup$ By the way, Octave gives a different answer [0.91803, 3.54098, 1.27869], which is the solution of minimal norm, and agrees with the formula given in this answer. Does anyone know why Matlab picks the particular solution [0,4,2/3] instead?!? $\endgroup$
    – Hans Lundmark
    Nov 25, 2019 at 14:56
  • 6
    $\begingroup$ Matlab tries to make the maximum number of elements zero. $\endgroup$
    – Austin
    Nov 26, 2019 at 6:45

5 Answers 5

Reset to default
125
$\begingroup$

If there are fewer equations than unknowns, usually there are many solutions. It is not impossible, but indeterminate.

An extreme example is this: one unknown, but no equation !

$\endgroup$
0
57
$\begingroup$

What MATLAB is doing, here, is finding a solution to the underdetermined system of equations that has the fewest possible non-zero elements. That is, it maximises the number of zeros in $x$.

MATLAB can also be applied to actually-unsolvable systems (overdetermined), in which it will give the "solution" with the smallest error (that is, the one that minimises $||Ax-b||_2$).

$\endgroup$
8
  • 8
    $\begingroup$ This seems to be the most cogent information on the issue. $\endgroup$
    – Fattie
    Nov 26, 2019 at 13:05
  • 2
    $\begingroup$ Maximizing the number of zeros still does not uniquely specify an answer. There are solutions for $a=0, b=0$ and $c=0$. Do you know what other other criteria MATLAB uses to choose between them? $\endgroup$
    – Paul Sinclair
    Nov 26, 2019 at 17:20
  • 1
    $\begingroup$ @PaulSinclair: I don't know MATLAB at all, but on any computing system it's a good guess that it searches in the order given. E.g., in the example it fixed the first variable to 0. $\endgroup$
    – Daniel R. Collins
    Nov 26, 2019 at 19:26
  • 1
    $\begingroup$ @DanielR.Collins - that was my guess too, but guessing about such things can easily be wrong, so I was curious what the actual method was. It is an idle curiosity, since I also do not know MATLAB, and have no plans to learn it or use it. But I have dealt with many other programming languages and know that little variances in behavior can sometimes result in massive headaches. $\endgroup$
    – Paul Sinclair
    Nov 26, 2019 at 19:52
  • 3
    $\begingroup$ @PaulSinclair - unfortunately, I've provided as much as I know, but it does appear that, if it's underdetermined, it sets the first undetermined value to zero, then the first remaining undetermined value, and so on. It would be nice if it worked like Octave, which minimises $||x||$. $\endgroup$
    – Glen O
    Nov 27, 2019 at 0:29
23
$\begingroup$

It is not impossible. The problem has a geometric interpretation which may clear things up for you. We know that all points $(x,y,z)$ on a plane in three-dimensional space satisfy equations of the form $Ax+By+Cz=D$. We may therefore interpret the equations $a+2b=8$ and $4b+3c=18$ as planes in three-dimensional space. We know that if two planes in three-dimensional space are not parallel to one another, then they must intersect along a line. Therefore, any point $(a,b,c)$ (like $(0,4,2/3)$, for example) that lies on this line will satisfy the system of equations in your question.

Here is a diagram to illustrate my point. The point $(0,4,2/3)$ is indicated, as well enter image description here

In order to actually find these points, if the line is not parallel to any of the axes, then you may simply pick a value for $a$, $b$, or $c$, leaving you with only two unknowns, and then solve the resulting system of equations as you would normally.

$\endgroup$
16
$\begingroup$

A system of 2 (or $n$) equations in 3 (or $m$) unknowns (with $n<m$) if it has a solution then it has infinite number of solutions.

A system of 3 (or $n$) equations in 2 (or $m$) unknowns (with $n>m$) might not have a solution.

$\endgroup$
6
  • 3
    $\begingroup$ It has infinite solutions, if it has a solution to start with. It might also have no solutions. $\endgroup$
    – take008
    Nov 25, 2019 at 13:55
  • 2
    $\begingroup$ The first sentence is incorrect. E.g. when both equations are $0x+0y+0z=1$, there is no solution. $\endgroup$
    – user1551
    Nov 25, 2019 at 14:04
  • 2
    $\begingroup$ You are right, if I called them "valid equations" will my sentence be right? Because the example you gave is not actually a real "equation" because $0\ne 1$ $\endgroup$
    – Fareed Abi Farraj
    Nov 25, 2019 at 14:08
  • 7
    $\begingroup$ No. $a+b+c+d=1$, $a=1$, $a=-1$. All of these equations are "valid". The way to fix the statement is by saying "if it has a solution, then it has infinite solutions." $\endgroup$
    – take008
    Nov 25, 2019 at 14:28
  • 4
    $\begingroup$ "Valid" doesn't have a formal definition. You're essentially saying "if the equation has solutions then it has solutions. If it doesn't then it doesn't." Which is also what everyone else is saying. $\endgroup$
    – OmnipotentEntity
    Nov 26, 2019 at 3:15
1
$\begingroup$

The set of solutions $S = \{ x \vert Ax=b \}$ will be one of three cases:

  1. No solution, $S = \emptyset$, $b \not\in \{ Ax \mid x\in V\}$, where $A: V \to W$.
  2. One solution, $S = \{ y \}$
  3. Infinite many solutions

The "impossible case" is 1., but your system is of case 3.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .