# Solving $Ax=B$: what's wrong with this linear algebra argument?

With $K>L$ and assuming that we are working with real variables, suppose that $B$ is $K\times 1$ and $A$ is $K\times L$ with full column rank. I'm trying to find $x$ ($L\times 1$) satisfying: $$Ax=B.\tag{i}$$ There are more equations than unknowns $(K>L)$ so there is no guarantee that we can find a solution. Yet, I cannot find what is wrong with this argument: pre-multiply both sides of (i) with $A'$: $$A'Ax=A'B\implies x=(A'A)^{-1}A'B.\tag{ii}$$ The matrix $A'A$ is invertible because $A$ has full column rank. Could you please explain why (ii) doesn't work? I can see that if $x=(A'A)^{-1}A'B$, then $$Ax=A(A'A)^{-1}A'B$$ which doesn't readily simplify to $B$. But is this enough to say (ii) is invalid? If (ii) doesn't work, how could I solve (i) or show that no solution exists?

• What matrix is $A'$? – David P Oct 21 '14 at 6:04
• @DavidPeterson It's the transpose of $A$. – yurnero Oct 21 '14 at 6:04
• Did you have a look at en.wikipedia.org/wiki/Generalized_inverse Perhaps this helps. – quid Oct 21 '14 at 6:05
• Sorry for another comment. I am not really sure I understand you and am a bit in a rush, but I think $A'$ does not induce an injective map. Thus Ax and B might be different while after multiplication with A' they are equal. – quid Oct 21 '14 at 6:08
• David's (+1) solution explains the logic. I will give a numerical example to make sure that you see where the problem is. With $A={1\choose 1}$ and $B={2\choose 1}$ you have the impossible system: $x=2$ AND $x=1$. Your idea to premultiply by $A'$ then gives as a consequence the system $x+x=2+1$ or $2x=3$. From that you would solve $x=3/2$, and realize that something went very wrong :-) – Jyrki Lahtonen Oct 21 '14 at 6:16

The difficulty is really logic, not algebra. It is true that $$\def\\#1{{\bf#1}}A\\x=\\b\quad\Rightarrow\quad A'A\\x=A'\\b\ ,$$ but it is not true that $$\def\\#1{{\bf#1}}A\\x=\\b\quad\Leftrightarrow\quad A'A\\x=A'\\b\ .$$ You have shown correctly that if there is a solution it is $\\x=(A'A)^{-1}A'\\b$, but this does not mean that there actually is a solution.