1
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ What matrix is $A'$? $\endgroup$ – David P Oct 21 '14 at 6:04
  • $\begingroup$ @DavidPeterson It's the transpose of $A$. $\endgroup$ – yurnero Oct 21 '14 at 6:04
  • $\begingroup$ Did you have a look at en.wikipedia.org/wiki/Generalized_inverse Perhaps this helps. $\endgroup$ – quid Oct 21 '14 at 6:05
  • 2
    $\begingroup$ 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. $\endgroup$ – quid Oct 21 '14 at 6:08
  • 2
    $\begingroup$ 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 :-) $\endgroup$ – Jyrki Lahtonen Oct 21 '14 at 6:16
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oh I see. Great point! $\endgroup$ – yurnero Oct 21 '14 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.