Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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