23

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?

linker
  • 483
  • 1
  • 3
  • 9
  • 91
    It is not impossible to solve this equation system , the solution is just not unique. – Peter Nov 25 '19 at 13:34
  • 53
    This is just one of many solutions. – Hagen von Eitzen Nov 25 '19 at 13:34
  • 9
    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. – Hans Lundmark Nov 25 '19 at 14:45
  • 3
    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?!? – Hans Lundmark Nov 25 '19 at 14:56
  • 6
    Matlab tries to make the maximum number of elements zero. – Austin Nov 26 '19 at 06:45
  • 2
    Matlab tries to minimize the 2-norm, this is not same as minimizing 0-norm which would be to make maximum number of elements 0. – mathreadler Nov 26 '19 at 10:07
  • 1
    @mathreadler: But that's what's strange! It's the answer given by Octave that is the one with minimal 2-norm (I checked it by hand), not the one given by Matlab (according to that web page). – Hans Lundmark Nov 26 '19 at 14:46
  • 1
    IIRC Matlab finds an invertible square submatrix and solves with that (but I don't know more details). – Dirk Nov 26 '19 at 17:41
  • 1
    @HansLundmark Hmm. That I did not expect. I expected Matlab to do a pseudoinverse or something similar that would minimize least square. Maybe they changed this in some recent version? – mathreadler Nov 26 '19 at 18:51
  • 2
    A little more detail about MATLABs backslash is here https://medium.com/mathworks/the-worlds-simplest-impossible-problem-d0515b861fc4 by Cleve Moler himself. MATLAB determines the rank of $A$ and gives a solution with no more non-zero entries than the rank. Interestingly, the MATLAB help https://de.mathworks.com/help/matlab/ref/mldivide.html states that the least squares solution is computed which is false. – Dirk Nov 27 '19 at 12:35
  • 1
    @Dirk: It's presumably a least squares solution in the (usual) sense that the residual $b-Ax$ has minimal 2-norm, not that $x$ has minimal 2-norm. Still, I find it somewhat weird that Mathworks have chosen the example in this question as an example of a “least squares solution”, since the residual is zero in this case... It might have been more enlightening to take an underdetermined system where the coefficient matrix is not of full rank, and the right-hand side is not in the column space. – Hans Lundmark Nov 27 '19 at 12:44
  • 1
    @HansLundmark Oh, I haven't heard of this meaning of "least squares" but sure, this makes a lot of sense. – Dirk Nov 27 '19 at 12:46

5 Answers5

125

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 !

J. W. Tanner
  • 60,406
57

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

Glen O
  • 12,425
  • 8
    This seems to be the most cogent information on the issue. – Fattie Nov 26 '19 at 13:05
  • 2
    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? – Paul Sinclair Nov 26 '19 at 17:20
  • 1
    @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. – Daniel R. Collins Nov 26 '19 at 19:26
  • 1
    @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. – Paul Sinclair Nov 26 '19 at 19:52
  • 3
    @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||$. – Glen O Nov 27 '19 at 00:29
  • @GlenO - That is okay. As I said, it was only an idle curiosity. My comment was more about pointing out that maximizing zeros did not completely define the result. – Paul Sinclair Nov 27 '19 at 00:35
  • Link to documentation: https://mathworks.com/help/matlab/math/systems-of-linear-equations.html#bt7ov7u. No mention of how Matlab selects which components are zero, however. – Hans Lundmark Nov 27 '19 at 12:49
  • @GlenO: As pointed out on this page (given by user Dirk in the comments to the question), the solution with minimal 2-norm is obtained from x = pinv(A)*b. – Hans Lundmark Nov 27 '19 at 12:50
23

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.

joshuaheckroodt
  • 2,789
16

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.

Fareed Abi Farraj
  • 3,446
  • 3
    It has infinite solutions, if it has a solution to start with. It might also have no solutions. – take008 Nov 25 '19 at 13:55
  • 2
    The first sentence is incorrect. E.g. when both equations are $0x+0y+0z=1$, there is no solution. – user1551 Nov 25 '19 at 14:04
  • 2
    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$ – Fareed Abi Farraj Nov 25 '19 at 14:08
  • 7
    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." – take008 Nov 25 '19 at 14:28
  • I did fix it in the way you said, but I still see that by your example we have $1=-1$ and this can't be considered "valid", so I still see if the system is "valid" then it has infinite number of solutions. But ofcourse if you figured out another example about what we are calling a "valid system" with no solutions then I'd like to know it please. – Fareed Abi Farraj Nov 25 '19 at 14:38
  • 4
    "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. – OmnipotentEntity Nov 26 '19 at 03:15
1

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.

mvw
  • 34,562