From a Residual to Equations for a Candidate Fit
For an overdetermined system, a matrix equation \(\mathbf{A}\mathbf{x}=\mathbf{b}\) has more equations than unknowns. It may have no exact solution, so we instead seek a vector \(\mathbf{x}\) whose fitted vector \(\mathbf{A}\mathbf{x}\) approximates \(\mathbf{b}\). The residual is the difference between the data vector and the fitted vector. For a least-squares fit, residual orthogonality gives a useful condition: the residual must be orthogonal to every column of \(\mathbf{A}\). This tutorial translates that geometric condition into a system of equations for a candidate fit.
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), where \(m>n\), and let \(\mathbf{b}\in\mathbb{R}^m\). Write the columns of \(\mathbf{A}\) as \(\mathbf{a}_1,\ldots,\mathbf{a}_n\), and let \(\mathbf{x}=(x_1,\ldots,x_n)^{\top}\in\mathbb{R}^n\). The fitted vector is \(\mathbf{A}\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\), which lies in the column space of \(\mathbf{A}\).
The columns are vectors in \(\mathbb{R}^m\), so each orthogonality condition is a dot product in \(\mathbb{R}^m\). There is one such condition for each unknown coefficient \(x_j\). The goal is to collect all \(n\) scalar conditions into a single matrix equation.
Collecting the Orthogonality Conditions
Proof. The \(j\)th entry of \(\mathbf{A}^{\top}\mathbf{r}\) is the dot product of the \(j\)th column of \(\mathbf{A}\) with \(\mathbf{r}\), so \((\mathbf{A}^{\top}\mathbf{r})_j=\mathbf{a}_j^{\top}\mathbf{r}\). If \(\mathbf{r}\) is orthogonal to every column, every entry of \(\mathbf{A}^{\top}\mathbf{r}\) is zero, and thus \(\mathbf{A}^{\top}\mathbf{r}=\mathbf{0}\). Conversely, if \(\mathbf{A}^{\top}\mathbf{r}=\mathbf{0}\), each of its entries is zero, so \(\mathbf{a}_j^{\top}\mathbf{r}=0\) for every \(j\). This is exactly orthogonality to every column. \(\square\)
For a candidate coefficient vector \(\mathbf{x}\), substitute its residual \(\mathbf{r}=\mathbf{b}-\mathbf{A}\mathbf{x}\) into this result. The requirement becomes \(\mathbf{A}^{\top}(\mathbf{b}-\mathbf{A}\mathbf{x})=\mathbf{0}\). Distributing \(\mathbf{A}^{\top}\) and moving the term involving \(\mathbf{x}\) to the other side gives the normal equations.
Proof. By the theorem, residual orthogonality is equivalent to \(\mathbf{A}^{\top}(\mathbf{b}-\mathbf{A}\mathbf{x})=\mathbf{0}\). Distributing the product gives \(\mathbf{A}^{\top}\mathbf{b}-\mathbf{A}^{\top}\mathbf{A}\mathbf{x}=\mathbf{0}\), which is equivalent, after adding \(\mathbf{A}^{\top}\mathbf{A}\mathbf{x}\) to both sides, to \(\mathbf{A}^{\top}\mathbf{A}\mathbf{x}=\mathbf{A}^{\top}\mathbf{b}\). Reversing these algebraic steps proves the converse as well. \(\square\)
The dimensions help keep the equation oriented correctly. The product \(\mathbf{A}^{\top}\mathbf{A}\) is \(n\times n\), \(\mathbf{x}\) has \(n\) entries, and \(\mathbf{A}^{\top}\mathbf{b}\) has \(n\) entries. The resulting system has \(n\) equations in \(n\) unknowns, even though the original system has \(m>n\) equations. This change in shape does not by itself guarantee a unique solution; the columns of \(\mathbf{A}\) may be dependent.
Forming and Checking the Equations
Worked Example: Two Columns and Three Observations
For the overdetermined system below, form the normal equations, find a candidate coefficient vector, and check its residual for orthogonality.
The columns are \(\mathbf{a}_1=(1,1,1)^{\top}\) and \(\mathbf{a}_2=(0,1,2)^{\top}\). Their dot products give the entries of \(\mathbf{A}^{\top}\mathbf{A}\): \(\mathbf{a}_1^{\top}\mathbf{a}_1=1+1+1=3\), \(\mathbf{a}_1^{\top}\mathbf{a}_2=0+1+2=3\), and \(\mathbf{a}_2^{\top}\mathbf{a}_2=0+1+4=5\). The entries of \(\mathbf{A}^{\top}\mathbf{b}\) are \(\mathbf{a}_1^{\top}\mathbf{b}=1+2+2=5\) and \(\mathbf{a}_2^{\top}\mathbf{b}=0+2+4=6\). Hence
Subtract the first scalar equation from the second to obtain \(2x_2=1\), so \(x_2=\tfrac12\). Substitution into \(3x_1+3x_2=5\) gives \(3x_1+\tfrac32=5\), hence \(3x_1=\tfrac72\) and \(x_1=\tfrac76\). The candidate is \(\mathbf{x}=(\tfrac76,\tfrac12)^{\top}\).
Check the equations: multiplying gives \(3(\tfrac76)+3(\tfrac12)=\tfrac72+\tfrac32=5\) and \(3(\tfrac76)+5(\tfrac12)=\tfrac72+\tfrac52=6\). The residual is
Its dot products with the columns are \(\mathbf{a}_1^{\top}\mathbf{r}=-\tfrac16+\tfrac13-\tfrac16=0\) and \(\mathbf{a}_2^{\top}\mathbf{r}=0+\tfrac13+2(-\tfrac16)=0\). Thus the residual has the required orthogonality.
This calculation illustrates a reliable order of work: compute the column dot products to build the two sides, solve for \(\mathbf{x}\), then calculate \(\mathbf{b}-\mathbf{A}\mathbf{x}\) and check its dot products. Checking the residual directly is valuable because it tests the geometric condition itself, not just an earlier line of algebra.
Worked Example: A Candidate with Integer Entries
Form and solve the normal equations for the following matrix and vector, then verify the residual.
The columns are \(\mathbf{a}_1=(1,0,1,0)^{\top}\) and \(\mathbf{a}_2=(0,1,1,1)^{\top}\). Therefore \(\mathbf{a}_1^{\top}\mathbf{a}_1=1+0+1+0=2\), \(\mathbf{a}_1^{\top}\mathbf{a}_2=0+0+1+0=1\), and \(\mathbf{a}_2^{\top}\mathbf{a}_2=0+1+1+1=3\). Also, \(\mathbf{a}_1^{\top}\mathbf{b}=2+0+4+0=6\) and \(\mathbf{a}_2^{\top}\mathbf{b}=0+1+4+3=8\). The equations are
From the first equation \(x_2=6-2x_1\). Substitute this into the second: \(x_1+3(6-2x_1)=8\), so \(x_1+18-6x_1=8\), \(-5x_1=-10\), and \(x_1=2\). Then \(x_2=6-2(2)=2\). Thus \(\mathbf{x}=(2,2)^{\top}\).
Check: \(\mathbf{A}\mathbf{x}=(2,2,4,2)^{\top}\), so \(\mathbf{r}=(0,-1,0,1)^{\top}\). The column dot products are \(\mathbf{a}_1^{\top}\mathbf{r}=0+0+0+0=0\) and \(\mathbf{a}_2^{\top}\mathbf{r}=0-1+0+1=0\). The residual is orthogonal to both columns.
Dependent Columns Still Give Normal Equations
The normal equations can be formed without assuming that the columns of \(\mathbf{A}\) are independent. When they are dependent, the equations may themselves be dependent, and solving them may not specify a unique coefficient vector. The dot-product derivation still applies: every candidate satisfying the normal equations has a residual orthogonal to each column, by the proposition. The next example demonstrates the distinction between forming the equations and claiming that they determine one answer.
Worked Example: Dependent Columns
Form the normal equations for this overdetermined system and check one candidate that satisfies them.
The columns are \(\mathbf{a}_1=(1,0,1)^{\top}\) and \(\mathbf{a}_2=(2,0,2)^{\top}\). Their dot products are \(\mathbf{a}_1^{\top}\mathbf{a}_1=1+0+1=2\), \(\mathbf{a}_1^{\top}\mathbf{a}_2=2+0+2=4\), and \(\mathbf{a}_2^{\top}\mathbf{a}_2=4+0+4=8\). The right-hand entries are \(\mathbf{a}_1^{\top}\mathbf{b}=1+0+3=4\) and \(\mathbf{a}_2^{\top}\mathbf{b}=2+0+6=8\). Thus the normal equations are
For a particular candidate, take \(\mathbf{x}=(2,0)^{\top}\). The left sides are \(2(2)+4(0)=4\) and \(4(2)+8(0)=8\), so both equations hold. Its fitted vector is \(\mathbf{A}\mathbf{x}=(2,0,2)^{\top}\), and its residual is \(\mathbf{r}=(-1,1,1)^{\top}\). Then \(\mathbf{a}_1^{\top}\mathbf{r}=-1+0+1=0\) and \(\mathbf{a}_2^{\top}\mathbf{r}=-2+0+2=0\). This confirms orthogonality for the chosen candidate; the displayed equations also show why one must not assume that every normal-equation system has independent equations.
Common Mistake: Using the Wrong Sign
A frequent error is to rearrange the residual equation and place a minus sign on the right-hand side. With the convention \(\mathbf{r}=\mathbf{b}-\mathbf{A}\mathbf{x}\), the orthogonality condition is \(\mathbf{A}^{\top}(\mathbf{b}-\mathbf{A}\mathbf{x})=\mathbf{0}\). Expanding gives \(\mathbf{A}^{\top}\mathbf{b}-\mathbf{A}^{\top}\mathbf{A}\mathbf{x}=\mathbf{0}\); moving the second term to the other side yields \(\mathbf{A}^{\top}\mathbf{A}\mathbf{x}=\mathbf{A}^{\top}\mathbf{b}\), with a positive right-hand side.
For the first worked example, the mistaken equation \(\mathbf{A}^{\top}\mathbf{A}\mathbf{x}=-\mathbf{A}^{\top}\mathbf{b}\) would require \(\begin{bmatrix}3&3\\3&5\end{bmatrix}\mathbf{x}=\begin{bmatrix}-5\\-6\end{bmatrix}\). The candidate \((\tfrac76,\tfrac12)^{\top}\) does not satisfy it: the left side is \((5,6)^{\top}\), not \((-5,-6)^{\top}\). The residual check catches the error too: the correctly derived candidate has zero dot product with each column, while changing the sign of the right-hand side does not preserve those normal equations.
Keep the definitions and dimensions visible when setting up a problem: \(\mathbf{x}\) is an \(n\)-entry coefficient vector, \(\mathbf{r}\) is an \(m\)-entry residual, and \(\mathbf{A}^{\top}\mathbf{r}\) records exactly the \(n\) dot products with the columns. This makes the normal equations a direct translation of residual orthogonality rather than a formula to memorize without its source.
Check Your Understanding
For each question, use the residual definition \(\mathbf{r}=\mathbf{b}-\mathbf{A}\mathbf{x}\) and justify the matrix dimensions in your work.
- Explain why the \(j\)th entry of \(\mathbf{A}^{\top}\mathbf{r}\) is the dot product of the \(j\)th column of \(\mathbf{A}\) with \(\mathbf{r}\).
- For \(\mathbf{A}=\begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix}\) and \(\mathbf{b}=(1,2,2)^{\top}\), write the two normal equations before solving them.
- For \(\mathbf{A}=\begin{bmatrix}1\\0\\1\end{bmatrix}\) and \(\mathbf{b}=(2,1,4)^{\top}\), form the single normal equation and check the residual for its solution.
- Show algebraically that \(\mathbf{A}^{\top}(\mathbf{b}-\mathbf{A}\mathbf{x})=\mathbf{0}\) is equivalent to \(\mathbf{A}^{\top}\mathbf{A}\mathbf{x}=\mathbf{A}^{\top}\mathbf{b}\).
- Why does the derivation of the normal equations not require the columns of \(\mathbf{A}\) to be independent?
