The Gram-Schmidt process is a simple algorithm for producing an orthogonal or orthonormal basis for any nonzero subspace of \( \mathbb{R}^n \).
(I) The Gram-Schmidt Process
Example 1
Let \( W = \text{Span}\{\vec{x}_1, \vec{x}_2\} \), where:
\[ \vec{x}_1 = \begin{bmatrix} 2 \\ -5 \\ 1 \end{bmatrix} \quad \text{and} \quad \vec{x}_2 = \begin{bmatrix} 4 \\ -1 \\ 2 \end{bmatrix} \]
Construct an orthogonal basis \( \{\vec{v}_1, \vec{v}_2\} \) and then an orthonormal basis \( \{\vec{u}_1, \vec{u}_2\} \) for \( W \).
Solution:
Step 1: Set the first orthogonal basis vector equal to the first original vector.
\[ \vec{v}_1 = \vec{x}_1 = \begin{bmatrix} 2 \\ -5 \\ 1 \end{bmatrix} \]
Step 2: Decompose \( \vec{x}_2 = \text{Proj}_{\vec{v}_1} \vec{x}_2 + \vec{v}_2 \), where \( \vec{v}_2 \) is the component of \( \vec{x}_2 \) orthogonal to \( \vec{v}_1 \).
\[
\begin{aligned}
\vec{v}_2 &= \vec{x}_2 - \text{Proj}_{\vec{v}_1}\vec{x}_2 = \vec{x}_2 - \frac{\vec{x}_2 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 \\
&= \begin{bmatrix} 4 \\ -1 \\ 2 \end{bmatrix} - \frac{15}{30}\begin{bmatrix} 2 \\ -5 \\ 1 \end{bmatrix} \\
&= \begin{bmatrix} 4 \\ -1 \\ 2 \end{bmatrix} - \begin{bmatrix} 1 \\ -5/2 \\ 1/2 \end{bmatrix} = \begin{bmatrix} 3 \\ 3/2 \\ 3/2 \end{bmatrix}
\end{aligned}
\]
Check: \( \vec{v}_1 \cdot \vec{v}_2 = 2(3) + (-5)(3/2) + 1(3/2) = 6 - 15/2 + 3/2 = 0 \).
So, \( \{\vec{v}_1, \vec{v}_2\} \) is an orthogonal basis for \( W \).
(Optional): We can scale \( \vec{v}_2 \) to clear fractions. Multiplying by \( 2/3 \) gives \( \vec{v}_2' = \begin{bmatrix} 2 \\ 1 \\ 1 \end{bmatrix} \). Both are valid orthogonal bases.
Step 3: Normalize the vectors to get an orthonormal basis.
\[
\begin{aligned}
\vec{u}_1 &= \frac{\vec{v}_1}{||\vec{v}_1||} = \frac{1}{\sqrt{30}}\begin{bmatrix} 2 \\ -5 \\ 1 \end{bmatrix} = \begin{bmatrix} 2/\sqrt{30} \\ -5/\sqrt{30} \\ 1/\sqrt{30} \end{bmatrix} \\
\vec{u}_2 &= \frac{\vec{v}_2'}{||\vec{v}_2'||} = \frac{1}{\sqrt{6}}\begin{bmatrix} 2 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 2/\sqrt{6} \\ 1/\sqrt{6} \\ 1/\sqrt{6} \end{bmatrix}
\end{aligned}
\]
\( \{\vec{u}_1, \vec{u}_2\} \) is an orthonormal basis for \( W \).
Example 2
Find an orthogonal basis for the column space of the matrix:
\[ A = \begin{bmatrix} 3 & -5 & 1 \\ 1 & 1 & 1 \\ -1 & 5 & -2 \\ 3 & -7 & 8 \end{bmatrix} = \begin{bmatrix} \vec{x}_1 & \vec{x}_2 & \vec{x}_3 \end{bmatrix} \]
Solution:
By row reducing \( A \), we find a pivot in every column. Thus, the columns \( \vec{x}_1, \vec{x}_2, \vec{x}_3 \) form a basis for \( \text{Col } A \).
Step 1:
\[ \vec{v}_1 = \vec{x}_1 = \begin{bmatrix} 3 \\ 1 \\ -1 \\ 3 \end{bmatrix} \]
\( W_1 = \text{Span}\{\vec{x}_1\} = \text{Span}\{\vec{v}_1\} \).
Step 2: Find \( \vec{v}_2 \) in \( \text{Col } A \) that is orthogonal to \( W_1 \).
\[
\begin{aligned}
\vec{v}_2 &= \vec{x}_2 - \text{Proj}_{W_1}\vec{x}_2 = \vec{x}_2 - \frac{\vec{x}_2 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 \\
&= \begin{bmatrix} -5 \\ 1 \\ 5 \\ -7 \end{bmatrix} - \frac{-40}{20}\begin{bmatrix} 3 \\ 1 \\ -1 \\ 3 \end{bmatrix} = \begin{bmatrix} -5 \\ 1 \\ 5 \\ -7 \end{bmatrix} + 2\begin{bmatrix} 3 \\ 1 \\ -1 \\ 3 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 3 \\ -1 \end{bmatrix}
\end{aligned}
\]
Step 3: Find \( \vec{v}_3 \) in \( \text{Col } A \) that is orthogonal to \( W_2 = \text{Span}\{\vec{v}_1, \vec{v}_2\} \).
By Theorem 8 (Orthogonal Decomposition), the projection of \( \vec{x}_3 \) onto \( W_2 \) is the sum of its projections onto the orthogonal basis vectors \( \vec{v}_1 \) and \( \vec{v}_2 \).
\[
\begin{aligned}
\vec{v}_3 &= \vec{x}_3 - \text{Proj}_{W_2}\vec{x}_3 \\
&= \vec{x}_3 - \left( \frac{\vec{x}_3 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 + \frac{\vec{x}_3 \cdot \vec{v}_2}{\vec{v}_2 \cdot \vec{v}_2}\vec{v}_2 \right) \\
&= \begin{bmatrix} 1 \\ 1 \\ -2 \\ 8 \end{bmatrix} - \frac{30}{20}\begin{bmatrix} 3 \\ 1 \\ -1 \\ 3 \end{bmatrix} - \frac{-10}{20}\begin{bmatrix} 1 \\ 3 \\ 3 \\ -1 \end{bmatrix} \\
&= \begin{bmatrix} 1 \\ 1 \\ -2 \\ 8 \end{bmatrix} - \begin{bmatrix} 9/2 \\ 3/2 \\ -3/2 \\ 9/2 \end{bmatrix} + \begin{bmatrix} 1/2 \\ 3/2 \\ 3/2 \\ -1/2 \end{bmatrix} = \begin{bmatrix} -3 \\ 1 \\ 1 \\ 3 \end{bmatrix}
\end{aligned}
\]
The set \( \{\vec{v}_1, \vec{v}_2, \vec{v}_3\} \) is an orthogonal basis for \( \text{Col } A \).
Theorem 11 (The Gram-Schmidt Process)
Given a basis \( \{\vec{x}_1, \dots, \vec{x}_p\} \) for a nonzero subspace \( W \) of \( \mathbb{R}^n \), define:
\[
\begin{aligned}
\vec{v}_1 &= \vec{x}_1 \\
\vec{v}_2 &= \vec{x}_2 - \frac{\vec{x}_2 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 \\
\vec{v}_3 &= \vec{x}_3 - \frac{\vec{x}_3 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 - \frac{\vec{x}_3 \cdot \vec{v}_2}{\vec{v}_2 \cdot \vec{v}_2}\vec{v}_2 \\
&\vdots \\
\vec{v}_p &= \vec{x}_p - \frac{\vec{x}_p \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 - \dots - \frac{\vec{x}_p \cdot \vec{v}_{p-1}}{\vec{v}_{p-1} \cdot \vec{v}_{p-1}}\vec{v}_{p-1}
\end{aligned}
\]
Then \( \{\vec{v}_1, \dots, \vec{v}_p\} \) is an orthogonal basis for \( W \). In addition:
\[ \text{Span}\{\vec{v}_1, \dots, \vec{v}_k\} = \text{Span}\{\vec{x}_1, \dots, \vec{x}_k\} \quad \text{for } 1 \le k \le p \]
Theorem 11 shows that any nonzero subspace \( W \) of \( \mathbb{R}^n \) has an orthogonal basis.
(II) QR Factorization of Matrices
If an \( m \times n \) matrix \( A \) has linearly independent columns \( \vec{x}_1, \dots, \vec{x}_n \), then applying the Gram-Schmidt Process (with normalization) to \( \vec{x}_1, \dots, \vec{x}_n \) amounts to factoring \( A \) as described in the next theorem.
Theorem 12 (The QR Factorization)
If \( A \) is an \( m \times n \) matrix with linearly independent columns, then \( A \) can be factored as:
\[ A = QR \]
where \( Q \) is an \( m \times n \) matrix whose columns form an orthonormal basis for \( \text{Col } A \), and \( R \) is an \( n \times n \) upper triangular invertible matrix with positive entries on its diagonal.
Example 4
Find a QR factorization of \( A \) from Example 2.
Solution:
First, normalize the orthogonal basis vectors \( \vec{v}_1, \vec{v}_2, \vec{v}_3 \) to obtain the columns of \( Q \).
\[
||\vec{v}_1|| = \sqrt{20}, \quad ||\vec{v}_2|| = \sqrt{20}, \quad ||\vec{v}_3|| = \sqrt{20}
\]
\[
\begin{aligned}
\vec{u}_1 &= \frac{1}{\sqrt{20}}\begin{bmatrix} 3 \\ 1 \\ -1 \\ 3 \end{bmatrix}, \quad \vec{u}_2 = \frac{1}{\sqrt{20}}\begin{bmatrix} 1 \\ 3 \\ 3 \\ -1 \end{bmatrix}, \quad \vec{u}_3 = \frac{1}{\sqrt{20}}\begin{bmatrix} -3 \\ 1 \\ 1 \\ 3 \end{bmatrix}
\end{aligned}
\]
Construct \( Q \):
\[
Q = \begin{bmatrix} \vec{u}_1 & \vec{u}_2 & \vec{u}_3 \end{bmatrix} = \frac{1}{\sqrt{20}} \begin{bmatrix} 3 & 1 & -3 \\ 1 & 3 & 1 \\ -1 & 3 & 1 \\ 3 & -1 & 3 \end{bmatrix}
\]
Next, find \( R \). Note that \( A = QR \), and since \( Q \) has orthonormal columns, \( Q^T Q = I \). Multiplying both sides by \( Q^T \):
\[ Q^T A = Q^T (QR) = I R = R \implies R = Q^T A \]
\[
\begin{aligned}
R &= \frac{1}{\sqrt{20}} \begin{bmatrix} 3 & 1 & -1 & 3 \\ 1 & 3 & 3 & -1 \\ -3 & 1 & 1 & 3 \end{bmatrix} \begin{bmatrix} 3 & -5 & 1 \\ 1 & 1 & 1 \\ -1 & 5 & -2 \\ 3 & -7 & 8 \end{bmatrix} \\
&= \frac{1}{\sqrt{20}} \begin{bmatrix} 20 & -40 & 30 \\ 0 & 20 & -10 \\ 0 & 0 & 20 \end{bmatrix} \\
&= \begin{bmatrix} \sqrt{20} & -2\sqrt{20} & \frac{3}{2}\sqrt{20} \\ 0 & \sqrt{20} & -\frac{1}{2}\sqrt{20} \\ 0 & 0 & \sqrt{20} \end{bmatrix}
\end{aligned}
\]
Check: We can multiply \( Q \) and \( R \) back together to verify \( A = QR \).
Example 5
Find the distance from \( \vec{y} \) to the subspace \( W = \text{Span}\{\vec{u}_1, \vec{u}_2\} \), where:
\[ \vec{y} = \begin{bmatrix} -1 \\ -5 \\ 10 \end{bmatrix}, \quad \vec{u}_1 = \begin{bmatrix} -2 \\ 0 \\ 0 \end{bmatrix}, \quad \vec{u}_2 = \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} \]
Solution:
Note that \( \vec{u}_1 \cdot \vec{u}_2 = -2 \neq 0 \). The basis is not orthogonal! We need to produce an orthogonal basis for \( W \) first.
Apply Gram-Schmidt:
\[ \vec{v}_1 = \vec{u}_1 = \begin{bmatrix} -2 \\ 0 \\ 0 \end{bmatrix} \]
\[ \vec{v}_2 = \vec{u}_2 - \frac{\vec{u}_2 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 = \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} - \frac{-2}{4}\begin{bmatrix} -2 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} - \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 2 \\ -1 \end{bmatrix} \]
Check: \( \vec{v}_1 \cdot \vec{v}_2 = 0 \).
Now, calculate the orthogonal projection \( \hat{y} \) onto \( W \) using the orthogonal basis \( \{\vec{v}_1, \vec{v}_2\} \):
\[
\begin{aligned}
\hat{y} &= \frac{\vec{y} \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 + \frac{\vec{y} \cdot \vec{v}_2}{\vec{v}_2 \cdot \vec{v}_2}\vec{v}_2 \\
&= \frac{2}{4}\begin{bmatrix} -2 \\ 0 \\ 0 \end{bmatrix} + \frac{-20}{5}\begin{bmatrix} 0 \\ 2 \\ -1 \end{bmatrix} \\
&= \begin{bmatrix} -1 \\ 0 \\ 0 \end{bmatrix} - 4\begin{bmatrix} 0 \\ 2 \\ -1 \end{bmatrix} = \begin{bmatrix} -1 \\ -8 \\ 4 \end{bmatrix}
\end{aligned}
\]
Calculate the error vector \( \vec{z} \):
\[ \vec{z} = \vec{y} - \hat{y} = \begin{bmatrix} -1 \\ -5 \\ 10 \end{bmatrix} - \begin{bmatrix} -1 \\ -8 \\ 4 \end{bmatrix} = \begin{bmatrix} 0 \\ 3 \\ 6 \end{bmatrix} \]
Check: \( \vec{z} \cdot \vec{v}_1 = 0 \) and \( \vec{z} \cdot \vec{v}_2 = 0 \).
The distance from \( \vec{y} \) to \( W \) is the length of \( \vec{z} \):
\[ ||\vec{y} - \hat{y}|| = ||\vec{z}|| = \sqrt{0^2 + 3^2 + 6^2} = \sqrt{45} = 3\sqrt{5} \]