From a Least-Squares Problem to a Linear System
When a system \(\mathbf{A}\mathbf{x}=\mathbf{b}\) has no exact solution, least squares asks for a coefficient vector \(\mathbf{x}\) whose image \(\mathbf{A}\mathbf{x}\) is as close as possible to \(\mathbf{b}\). “As close as possible” means minimizing the Euclidean distance \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|\), or equivalently its square. The normal equations turn this minimization problem into a linear system that can be solved by familiar row reduction.
Throughout this tutorial, \(\mathbf{A}\in\mathbb{R}^{m\times n}\), \(\mathbf{b}\in\mathbb{R}^{m}\), and \(\mathbf{x}\in\mathbb{R}^{n}\). The residual for a proposed coefficient vector is defined here as \(\mathbf{r}=\mathbf{b}-\mathbf{A}\mathbf{x}\). A least-squares solution is any vector \(\widehat{\mathbf{x}}\) that minimizes \(\|\mathbf{b}-\mathbf{A}\mathbf{x}\|\) over all \(\mathbf{x}\in\mathbb{R}^{n}\). Its fitted vector is \(\mathbf{A}\widehat{\mathbf{x}}\), and its residual is \(\mathbf{b}-\mathbf{A}\widehat{\mathbf{x}}\).
The matrix dimensions help prevent setup errors: \(\mathbf{A}^{\top}\mathbf{A}\) is \(n\times n\), \(\mathbf{A}^{\top}\mathbf{b}\) is \(n\times1\), and the unknown coefficient vector is \(n\times1\). The normal matrix is symmetric because \((\mathbf{A}^{\top}\mathbf{A})^{\top}=\mathbf{A}^{\top}\mathbf{A}\). It need not be invertible; row reduction, not an assumed inverse, is the general way to solve the equations.
Why Solving the Normal Equations Works
The equivalence in the definition is the reason that row-reducing the normal equations solves the minimization problem. The proof below also shows why the equations describe a minimum rather than merely a candidate.
Proof. Write \(\mathbf{r}=\mathbf{b}-\mathbf{A}\widehat{\mathbf{x}}\). First suppose \(\widehat{\mathbf{x}}\) solves the normal equations. Then \(\mathbf{A}^{\top}\mathbf{r}=\mathbf{A}^{\top}\mathbf{b}-\mathbf{A}^{\top}\mathbf{A}\widehat{\mathbf{x}}=\mathbf{0}\). For any other coefficient vector \(\mathbf{y}\), put \(\mathbf{h}=\mathbf{y}-\widehat{\mathbf{x}}\). Expanding the squared norm gives $$ \|\mathbf{b}-\mathbf{A}\mathbf{y}\|^2 =\|\mathbf{r}-\mathbf{A}\mathbf{h}\|^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\). Since \(\|\mathbf{A}\mathbf{h}\|^2\ge0\), we have \(\|\mathbf{b}-\mathbf{A}\mathbf{y}\|^2\ge\|\mathbf{r}\|^2\). Thus \(\widehat{\mathbf{x}}\) is a minimizer.
Conversely, suppose \(\widehat{\mathbf{x}}\) is a minimizer. For any \(\mathbf{h}\in\mathbb{R}^{n}\) and real \(t\), the vector \(\widehat{\mathbf{x}}+t\mathbf{h}\) is an allowed competitor. Expanding its squared residual gives $$ \|\mathbf{b}-\mathbf{A}(\widehat{\mathbf{x}}+t\mathbf{h})\|^2 =\|\mathbf{r}\|^2-2t\mathbf{r}^{\top}\mathbf{A}\mathbf{h} +t^2\|\mathbf{A}\mathbf{h}\|^2. $$ If \(\mathbf{r}^{\top}\mathbf{A}\mathbf{h}\ne0\), choose \(t\) with the same sign as that scalar and sufficiently small nonzero magnitude. The term linear in \(t\) is then negative and has larger magnitude than the quadratic term, contradicting minimality. Therefore \(\mathbf{r}^{\top}\mathbf{A}\mathbf{h}=0\) for every \(\mathbf{h}\). Taking \(\mathbf{h}=\mathbf{A}^{\top}\mathbf{r}\) yields \(\|\mathbf{A}^{\top}\mathbf{r}\|^2=0\), so \(\mathbf{A}^{\top}\mathbf{r}=\mathbf{0}\). Substituting \(\mathbf{r}=\mathbf{b}-\mathbf{A}\widehat{\mathbf{x}}\) gives the normal equations. \(\square\)
This result justifies the computational recipe: form the normal equations, solve them, and compute the residual for a solution. Least-squares solutions exist for every real matrix and data vector: the column space of \(\mathbf{A}\) is a finite-dimensional subspace of \(\mathbb{R}^{m}\), so the Best Approximation Theorem gives a closest vector in that column space. The normal-equations theorem then says its coefficient vectors are precisely the solutions of the system.
A Row-Reduction Procedure
Compute \(\mathbf{A}^{\top}\mathbf{A}\) and \(\mathbf{A}^{\top}\mathbf{b}\), checking their dimensions before proceeding.
Row-reduce \(\left[\mathbf{A}^{\top}\mathbf{A}\mid\mathbf{A}^{\top}\mathbf{b}\right]\). Read off the full solution set, including any free variables.
Any solution of the normal equations is a least-squares solution. If there are free variables, state whether you are giving one solution or the full family.
Compute \(\mathbf{r}=\mathbf{b}-\mathbf{A}\widehat{\mathbf{x}}\) using the chosen vector, and substitute into the normal equations as a check.
For an arbitrary matrix, the normal equations are consistent, but their solution need not be unique. When the columns of \(\mathbf{A}\) are dependent, different coefficient vectors can produce the same fitted vector. Row reduction reveals this through free variables; setting those variables to convenient values provides a particular minimizing vector without discarding the rest of the solution family.
Worked Normal-Equation Calculations
Worked Example: A Unique Least-Squares Solution
Find a least-squares solution for \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}1\\2\\2\end{bmatrix}\), then report its residual.
First compute the products. The columns of \(\mathbf{A}\) are \((1,0,1)^{\top}\) and \((0,1,1)^{\top}\), so their pairwise dot products give \(\mathbf{A}^{\top}\mathbf{A}\). The dot products with \(\mathbf{b}\) give \(\mathbf{A}^{\top}\mathbf{b}\):
Row-reduce the augmented normal system. Swap the rows, subtract twice the new first row from the second, scale the second row by \(-\tfrac13\), and clear above its pivot:
Thus \(\widehat{\mathbf{x}}=\begin{bmatrix}\tfrac23\\\tfrac53\end{bmatrix}\). Its fitted vector is \(\mathbf{A}\widehat{\mathbf{x}}=\begin{bmatrix}\tfrac23\\\tfrac53\\\tfrac73\end{bmatrix}\), so the residual is
Check: multiplying the normal matrix by the proposed vector gives \(\begin{bmatrix}2&1\\1&2\end{bmatrix}\begin{bmatrix}\tfrac23\\\tfrac53\end{bmatrix} =\begin{bmatrix}3\\4\end{bmatrix}\), as required. Also \(\mathbf{A}^{\top}\mathbf{r}=\begin{bmatrix}\tfrac13-\tfrac13\\\tfrac13-\tfrac13\end{bmatrix}=\mathbf{0}\). The squared residual length is \(\|\mathbf{r}\|^2=\tfrac19+\tfrac19+\tfrac19=\tfrac13\).
Worked Example: A Four-Equation Fit
For \(\mathbf{A}=\begin{bmatrix}1&0\\1&1\\1&2\\1&3\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}1\\2\\2\\4\end{bmatrix}\), find a minimizing coefficient vector and its residual.
Compute each entry from the columns \((1,1,1,1)^{\top}\) and \((0,1,2,3)^{\top}\):
In the augmented matrix, scale the first row by \(\tfrac12\), subtract three times that row from the second, scale the second row by \(\tfrac15\), and clear the entry above its pivot:
The first row now gives \(x_1=\tfrac9{10}\), and the second gives \(x_2=\tfrac9{10}\). Hence \(\widehat{\mathbf{x}}=\begin{bmatrix}\tfrac9{10}\\\tfrac9{10}\end{bmatrix}\). The fitted vector is \(\begin{bmatrix}\tfrac9{10}\\\tfrac95\\\tfrac{27}{10}\\\tfrac{18}{5}\end{bmatrix}\), and therefore
Check: the normal system gives \(\begin{bmatrix}4&6\\6&14\end{bmatrix}\begin{bmatrix}\tfrac9{10}\\\tfrac9{10}\end{bmatrix} =\begin{bmatrix}9\\18\end{bmatrix}\). For the residual, \(\mathbf{A}^{\top}\mathbf{r}\) has entries \(\tfrac1{10}+\tfrac2{10}-\tfrac7{10}+\tfrac4{10}=0\) and \(\tfrac2{10}-\tfrac{14}{10}+\tfrac{12}{10}=0\). Its squared length is \(\|\mathbf{r}\|^2=\tfrac{1+4+49+16}{100}=\tfrac7{10}\).
Worked Example: Dependent Columns and Many Minimizers
Let \(\mathbf{A}=\begin{bmatrix}1&2\\0&0\\1&2\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}1\\1\\3\end{bmatrix}\). Solve the normal equations and give one minimizing vector with its residual.
The second column of \(\mathbf{A}\) is twice the first, so dependence is expected. Direct multiplication gives
Reduce the augmented matrix by scaling the first row by \(\tfrac12\) and subtracting four times that row from the second:
Thus \(x_1+2x_2=2\). Let \(x_2=t\), where \(t\in\mathbb{R}\); the full solution family is \(\mathbf{x}=\begin{bmatrix}2-2t\\t\end{bmatrix}\). Choose \(t=0\), giving \(\widehat{\mathbf{x}}=\begin{bmatrix}2\\0\end{bmatrix}\). Then \(\mathbf{A}\widehat{\mathbf{x}}=\begin{bmatrix}2\\0\\2\end{bmatrix}\) and \(\mathbf{r}=\begin{bmatrix}-1\\1\\1\end{bmatrix}\).
Check: the chosen vector satisfies the normal equations because \(\begin{bmatrix}2&4\\4&8\end{bmatrix}\begin{bmatrix}2\\0\end{bmatrix} =\begin{bmatrix}4\\8\end{bmatrix}\). Its residual has squared length \(1+1+1=3\), and \(\mathbf{A}^{\top}\mathbf{r}=\begin{bmatrix}-1+1\\-2+2\end{bmatrix}=\mathbf{0}\). For any \(t\) in the solution family, \(\mathbf{A}\mathbf{x}=\begin{bmatrix}2\\0\\2\end{bmatrix}\), so all these coefficient vectors produce the same fit and residual.
Uniqueness and a Common Error
Proof. For any \(\mathbf{z}\in\mathbb{R}^{n}\), \(\mathbf{z}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{z}=\|\mathbf{A}\mathbf{z}\|^2\). Therefore \(\mathbf{A}^{\top}\mathbf{A}\mathbf{z}=\mathbf{0}\) implies \(\|\mathbf{A}\mathbf{z}\|^2=0\), hence \(\mathbf{A}\mathbf{z}=\mathbf{0}\). Conversely, if \(\mathbf{A}\mathbf{z}=\mathbf{0}\), then \(\mathbf{A}^{\top}\mathbf{A}\mathbf{z}=\mathbf{0}\). Thus the two homogeneous systems have exactly the same solutions. If the columns are independent, the only \(\mathbf{z}\) with \(\mathbf{A}\mathbf{z}=\mathbf{0}\) is \(\mathbf{0}\), so two solutions \(\mathbf{x}_1,\mathbf{x}_2\) of the normal equations must agree: their difference solves the homogeneous system. If the columns are dependent, there is a nonzero \(\mathbf{z}\) with \(\mathbf{A}\mathbf{z}=\mathbf{0}\); adding it to any normal-equation solution gives a different solution. This proves both directions. \(\square\)
Common mistake: solving selected rows of the original system instead. In the first example, the first two rows of \(\mathbf{A}\mathbf{x}=\mathbf{b}\) give \(x_1=1\) and \(x_2=2\). But this vector predicts \(\mathbf{A}\mathbf{x}=\begin{bmatrix}1\\2\\3\end{bmatrix}\), so its residual is \(\begin{bmatrix}0\\0\\-1\end{bmatrix}\). It does not satisfy the normal equations, since \(\mathbf{A}^{\top}\mathbf{r}=\begin{bmatrix}-1\\-1\end{bmatrix}\ne\mathbf{0}\). The correction is to form and solve the full normal system; the minimizing vector is \(\begin{bmatrix}\tfrac23\\\tfrac53\end{bmatrix}\), not the solution to an arbitrarily selected pair of equations.
Also avoid writing \((\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{A}^{\top}\mathbf{b}\) unless invertibility has been established. The dependent-column example has a singular normal matrix and still has least-squares solutions. Row reduction handles both unique and nonunique cases and makes the solution family visible.
Check Your Understanding
For each problem, form the normal equations before choosing a coefficient vector. Include a residual where requested.
- For \(\mathbf{A}=\begin{bmatrix}1\\1\\1\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}0\\1\\2\end{bmatrix}\), compute the normal equations and find the least-squares solution.
- For \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}2\\0\\1\end{bmatrix}\), find a minimizing coefficient vector and its residual.
- For \(\mathbf{A}=\begin{bmatrix}1&3\\0&0\end{bmatrix}\), identify the relation between the columns and explain why the normal matrix cannot be inverted.
- State the dimensions of \(\mathbf{A}^{\top}\mathbf{A}\) and \(\mathbf{A}^{\top}\mathbf{b}\) when \(\mathbf{A}\in\mathbb{R}^{m\times n}\).
- Explain why every solution of the normal equations is a least-squares solution, even if that solution is not unique.
