How do the normal equations *always* have a solution?

Question

My professor says that "the normal equations always have a solution", even when $A$ is not full rank. HOwever, this does not make sense to me. The normal equations are

$$A^\dagger=(A^TA)^{-1}A^T$$

$A^TA$ is invertible IFF $A$ is full column rank. So, it seems to me like there is only a solution to the normal equations if $A$ is full column rank?

edit: I wonder if he meant to say "we can always find the Moore Penrose Inverse even when $A$ is not full rank". that makes more sense to me but I just wantto confirm.

Answer 1

"The normal equations always have a solution" is the same as saying "the column space of $A^T$ is contained in the column space of $A^T A$". One way to see this is to note that the reverse containment is clearly true, and then to show that the rank of $A^T A$ is the same as the rank of $A$. This is closely related to the "four fundamental subspaces theorem"; if you're not aware of this result, pick up Gilbert Strang's book.

They do not always have a unique solution, and indeed they do not when $A$ has deficient column rank.

Answer 2

Actually I think what he meant is that you can solve $A^T A A^\dagger = A^T$ for $A^\dagger$. If $A^T A$ is invertible, the solution is $(A^T A)^{-1} A^T$; otherwise you can use Moore-Penrose.

Answer 3

I reply to this question by completing the answer by Olittle above that says that "It seems intuitive that there should always exist a (possibly non-unique) value of $x$ that minimizes $\|Ax−b\|^2$". This is true because first observe that solving the normal equation of $Ax=b$ is equivalent to the minimization of $\|Ax−b\|^2$ in the Euclidean space $\mathbb{K}^m$. Now, for $A\in \mathbb{K}^{m\times n}$, let $\mathcal{R}(A)$ denote the range of $A$ which is a closed and convex subset of $\mathbb{K}^m$ because $\mathcal{R}(A)$ is a subspace of a finite-dimensional normed space (Recall that a finite-dimensional subspace of a normed space is a closed set, see Every finite-dimension subspace of $\mathcal{X}$ is closed.). Then for any $b\in\mathbb{K}^m$ the problem: minimize $\|y−b\|^2$ for $y\in \mathcal{R}(A)\subseteq\mathbb{K}^m$ has a solution (and is unique) given that it is equivalent to the problem of the minimum distance of the point $b\in\mathbb{K}^m$ to the closed convex subset $\mathcal{R}(A)$ of the Euclidean space (which is a Hilbert space) $\mathbb{K}^m$. Denote then $\bar y$ such solution. Since $\bar y\in \mathcal{R}(A)$, then $Ax=\bar y$ has solution. This is then a minimizer of $\|Ax−b\|^2$, thus it is a solution of the normal equations of $Ax=b$.