# Prove: existence of solution of $Ax = b$ by least squares

I'm studying for my exam of linear algebra.. I want to prove the following corollary:

Given $A \in{R^{m\times n}}$, there is always a solution $x$ to $Ax = y$ for the least-squares minimization problem, if and only if $A$ has rank $n$ (full column rank).

-
This seems strange. We usually resort to least squares when we have more equations than unknowns, that's more rows than columns, that's $m\gt n$, in which case $A$ can't have rank $m$. –  Gerry Myerson Aug 27 '12 at 5:36
@GerryMyerson yeah my bad rank (A) = n –  franvergara66 Aug 27 '12 at 5:37
So that would be full column rank, right? –  Gerry Myerson Aug 27 '12 at 5:41
@GerryMyerson That's right, right now I edit the question –  franvergara66 Aug 27 '12 at 5:44
The way you do least squares is, you solve the normal equation, $A^tAx=A^ty$. Note that $A^tA$ is an $n\times n$ matrix. If the rank of $A$ is less than $n$, then the rank of $A^tA$ is less than $n$, so there are vectors $y$ not in its column space, so there are vectors $y$ for which the normal equation has no solution. If $A$ has rank $n$, then (you can prove that) $A^tA$ has rank $n$, so the normal equation has a solution for all $y$.
Actually the problem $$\|Ax-y\|=\min$$ for any given $A$ and $y$ has always a solution $x$. Any $\tilde{x}=x+z$, where $z\in\ker A$, is again a solution. If $A$ has a full column rank and hence $\dim\ker A=0$, then the problem has the solution, that is, a solution which is unique.
I cannot yet comment on answers, so I put it here. To correct the answer of Gerry Myerson, the system $A^TAx=A^Ty$ has always a solution even when the rank is not "full" since the system is consistent, that is, $A^Ty$ lies in the column-space of $A^TA$. –  Algebraic Pavel Aug 20 '13 at 12:47