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

Question

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?

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

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

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

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

Answer 5

Here is a simpler example of what you are doing. Consider the argument

\begin{align} 2 \times 3 &= 8 \\ \frac 12 \times 2 \times 3 &= \frac 12 \times 8 \\ 3 &= 4 \end{align}

If you put $``="$ between two quantities that aren't equal, then you cannot believe any conclusions that may follow.

\begin{equation} \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} \end{equation}

Is equivalent to

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

Which clearly has no solution.

Geometrically, the point $(1,1,1)$ is not on the plane spanned by the vectors $(4,0,0)$ and $(0,5,0)$.

Equations like this occur all of the time in statistics. Their, $``$solution$"$ would be to add an error term on the right end

$$\left[ \begin{array}{c} 4 & 0\\ 0 & 5\\ 0 & 0\\ \end{array} \right] \left[ \begin{array}{c} x_1\\ x_2\\ \end{array} \right] = \left[ \begin{array}{c} 1\\ 1\\ 1\\ \end{array} \right] + \left[ \begin{array}{c} \epsilon_1\\ \epsilon_2\\ \epsilon_3\\ \end{array} \right]$$

and then find the values of $x_1$ and $x_2$ that will minimize the sum of the squares of the error: $\epsilon_1^2 + \epsilon_2^2 + \epsilon_3^2$

Geometrically, that would be the perpendicular projection of the point $(1,1,1)$ onto the plane spanned by the vectors $(4,0,0)$ and $(0,5,0)$.

It turns out that, even if $Ax = b$ has no solution, $A^TAx = A^Tb$ does have a solution, namely $\hat x = \left(A^TA \right)^{-1}A^Tb$, and $\hat x$ minimizes the sum of the squares of the errors, $\|b- A\hat x \|^2$

Answer 6

One of the principles of classical logic is that if we accept any false statement as true, then it is possible to prove anything ("paradox of entailment").

Your initial equation implies 0*x1 + 0*x2 = 1, i.e. 0 = 1. By manipulating the two sides of this "equation" we can then get any mathematical result we like.

Answer 7

It is a general fact of life that when you try to solve an equation $F(X) = V$ and you transform the system by implication: $$F(X) = V\quad \Longrightarrow \quad G(X)= W$$ then the second equation may have more solutions than the first one. On the other hand, no solution is lost.

Nevertheless, such implications remain a powerful tool to solve systems, especially non linear systems. Only remember that after solving $G(X) = W$, one needs to remove the extra "solutions".