Existence of least squares solution to $Ax=b$ Does a least squares solution to $Ax=b$ always exist?

We just need to prove that the rank of matrix $A^TA$ equals the rank of augmented matrix $[A^TA,A^Tb]$. We prove it below:
denote the rank of matrix as rank A=k. By using the rank equality(can be found in nearly every algebra textbook.):rank $A^TA$=rank $A$=rank $A^T$. We know rank $[A^TA,A^Tb]\ge$rank A, since the former has one more column than the latter. But, on the other hand, $[A^TA,A^Tb]=A^T[A,b]$, and by using the rank inequality(can be found in some algebra textbooks):
rank $AB\le$ min{rank A, rank B}. so rank $A^T[A,b]$$\le$rank $A^T$=rank A=k.
Combining the two inequality, we have rank $[A^TA,A^Tb]$=k.
So the rank of matrix$[A^TA]$ is always equal to the rank of the augmented matrix$[A^TA,A^Tb]$. By the theorem of existence and uniqueness of vector equation, we know the least square problem always has at least one solution. Thus we finish our proof. Q.E.D.
