Proof Of The Normal Equations Characterization

The Characterization to Prove

For a system \(\mathbf{A}\mathbf{x}=\mathbf{b}\) with no exact solution, least squares asks for a vector \(\mathbf{x}\) whose image \(\mathbf{A}\mathbf{x}\) is as close as possible to \(\mathbf{b}\). Here \(\mathbf{A}\in\mathbb{R}^{m\times n}\), \(\mathbf{x}\in\mathbb{R}^n\), and \(\mathbf{b}\in\mathbb{R}^m\). The squared error at \(\mathbf{x}\) is \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^2\), where the norm is the Euclidean norm. A minimizer is a vector \(\widehat{\mathbf{x}}\) for which this quantity is no larger than its value at any other vector in \(\mathbb{R}^n\).

Write the residual at a candidate \(\widehat{\mathbf{x}}\) as \(\mathbf{r}=\mathbf{A}\widehat{\mathbf{x}}-\mathbf{b}\). The normal equations for that candidate are \(\mathbf{A}^{\top}\mathbf{r}=\mathbf{0}\), or, equivalently, \(\mathbf{A}^{\top}(\mathbf{A}\widehat{\mathbf{x}}-\mathbf{b})=\mathbf{0}\). The point of this tutorial is the exact equivalence: a candidate minimizes the squared error if and only if it satisfies this equation. The proof will not require \(\mathbf{A}\) to be square or to have independent columns.

Why the Normal Equations Express Orthogonality

The column space \(\operatorname{Col}\mathbf{A}\) consists of all vectors \(\mathbf{A}\mathbf{h}\) as \(\mathbf{h}\) ranges over \(\mathbb{R}^n\). Thus changing a coefficient vector by \(\mathbf{h}\) changes the fitted vector by \(\mathbf{A}\mathbf{h}\), a vector in the column space. A residual is orthogonal to that entire space precisely when it is orthogonal to each column of \(\mathbf{A}\).

Proof. Suppose \(\mathbf{A}^{\top}\mathbf{r}=\mathbf{0}\). Any \(\mathbf{y}\in\operatorname{Col}\mathbf{A}\) has the form \(\mathbf{y}=\mathbf{A}\mathbf{h}\) for some \(\mathbf{h}\in\mathbb{R}^n\). Using the Euclidean dot product, \(\mathbf{r}^{\top}\mathbf{y}=\mathbf{r}^{\top}\mathbf{A}\mathbf{h}=(\mathbf{A}^{\top}\mathbf{r})^{\top}\mathbf{h}=0\), so \(\mathbf{r}\perp\mathbf{y}\). Conversely, suppose \(\mathbf{r}\) is orthogonal to every vector in \(\operatorname{Col}\mathbf{A}\). Each column \(\mathbf{a}_j\) of \(\mathbf{A}\) belongs to that column space, so \(\mathbf{a}_j^{\top}\mathbf{r}=0\) for every \(j=1,\dots,n\). These \(n\) quantities are exactly the entries of \(\mathbf{A}^{\top}\mathbf{r}\), so \(\mathbf{A}^{\top}\mathbf{r}=\mathbf{0}\). \(\square\)

This lemma gives a geometric reading of the normal equations: at a least-squares fit, the residual must be perpendicular to every possible change in the fitted vector. The characterization theorem shows both why minimizers have this property and why the property is enough for global minimality.

The Squared-Norm Decomposition

For any change \(\mathbf{h}\in\mathbb{R}^n\) to a candidate \(\widehat{\mathbf{x}}\), the new residual is \(\mathbf{r}+\mathbf{A}\mathbf{h}\). Expanding its squared norm gives the central identity:

The middle term is the interaction between the old residual and the change in the fit. If the normal equations hold, then \(\mathbf{r}^{\top}\mathbf{A}\mathbf{h}=(\mathbf{A}^{\top}\mathbf{r})^{\top}\mathbf{h}=0\), leaving a sum of the current squared error and a nonnegative quantity. Conversely, if the current fit is minimizing, no change along any column direction can improve it. The theorem makes these observations precise without relying on differentiation.

