The wikipedia article on linear least squares only considers overdetermined systems (rows $\geq$ columns). I'm confused if this assumption is really necessary or not.
Given any matrix $A, \|Ax - b\|^2$ is convex and differentiable so the minimum is given by solving the normal equations $A^T Ax = A^T b$. If $A$ has full rank then $A^TA$ is invertible and a unique $x$ exists.
If $A$ does not have full rank, then I still know that there is a unique $z \in \operatorname{range}(A)$ that minimizes the least squares problem by the projection theorem. So I have some $x_0$ such that $z = Ax_0$.
Question 1: In the case that $A$ does not have full rank, the projection theorem gives the existence of a minimizer $x_0$. How can I prove the existence of $x_0$ directly from the normal equations $A^TAx = A^Tb$? aPriori, it doesn't appear that this system needs to be consistent.
Now that I have $x_0$ as a solution, I want to find all other solutions. From my differential equations class, I would guess that all other minimizers are given by $x_0+\ker(A)$. To prove this (I think) I suppose that $y$ is any other minimizer. Then by the uniqueness of $z$, I have $Ay = z$. And so $Ay - Ax_0 = 0$ and $y-x_0 \in \ker(A)$, which says $y\in x_0 + \ker(A)$.
However, these two observations look contradictory: Suppose A has full rank and a non trivial kernel (overdetermined and full rank). The second observation says that $y\in x_0 + \ker(A)$ is a minimizer, indeed, $\|Ay - b\| = \|A(x_0+x) -b\| = \|Ax_0 -b\| =$ minimum. However, $A^TA$ is invertible, so the normal equations say that $x_0$ is unique and given by $x_0 = (A^TA)^{-1}A^Tb.$
Question 2: When $A$ has full rank and a nontrivial kernel, the normal equations says the minimizer $x_0 := (A^TA)^{-1}A^Tb$ is unique. Direct verification shows this is not the case, as any $x\in x_0 + \ker(A)$ is a minimizer. Where is the error in my reasoning that led me to this paradox?
