We know from linear algebra, the least square solution of linear equation system : $$Ax=b$$ always exists. That is, the equation $$A^TAx=A^Tb$$ always has at least one solution. Most of us explain it existence by interpreting least square problem as a matter of orthogonal projection. It's correct, I know. But can we prove this by showing that the rank of matrix $$A^TA$$ is equal to the rank of the augmented matrix:$$[A^TA,A^Tb]$$for any given vector b?
I've worked for hours but failed to show that.
Although there is a similar thread in mathematics.SX, but I personally think there is no good answer presented there. So I address this problem again.
Thanks at first!
[update]
Now I come up with a proof for this proposition:
suppose that rank $A^TA$=k, and the matrix $[A^TA,A^Tb]$ has one more column than $[A^TA]$, so rank $[A^TA,A^Tb]\ge k$. But on the other hand, we have $[A^TA,A^Tb]=A^T[A,b]$, using the rank inequality, we have $rank [A^TA,A^Tb]\le rank A^T$. Since (we can prove that) $ rank A^TA= rank A= rank A^T$ for any given matrix A. So the inequality is actually $rank [A^TA,A^Tb]\le k$. Combining the two inequalities, we have $rank [A^TA,A^Tb]=rank A^TA$. Q.E.D.
You can decompose $b$ into a vector $Av$ in the column space of $A$ and a vector $w$ orthogonal to that column space: $Av+w=b$. Then $A^tAv+A^tw=A^tb$. But $w$ is orthogonal to the row space of $A^t$, so $A^tw=0$, so $A^tAv=A^tb$.