Proof of equivalence theorem about left invertible matrices

Question

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?

score 4 · Accepted Answer · answered Jan 28 '13 at 21:39

4

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

answered Jan 28 '13 at 21:39

Giuseppe Negro

32,319

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

score 2 · Answer 2 · answered Jan 28 '13 at 21:26

2

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.

answered Jan 28 '13 at 21:26

Arin Chaudhuri

6,349

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. – Arin Chaudhuri Jan 29 '13 at 00:32

score 1 · Answer 3 · answered Jan 28 '13 at 21:27

1

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

answered Jan 28 '13 at 21:27

Julien

44,791

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. – Julien Jan 28 '13 at 21:58

Proof of equivalence theorem about left invertible matrices

3 Answers3