What Full Column Rank Guarantees
In a least-squares problem, a vector \(\mathbf{b}\) may not be exactly equal to \(\mathbf{A}\mathbf{x}\) for any choice of coefficients \(\mathbf{x}\). We instead seek a vector \(\mathbf{x}\) that makes the residual \(\mathbf{b}-\mathbf{A}\mathbf{x}\) as short as possible. The column space determines which fitted vectors \(\mathbf{A}\mathbf{x}\) are available, while the columns also determine whether different coefficient vectors can produce the same fit. When the columns are linearly independent, the least-squares fit has a unique coefficient vector.
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 least-squares problem is to minimize \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^2\) over all \(\mathbf{x}\in\mathbb{R}^n\). The columns of \(\mathbf{A}\) are vectors in \(\mathbb{R}^m\).
Full column rank requires \(n\leq m\), since more than \(m\) vectors in \(\mathbb{R}^m\) cannot be linearly independent. It does not require that \(\mathbf{A}\mathbf{x}=\mathbf{b}\) have an exact solution. It concerns uniqueness of the coefficients that minimize the error, not whether the minimum error is zero.
The Gram Matrix Is Invertible
The matrix \(\mathbf{A}^{\top}\mathbf{A}\) is an \(n\times n\) matrix, regardless of the number \(m\) of rows of \(\mathbf{A}\). It is often called the Gram matrix of the columns. Its key property here follows directly from the definition of full column rank and the identity \(\mathbf{z}^{\top}\mathbf{z}=\|\mathbf{z}\|^2\).
Proof. Let \(\mathbf{z}\in\mathbb{R}^n\) be nonzero. Full column rank means that \(\mathbf{A}\mathbf{z}\ne\mathbf{0}\). Therefore \(\mathbf{z}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{z}=(\mathbf{A}\mathbf{z})^{\top}(\mathbf{A}\mathbf{z})=\|\mathbf{A}\mathbf{z}\|^2>0\). In particular, if \(\mathbf{A}^{\top}\mathbf{A}\mathbf{z}=\mathbf{0}\), then \(\|\mathbf{A}\mathbf{z}\|^2=\mathbf{z}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{z}=0\). A vector has squared norm zero only if it is the zero vector, so \(\mathbf{A}\mathbf{z}=\mathbf{0}\). Full column rank then gives \(\mathbf{z}=\mathbf{0}\). Thus the square matrix \(\mathbf{A}^{\top}\mathbf{A}\) has only the zero vector in its null space and is invertible by the Invertible Matrix Theorem. \(\square\)
The strict inequality in this proof is important: it rules out any nonzero coefficient change that leaves the Gram quadratic expression equal to zero. This positive quadratic expression is also why the Gram matrix is called positive definite. We will use its invertibility to turn the normal equations into a single coefficient vector.
From the Normal Equations to Uniqueness
The Normal Equations Characterization states that, for \(\mathbf{A}\in\mathbb{R}^{m\times n}\) and \(\mathbf{b}\in\mathbb{R}^m\), a vector \(\widehat{\mathbf{x}}\) is a least-squares minimizer if and only if \(\mathbf{A}^{\top}(\mathbf{A}\widehat{\mathbf{x}}-\mathbf{b})=\mathbf{0}\), or equivalently \(\mathbf{A}^{\top}\mathbf{A}\widehat{\mathbf{x}}=\mathbf{A}^{\top}\mathbf{b}\). This characterization was proved in the preceding material. A minimizer exists: by the Best Approximation Theorem, the projection of \(\mathbf{b}\) onto the column space of \(\mathbf{A}\) is a closest vector in that subspace, and it can be written as \(\mathbf{A}\mathbf{x}\) for some \(\mathbf{x}\in\mathbb{R}^n\).
Proof. The existence of a least-squares minimizer follows from the Best Approximation Theorem as stated above. For uniqueness, suppose \(\mathbf{x}_1\) and \(\mathbf{x}_2\) are both minimizers. By the Normal Equations Characterization, they satisfy \(\mathbf{A}^{\top}\mathbf{A}\mathbf{x}_1=\mathbf{A}^{\top}\mathbf{b}\) and \(\mathbf{A}^{\top}\mathbf{A}\mathbf{x}_2=\mathbf{A}^{\top}\mathbf{b}\). Subtracting gives \(\mathbf{A}^{\top}\mathbf{A}(\mathbf{x}_1-\mathbf{x}_2)=\mathbf{0}\). The matrix \(\mathbf{A}^{\top}\mathbf{A}\) is invertible by the preceding theorem, so \(\mathbf{x}_1-\mathbf{x}_2=\mathbf{0}\), and hence \(\mathbf{x}_1=\mathbf{x}_2\). Finally, the normal equations have the unique solution obtained by multiplying by \((\mathbf{A}^{\top}\mathbf{A})^{-1}\): \(\widehat{\mathbf{x}}=(\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{A}^{\top}\mathbf{b}\). The characterization says that this solution is a least-squares minimizer, and the argument just given says it is the only one. \(\square\)
Thus the formula does not come from assuming that the original system \(\mathbf{A}\mathbf{x}=\mathbf{b}\) is solvable. It solves the normal equations, whose solution is the unique coefficient vector for the best approximation, even when a nonzero residual remains.
Computing and Checking the Unique Minimizer
Worked Example: A Nonzero Least-Squares Residual
Find the least-squares minimizer for \(\mathbf{A}=\begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}1\\2\\2\end{bmatrix}\).
The columns are independent: if \(c_1\begin{bmatrix}1\\1\\1\end{bmatrix}+c_2\begin{bmatrix}0\\1\\2\end{bmatrix}=\mathbf{0}\), the first coordinate gives \(c_1=0\), and the second then gives \(c_2=0\). So \(\mathbf{A}\) has full column rank. Compute the two products in the normal equations:
The determinant of the Gram matrix is \(3\cdot5-3\cdot3=6\), and its inverse is \(\frac16\begin{bmatrix}5&-3\\-3&3\end{bmatrix}\). Therefore
Check: The fitted vector is \(\mathbf{A}\widehat{\mathbf{x}}=\begin{bmatrix}7/6\\5/3\\13/6\end{bmatrix}\), so the residual \(\mathbf{b}-\mathbf{A}\widehat{\mathbf{x}}=\begin{bmatrix}-1/6\\1/3\\-1/6\end{bmatrix}\). Its dot product with the first column is \(-1/6+1/3-1/6=0\); its dot product with the second is \(1/3+2(-1/6)=0\). Thus \(\mathbf{A}^{\top}(\mathbf{b}-\mathbf{A}\widehat{\mathbf{x}})=\mathbf{0}\), as required. The residual is not zero, so this example also shows that a unique minimizer need not give an exact solution.
Worked Example: Orthogonal Columns
Find the unique least-squares minimizer for \(\mathbf{A}=\begin{bmatrix}1&1\\1&-1\\1&0\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}3\\1\\2\end{bmatrix}\).
The columns are independent because a linear combination equal to zero has first two coordinates \(c_1+c_2=0\) and \(c_1-c_2=0\), which imply \(c_1=c_2=0\). Direct multiplication gives
The inverse of \(\mathbf{A}^{\top}\mathbf{A}\) is \(\begin{bmatrix}1/3&0\\0&1/2\end{bmatrix}\), so \(\widehat{\mathbf{x}}=\begin{bmatrix}1/3&0\\0&1/2\end{bmatrix}\begin{bmatrix}6\\2\end{bmatrix}=\begin{bmatrix}2\\1\end{bmatrix}\).
Check: Multiplication gives \(\mathbf{A}\widehat{\mathbf{x}}=\begin{bmatrix}2+1\\2-1\\2\end{bmatrix}=\begin{bmatrix}3\\1\\2\end{bmatrix}=\mathbf{b}\). The residual is \(\mathbf{0}\), so the normal equations hold. Here the least-squares solution is also an exact solution, and full column rank guarantees that there is no second coefficient vector producing the same exact fit.
Worked Example: A Fractional Minimizer
For \(\mathbf{A}=\begin{bmatrix}1&1\\1&0\\0&1\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}2\\0\\1\end{bmatrix}\), compute the unique minimizer and check the residual.
The columns are independent: the second coordinate of \(c_1\begin{bmatrix}1\\1\\0\end{bmatrix}+c_2\begin{bmatrix}1\\0\\1\end{bmatrix}=\mathbf{0}\) gives \(c_1=0\), and the third gives \(c_2=0\). The normal-equation matrices are
The Gram matrix has determinant \(2\cdot2-1\cdot1=3\), so its inverse is \(\frac13\begin{bmatrix}2&-1\\-1&2\end{bmatrix}\). Hence
Check: \(\mathbf{A}\widehat{\mathbf{x}}=\begin{bmatrix}5/3\\1/3\\4/3\end{bmatrix}\), so \(\mathbf{b}-\mathbf{A}\widehat{\mathbf{x}}=\begin{bmatrix}1/3\\-1/3\\-1/3\end{bmatrix}\). Dotting this residual with the first column gives \(1/3-1/3=0\), and dotting it with the second gives \(1/3-1/3=0\). The residual is orthogonal to both columns, verifying the normal equations and therefore the minimizing property.
Common Pitfall: Using the Wrong Product
The Gram matrix for the normal equations is \(\mathbf{A}^{\top}\mathbf{A}\), not \(\mathbf{A}\mathbf{A}^{\top}\). The order matters both for the dimensions and for the role of the unknown vector. For example, in the first worked example, \(\mathbf{A}\) is \(3\times2\), so \(\mathbf{A}^{\top}\mathbf{A}\) is \(2\times2\) and can multiply \(\mathbf{x}\in\mathbb{R}^2\). By contrast, \(\mathbf{A}\mathbf{A}^{\top}\) is \(3\times3\). The incorrect equation \(\mathbf{A}\mathbf{A}^{\top}\mathbf{x}=\mathbf{A}^{\top}\mathbf{b}\) is not even dimensionally defined: the left side attempts to multiply a \(3\times3\) matrix by a two-entry vector, while the right side has two entries.
Another error is to assume that full column rank makes the residual zero. The first example disproves that claim: its columns are independent and the minimizer is unique, but its residual is \(\begin{bmatrix}-1/6\\1/3\\-1/6\end{bmatrix}\ne\mathbf{0}\). Full column rank ensures invertibility of the Gram matrix and uniqueness of the minimizing coefficients. Exact solvability is a separate question about whether \(\mathbf{b}\) belongs to \(\operatorname{Col}\mathbf{A}\).
Why the Formula Is Useful
When the columns are independent, the normal equations reduce a least-squares problem to an ordinary square system with one solution. Each step has a specific role: \(\mathbf{A}^{\top}\mathbf{b}\) records how the data vector pairs with the columns, \(\mathbf{A}^{\top}\mathbf{A}\) records how the columns pair with one another, and invertibility ensures these pairings determine one coefficient vector. The formula is useful for reasoning and exact small examples. For larger computations, other methods can be preferable, but the uniqueness argument remains the same: independent columns make \(\mathbf{A}^{\top}\mathbf{A}\) invertible.
Check Your Understanding
Use the full-column-rank condition and the normal equations to justify each answer.
- Why does \(\mathbf{z}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{z}>0\) hold for every nonzero \(\mathbf{z}\) when \(\mathbf{A}\) has full column rank?
- For \(\mathbf{A}=\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}1\\2\\0\end{bmatrix}\), compute \(\mathbf{A}^{\top}\mathbf{A}\), \(\mathbf{A}^{\top}\mathbf{b}\), and the unique minimizer.
- If two vectors both satisfy the normal equations and \(\mathbf{A}\) has full column rank, why must they be equal?
- Does a unique least-squares minimizer imply \(\mathbf{A}\widehat{\mathbf{x}}=\mathbf{b}\)? Explain.
- For an \(m\times n\) matrix, what are the dimensions of \(\mathbf{A}^{\top}\mathbf{A}\) and \(\mathbf{A}\mathbf{A}^{\top}\), and which one appears in the normal equations for \(\mathbf{x}\)?
