# Proof of equivalence theorem about left invertible matrices

I am taking a course in Matrix Theory and we have a theorem that states (among other things) that:

The following conditions on the matrix $A$ of size $m \times n$ are equivalent:

(1) A has left inverse
(2) The system $Ax=b$ has at most one solution for any column vector $b$.
...

The proof that (1) $\implies$ (2) goes like this:

If $Ax=b$ and $V$ is a left inverse, then $VAx=Vb \implies x=Vb$, so we have at most one solution (if any).

The thing is, left inverses are not unique right? Take $A = \left( \begin{matrix} 1 \\ 0 \end{matrix} \right)$ That has left inverses $V_1= \left( \begin{matrix} 1 & 0 \end{matrix} \right)$ and $V_2 = \left( \begin{matrix} 1 & 1 \end{matrix} \right)$

Does this mean that the proof is wrong or am I missing something?

-
+1 Good question! – user1551 Jan 28 '13 at 22:21

Yours is a nice observation. The way out of this apparent issue is that if $b=Ax$, then $V_1b = V_2 b = x$. We can check this directly with the matrices of your example, that is $$\begin{array}{ccc} A=\begin{bmatrix} 1 \\ 0\end{bmatrix}, & V_1=\begin{bmatrix} 1 & 0\end{bmatrix},& V_2=\begin{bmatrix} 1 & 1\end{bmatrix}\end{array}.$$ In this case $b=Ax$ means that $$b= \begin{bmatrix} b_1 \\ 0 \end{bmatrix},$$ for a scalar $b_1$. Then $$V_1 b= b_1= V_2b.$$

-
Thank you very much! How come things get so obvious once you see the solution =) – evading Jan 28 '13 at 21:41
@refuser: You're welcome. Yours is actually a nice question: it's a good thing to stress-test theorems and proofs like this. – Giuseppe Negro Jan 28 '13 at 21:58

Existence of left inverse means $A$ is 1-1, i.e., $Ax_1 = Ax_2$ implies $VAx_1 = VAx_2$ , i.e., $x_1=x_2$. So a solution, if it exists, must be unique.

-
Thank you for you help. I chose to accept another solution as that was the one the made it "click" for me. Even if I in retrospect believe that you ment the same thing. – evading Jan 28 '13 at 21:43
No problems, you did the correct thing by selecting the better answer. – ACARCHAU Jan 29 '13 at 0:32

Adding an intermediate step could help.

The matrix $A$ has a left inverse iff $A$ is injective iff the system $Ax=b$ has at most one solution for every $b$.

-
I'm afraid that your answer was not so helpful to me. Though I know what an injective function is I'm not quite there yet with the matrices. I still want to thank you for taking the time to answer though. – evading Jan 28 '13 at 21:44
You're welcome, sorry it did not help. – 1015 Jan 28 '13 at 21:58