Using the Left-Inverse to "Solve" an Impossible System of Equations

I was working with the following system of equations:

$$\begin{split} \begin{bmatrix} 4 & 0\\ 0 & 5\\ 0 & 0\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \end{bmatrix} & = \begin{bmatrix} 1\\ 1\\ 1\\ \end{bmatrix} \end{split} $$

Clearly, this has no solution on account of the last rows in the coefficient and solution matrices.

However, multiplying by the left-inverse of the coefficient matrix seems to imply a solution:

$$\begin{split} \begin{bmatrix} \frac{1}{4} & 0 & b_{13}\\ 0 & \frac{1}{5} & b_{23}\\ \end{bmatrix} \begin{bmatrix} 4 & 0\\ 0 & 5\\ 0 & 0\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \end{bmatrix} & = \begin{bmatrix} \frac{1}{4} & 0 & b_{13}\\ 0 & \frac{1}{5} & b_{23}\\ \end{bmatrix} \begin{bmatrix} 1\\ 1\\ 1\\ \end{bmatrix} \\ \begin{bmatrix} x_1\\ x_2\\ \end{bmatrix} & = \begin{bmatrix} \frac{1}{4} + b_{13}\\ \frac{1}{5} + b_{23}\\ \end{bmatrix} \end{split} $$

Where $b_{13}$ and $b_{23}$ can be any number. As stated above, there is no solution to this system, so any solution obtained by the above method is wrong.

What I am not understanding is why, after applying the rules of matrix multiplication, does it seem possible that there is a solution? Did I make a mistake somewhere in the process, and/or is there some fundamental nuance of linear algebra that I'm missing here?

Solution 1:

If $Av=b$, then $TAv=Tb$. The converse is in general not true, as you have noticed. In fact, $Av=b\iff Av-b=0$, but

$$TAv=Tb\iff T(Av-b)=0\iff Av-b\in \ker T$$

Hence, the converse may fail to hold if $\ker T \neq \{0\}$, that is, if $T$ is not injective.

Solution 2:

Multiplying both sides by a non invertible matrix can change the solution set. For instance, you get infinitely many solutions when multiplying both sides of any linear system by the zero matrix.

A different case, but similar under several respects, is when you have $x^2=-1$; if you multiply both sides by $x$, you get the equation $x^3=-x$, which has $0$ as a solution. Or, if you square both sides, you get $x^4=1$, which has $1$ and $-1$ has roots. On the other hand, the original equation has no solution (in the real numbers). The main point is that if you do reversible transformations to your equation, you are guaranteed that the solution set doesn't change; with nonreversible transformations, you don't lose solutions, but may add some.

However there is a real-world application of this “wrong” method. If you choose appropriately the left inverse, namely use the Moore-Penrose pseudoinverse, which in this case is $$ A^+=(A^TA)^{-1}A^T $$ where $A$ is the coefficient matrix of the given system, produces a system which features the “least squares solution”.

Since $$ \begin{bmatrix} 4 & 0 & 0 \\ 0 & 5 & 0 \end{bmatrix} \begin{bmatrix} 4 & 0 \\ 0 & 5 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 16 & 0 \\ 0 & 25 \end{bmatrix} $$ we have $$ A^+=\begin{bmatrix} 1/16 & 0 \\ 0 & 1/25 \end{bmatrix} \begin{bmatrix} 4 & 0 & 0 \\ 0 & 5 & 0 \end{bmatrix} = \begin{bmatrix} 1/4 & 0 & 0 \\ 0 & 1/5 & 0 \end{bmatrix} $$ and $$ A^+\begin{bmatrix}1\\1\\1\end{bmatrix}=\begin{bmatrix} 1/4 \\ 1/5 \end{bmatrix} $$

While the given system has no solution, there are reasons why $x_1=1/4$ and $x_2=1/5$ can be considered “almost a solution”.

Solution 3:

All you have shown is that if $\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$ is a solution then $\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$ has the form given. This doesn't mean that there really is a solution.

Solution 4:

Examine what you’ve done in terms of the system of linear equations that your matrix equation represents: $$\begin{align}4x_1&=1\\5x_2&=1\\0&=1.\end{align}$$ This system is obviously inconsistent because of the last equation. Multiplying by the matrix in your question amounts to replacing the first equation with $\frac14$ times the first one plus $b_1$ times the second, and similarly replacing the second equation by a linear combination of it and the third equation, producing $$\begin{align} x_1&=b_1+\frac14 \\ x_2&=b_2+\frac15.\end{align}$$ Note, however, that in the process you’ve also discarded the third equation, which was the one causing the inconsistency. This new system does indeed have a solution, but it’s not equivalent to the original system. Effectively, you’ve back-substituted $1$ for $0$ in the first two equations.