2
$\begingroup$

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

  • 0
    @GerryMyerson That's right, right now I edit the question2012-08-27

2 Answers 2

4

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

1

Actually the problem $ \|Ax-y\|=\min $ for any given $A$ and $y$ has always a solution $x$ since the system of normal equations $A^TAx=A^Ty$ is solvable for any $y$. 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.