Why Dependent Generators Need a Different Route
A matrix can list many vectors that generate the same subspace, even when some of those vectors add no new directions. The projection depends on the subspace, not on how many times its directions are listed. This matters computationally: the full-column-rank formula uses an inverse that may not exist when the listed columns are dependent. The reliable approach is to first retain a basis for the column space, then project using that independent set.
All vectors and matrices in this tutorial are real. For a matrix \(\mathbf{A}\in\mathbb{R}^{n\times p}\), its column space is \(\operatorname{Col}\mathbf{A}=\operatorname{span}\{\mathbf{a}_1,\dots,\mathbf{a}_p\}\), where \(\mathbf{a}_j\) are its columns. A list of columns is dependent if a nontrivial linear combination of them is \(\mathbf{0}\); a basis is an independent list that spans the subspace.
Thus, to compute the projection onto \(\operatorname{Col}\mathbf{A}\), we need a convenient basis for that column space. Row reduction identifies which original columns to keep. It is important to take those columns from \(\mathbf{A}\), not from its reduced form: row operations preserve linear relations among columns but generally change the actual column vectors.
Selecting a Basis from the Original Columns
Proof. Let \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\). There is an invertible matrix \(\mathbf{E}\) such that \(\mathbf{R}=\mathbf{E}\mathbf{A}\), because each elementary row operation is multiplication on the left by an invertible elementary matrix. Suppose the pivot-column indices are \(j_1,\dots,j_r\). The pivot columns of \(\mathbf{R}\) are linearly independent: each has a \(1\) in its own pivot row and \(0\) in the other pivot rows, so a linear combination of them equal to \(\mathbf{0}\) has every coefficient equal to \(0\). Since multiplication by the invertible \(\mathbf{E}\) preserves whether a combination equals \(\mathbf{0}\), the corresponding columns \(\mathbf{a}_{j_1},\dots,\mathbf{a}_{j_r}\) of \(\mathbf{A}\) are independent as well. Every nonpivot column of \(\mathbf{R}\) is a linear combination of its pivot columns: the coefficients are its entries in the pivot rows, since a pivot column has a \(1\) in its own pivot row and \(0\) in all the other pivot rows. Applying \(\mathbf{E}^{-1}\) to this relation shows that the corresponding nonpivot column of \(\mathbf{A}\) is the same combination of \(\mathbf{a}_{j_1},\dots,\mathbf{a}_{j_r}\). Hence the selected original columns are independent and span every column of \(\mathbf{A}\), so they form a basis for \(\operatorname{Col}\mathbf{A}\). \(\square\)
Worked Example: Find a Basis Among Four Generators
Find a basis for the column space of
Reduce \(\mathbf{A}\). First apply \(R_2\to R_2-R_1\), then \(R_3\to R_3-R_2\), using the new second row:
The pivot columns are columns 1 and 2. Therefore retain those columns from the original matrix, not from the reduced matrix:
Check: the third column of \(\mathbf{A}\) is \((1,2,1)^{\top}=\mathbf{a}_1+\mathbf{a}_2\), and the fourth is \((2,1,-1)^{\top}=2\mathbf{a}_1-\mathbf{a}_2\). Thus all columns lie in the span of the first two, which are independent by the pivot-column theorem.
Projecting with an Independent Basis Matrix
Suppose the retained basis vectors are the columns of \(\mathbf{B}\in\mathbb{R}^{n\times r}\). Since they are independent, \(\mathbf{B}\) has full column rank. The full-rank projection formula is
This works because \(\mathbf{B}^{\top}\mathbf{B}\) is invertible when the columns of \(\mathbf{B}\) are independent. The result is in \(\operatorname{Col}\mathbf{B}\), and its difference from \(\mathbf{x}\) is orthogonal to every column of \(\mathbf{B}\). The next result establishes these facts and explains why the same formula computes the projection onto the original, possibly rank-deficient, generator matrix's column space.
Proof. Because the columns of \(\mathbf{B}\) are independent, \(\mathbf{B}\mathbf{c}\ne\mathbf{0}\) whenever \(\mathbf{c}\ne\mathbf{0}\). For such \(\mathbf{c}\), \(\mathbf{c}^{\top}\mathbf{B}^{\top}\mathbf{B}\mathbf{c}=(\mathbf{B}\mathbf{c})^{\top}(\mathbf{B}\mathbf{c})=\|\mathbf{B}\mathbf{c}\|^2>0\). Thus \(\mathbf{B}^{\top}\mathbf{B}\) has zero null space and, being square, is invertible. Define \(\mathbf{y}=\mathbf{B}(\mathbf{B}^{\top}\mathbf{B})^{-1}\mathbf{B}^{\top}\mathbf{x}\). Its form shows \(\mathbf{y}\in\operatorname{Col}\mathbf{B}=\operatorname{Col}\mathbf{A}\). Also, \(\mathbf{B}^{\top}(\mathbf{x}-\mathbf{y})=\mathbf{B}^{\top}\mathbf{x}-\mathbf{B}^{\top}\mathbf{B}(\mathbf{B}^{\top}\mathbf{B})^{-1}\mathbf{B}^{\top}\mathbf{x}=\mathbf{0}\). So \(\mathbf{x}-\mathbf{y}\) is orthogonal to each column of \(\mathbf{B}\), and therefore to every linear combination of those columns. Hence \(\mathbf{x}-\mathbf{y}\in(\operatorname{Col}\mathbf{A})^\perp\). By uniqueness in the orthogonal decomposition theorem, \(\mathbf{y}\) is the projection. If \(\mathbf{Q}\) has orthonormal columns, then \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}\); substituting \(\mathbf{B}=\mathbf{Q}\) into the formula gives \(\mathbf{Q}(\mathbf{Q}^{\top}\mathbf{Q})^{-1}\mathbf{Q}^{\top}\mathbf{x}=\mathbf{Q}\mathbf{Q}^{\top}\mathbf{x}\). \(\square\)
Worked Example: Project Using the Retained Columns
Use the matrix \(\mathbf{A}\) from the first example and project \(\mathbf{x}=(1,0,2)^{\top}\) onto its column space. The retained basis matrix is \(\mathbf{B}=\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}\). First compute the Gram matrix and the vector of inner products:
The inverse is \(\frac13\begin{bmatrix}2&-1\\-1&2\end{bmatrix}\), as multiplication verifies:
The basis coordinates of the projection are
Consequently, \(\mathbf{y}=\mathbf{B}\begin{bmatrix}0\\1\end{bmatrix}=(0,1,1)^{\top}\). Check: the residual is \(\mathbf{x}-\mathbf{y}=(1,-1,1)^{\top}\), and its dot products with the two basis columns are \(1-1+0=0\) and \(0-1+1=0\). The answer is in the column space and the residual is orthogonal to it.
Using an Orthonormal Basis Instead
Another option is to orthonormalize a basis for the column space. If the resulting columns are \(\mathbf{q}_1,\dots,\mathbf{q}_r\), then the coefficient of \(\mathbf{q}_j\) in the projection is \(\mathbf{q}_j^{\top}\mathbf{x}\). Summing those components gives \(\sum_{j=1}^{r}(\mathbf{q}_j^{\top}\mathbf{x})\mathbf{q}_j\), or \(\mathbf{Q}\mathbf{Q}^{\top}\mathbf{x}\). The columns must be an orthonormal basis of the desired space; orthonormalizing a list that fails to span the entire column space would project onto only part of it.
Worked Example: Orthonormalize Dependent Generators and Project
Let the columns of \(\mathbf{A}\) be \(\mathbf{u}=(1,1,0)^{\top}\), \(\mathbf{v}=(1,0,1)^{\top}\), and \(\mathbf{u}+\mathbf{v}=(2,1,1)^{\top}\). The third column is dependent on the first two, so \(\mathbf{u},\mathbf{v}\) form a basis for the column space. Construct an orthonormal basis. First, \(\|\mathbf{u}\|=\sqrt{2}\), so \(\mathbf{q}_1=(1,1,0)^{\top}/\sqrt{2}\). Subtract from \(\mathbf{v}\) its component along \(\mathbf{q}_1\):
This vector has norm \(\sqrt{3/2}\), so after normalizing we obtain \(\mathbf{q}_2=(1,-1,2)^{\top}/\sqrt{6}\). Indeed, \(\mathbf{q}_1^{\top}\mathbf{q}_2=(1-1)/\sqrt{12}=0\), and both vectors have norm \(1\). For \(\mathbf{x}=(2,0,1)^{\top}\), the two coefficients are \(\mathbf{q}_1^{\top}\mathbf{x}=2/\sqrt{2}\) and \(\mathbf{q}_2^{\top}\mathbf{x}=4/\sqrt{6}\). Thus
Check: this answer is \(\frac13\mathbf{u}+\frac43\mathbf{v}\), so it lies in the column space. The residual is \((1/3,-1/3,-1/3)^{\top}\); its dot products with \(\mathbf{u}\) and \(\mathbf{v}\) are \(1/3-1/3=0\) and \(1/3-1/3=0\). Hence it is orthogonal to the whole space spanned by the generators.
Common Mistake: Inverting the Gram Matrix of All Generators
A tempting but invalid calculation is to apply \(\mathbf{A}(\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{A}^{\top}\mathbf{x}\) directly when \(\mathbf{A}\) has dependent columns. In the first example, the third column is the sum of the first two and the fourth is twice the first minus the second. Therefore \(\mathbf{A}\mathbf{c}=\mathbf{0}\) for a nonzero coefficient vector \(\mathbf{c}=(1,1,-1,0)^{\top}\). It follows that \(\mathbf{A}^{\top}\mathbf{A}\mathbf{c}=\mathbf{A}^{\top}\mathbf{0}=\mathbf{0}\), so \(\mathbf{A}^{\top}\mathbf{A}\) has a nonzero vector in its null space and cannot be inverted. Writing down its inverse is not a matter of simplifying a difficult expression; that inverse does not exist.
The correction is to select independent columns first, forming \(\mathbf{B}\), and then use \(\mathbf{B}(\mathbf{B}^{\top}\mathbf{B})^{-1}\mathbf{B}^{\top}\). Alternatively, orthonormalize a basis and use \(\mathbf{Q}\mathbf{Q}^{\top}\). Both routes represent the same projection onto the original column space because the selected basis spans exactly that space. Redundant columns affect the calculation's form, but not the subspace being projected onto.
Check Your Understanding
For each calculation, identify a basis for the generator space before deciding which projection formula applies.
- For columns \((1,0,1)^{\top},(2,0,2)^{\top},(0,1,1)^{\top}\), find pivot-column indices and state a basis for their column space.
- Explain why \(\mathbf{A}^{\top}\mathbf{A}\) is not invertible when the columns of \(\mathbf{A}\) are dependent.
- Let \(\mathbf{B}\) have independent columns. Write the full-column-rank formula for projecting \(\mathbf{x}\) onto \(\operatorname{Col}\mathbf{B}\), and state what property of the residual verifies the result.
- For the generators \((1,1,0)^{\top},(1,0,1)^{\top},(2,1,1)^{\top}\), verify the stated dependence and give the dimension of their span.
- If \(\mathbf{Q}\) has orthonormal columns spanning a subspace \(W\), write the projection of \(\mathbf{x}\) onto \(W\) and explain why the columns must span all of \(W\).
