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

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.

• $A^{T}A x=A^{T}b$ can have a solution/solutions even if $A^{T}A$ is not invertible. Sep 17, 2018 at 16:35
• I disagree with the statement of what the normal equations are in this question. The normal equations are $A^T Ax = A^T b$. The normal equations can be derived by minimizing $\frac12 \| Ax - b \|^2$ with respect to $x$. Setting the gradient equal to $0$, we obtain $A^T (Ax - b) = 0$. It seems intuitive that there should always exist a (possibly non-unique) value of $x$ that minimizes $\frac12 \|Ax - b \|^2$, even if $A$ does not have full rank. Sep 17, 2018 at 16:52

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

• I guess what I'm confused by is how the normal equations even make sense at all if $A^TA$ is not invertible. Sep 17, 2018 at 16:43
• @guimption The normal equations are not $x=(A^T A)^{-1} A^T b$. They are $A^T A x = A^T b$.
– Ian
Sep 17, 2018 at 16:43
• Ah, that's key thank you!! Sep 17, 2018 at 16:43
• @Ian Would you have an argument for why $A^T$ and $A^TA$ have the same rank?
– Blue
Feb 22, 2021 at 17:27
• @Blue Basically what you need to get to is that a matrix $B$ maps its row space to its column space. Thus the column space of $A^T A$ will contain the column space of $A$ if the column space of $A$ contains the row space of $A^T$...which it certainly does, because those are the same space.
– Ian
Mar 19, 2021 at 15:32

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.

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