Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

2 Answers 2

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|improve this answer

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.

share|improve this answer
1  
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

Your Answer

 
discard

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.