Proof. Set \(\mathbf{r}=\mathbf{A}\widehat{\mathbf{x}}-\mathbf{b}\). First suppose \(\widehat{\mathbf{x}}\) is a least-squares minimizer. For each column \(\mathbf{a}_j\) of \(\mathbf{A}\), changing \(\widehat{\mathbf{x}}\) to \(\widehat{\mathbf{x}}+t\mathbf{e}_j\) changes the residual to \(\mathbf{r}+t\mathbf{a}_j\), where \(t\in\mathbb{R}\) and \(\mathbf{e}_j\) is the \(j\)th standard basis vector in \(\mathbb{R}^n\). Minimality gives \(\|\mathbf{r}+t\mathbf{a}_j\|^2\geq\|\mathbf{r}\|^2\) for every \(t\). If \(\mathbf{a}_j=\mathbf{0}\), then \(\mathbf{a}_j^{\top}\mathbf{r}=0\). If \(\mathbf{a}_j\ne\mathbf{0}\) and \(\mathbf{a}_j^{\top}\mathbf{r}\ne0\), choose \(t=-(\mathbf{a}_j^{\top}\mathbf{r})/\|\mathbf{a}_j\|^2\). Expanding the squared norm for this choice gives \(\|\mathbf{r}+t\mathbf{a}_j\|^2-\|\mathbf{r}\|^2=-(\mathbf{a}_j^{\top}\mathbf{r})^2/\|\mathbf{a}_j\|^2<0\), contradicting minimality. Therefore \(\mathbf{a}_j^{\top}\mathbf{r}=0\) for every column. These are the entries of \(\mathbf{A}^{\top}\mathbf{r}\), so \(\mathbf{A}^{\top}\mathbf{r}=\mathbf{0}\).

Now suppose \(\mathbf{A}^{\top}\mathbf{r}=\mathbf{0}\). For any \(\mathbf{x}\in\mathbb{R}^n\), let \(\mathbf{h}=\mathbf{x}-\widehat{\mathbf{x}}\). Its residual is \(\mathbf{r}+\mathbf{A}\mathbf{h}\), and the squared-norm identity gives \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^2=\|\mathbf{r}\|^2+2\mathbf{r}^{\top}\mathbf{A}\mathbf{h}+\|\mathbf{A}\mathbf{h}\|^2\). The middle term is zero because \(\mathbf{r}^{\top}\mathbf{A}\mathbf{h}=(\mathbf{A}^{\top}\mathbf{r})^{\top}\mathbf{h}=0\). Hence \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^2=\|\mathbf{r}\|^2+\|\mathbf{A}\mathbf{h}\|^2\geq\|\mathbf{r}\|^2=\|\mathbf{A}\widehat{\mathbf{x}}-\mathbf{b}\|^2\). This holds for every \(\mathbf{x}\), so \(\widehat{\mathbf{x}}\) is a least-squares minimizer. Both implications are proved. \(\square\)

Applying the Characterization

A Common Error: Dropping the Cross Term

The squared-norm decomposition always contains the term \(2\mathbf{r}^{\top}\mathbf{A}\mathbf{h}\). It can be removed only when the residual satisfies the normal equations. For a concrete check, use the matrix and vector from the first worked example, but take the candidate \(\mathbf{x}=\mathbf{0}\). Its residual is \(\mathbf{r}=-\mathbf{b}=\begin{bmatrix}-1\\-2\\-2\end{bmatrix}\). Choose \(\mathbf{h}=\begin{bmatrix}1\\0\end{bmatrix}\), so \(\mathbf{A}\mathbf{h}=\begin{bmatrix}1\\0\\1\end{bmatrix}\). Then \(\|\mathbf{r}\|^2=9\), \(\|\mathbf{A}\mathbf{h}\|^2=2\), and \(\mathbf{r}^{\top}\mathbf{A}\mathbf{h}=-3\). The actual new squared error is \(9+2(-3)+2=5\), not \(9+2=11\). In fact the new residual is \(\mathbf{r}+\mathbf{A}\mathbf{h}=\begin{bmatrix}0\\-2\\-1\end{bmatrix}\), whose squared norm is \(5\).

Another tempting but incorrect conclusion is that the residual at a minimizer must be \(\mathbf{0}\). That would mean \(\mathbf{A}\widehat{\mathbf{x}}=\mathbf{b}\), which need not be possible. In the first example the residual is nonzero, yet its dot product with each column is zero and the squared-norm decomposition proves minimality. The normal equations describe the residual's direction relative to the column space, not whether the residual itself vanishes.

What the Equivalence Does and Does Not Say

The theorem is an if-and-only-if test for a particular candidate: checking \(\mathbf{A}^{\top}(\mathbf{A}\widehat{\mathbf{x}}-\mathbf{b})=\mathbf{0}\) proves that candidate minimizes the error, and every minimizer must pass the same test. The proof uses only the Euclidean inner product, the matrix-vector product, and the nonnegativity of a squared norm. It does not assume a unique minimizer, independent columns, or an invertible matrix. These hypotheses matter for other questions, such as whether the coefficient vector is unique, but they are not needed for this characterization.

The decomposition also quantifies how a candidate changes under a perturbation. When the normal equations hold, the increase in squared error is exactly \(\|\mathbf{A}\mathbf{h}\|^2\). If a perturbation changes the coefficients but leaves the fitted vector unchanged, then \(\mathbf{A}\mathbf{h}=\mathbf{0}\), and the error remains the same. Otherwise, the squared error increases by the squared length of the change in the fit.