Gram-Schmidt Process and QR Factorization

The Gram-Schmidt process systematically converts any basis into an orthonormal basis. This algorithm is foundational for numerical linear algebra and leads to the QR factorization.

DefinitionGram-Schmidt Process

Given a basis $\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\}$ for inner product space $V$ , construct an orthonormal basis $\{\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_n\}$ :

Step 1: Normalize the first vector: $\mathbf{e}_1 = \frac{\mathbf{v}_1}{\|\mathbf{v}_1\|}$

Step k (for $k = 2, \ldots, n$ ): Subtract projections onto previous vectors, then normalize: $\mathbf{u}_k = \mathbf{v}_k - \sum_{i=1}^{k-1} \langle \mathbf{v}_k, \mathbf{e}_i \rangle \mathbf{e}_i$ $\mathbf{e}_k = \frac{\mathbf{u}_k}{\|\mathbf{u}_k\|}$

ExampleGram-Schmidt Application

Orthonormalize $\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$ where: $\mathbf{v}_1 = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}, \quad \mathbf{v}_2 = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}, \quad \mathbf{v}_3 = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}$

Step 1: $\mathbf{e}_1 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}$

Step 2: $\mathbf{u}_2 = \mathbf{v}_2 - \langle \mathbf{v}_2, \mathbf{e}_1 \rangle \mathbf{e}_1 = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} - \frac{1}{2}\begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1/2 \\ -1/2 \\ 1 \end{pmatrix}$

Then $\mathbf{e}_2 = \frac{\mathbf{u}_2}{\|\mathbf{u}_2\|} = \frac{1}{\sqrt{6}}\begin{pmatrix} 1 \\ -1 \\ 2 \end{pmatrix}$

Step 3: Compute $\mathbf{u}_3$ similarly, then normalize.

DefinitionOrthogonal Projection

The orthogonal projection of vector $\mathbf{v}$ onto subspace $W$ with orthonormal basis $\{\mathbf{e}_1, \ldots, \mathbf{e}_k\}$ is: $\text{proj}_W(\mathbf{v}) = \sum_{i=1}^k \langle \mathbf{v}, \mathbf{e}_i \rangle \mathbf{e}_i$

This is the closest point in $W$ to $\mathbf{v}$ : it minimizes $\|\mathbf{v} - \mathbf{w}\|$ over all $\mathbf{w} \in W$ .

TheoremQR Factorization

Any $m \times n$ matrix $A$ with linearly independent columns can be factored as: $A = QR$

where $Q$ is $m \times n$ with orthonormal columns, and $R$ is $n \times n$ upper triangular with positive diagonal entries.

The Gram-Schmidt process applied to the columns of $A$ produces $Q$ , and $R$ records the coefficients.

ExampleQR Decomposition

For $A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}$ with columns $\mathbf{v}_1, \mathbf{v}_2$ :

Gram-Schmidt gives: $Q = \begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{6} \\ 1/\sqrt{2} & -1/\sqrt{6} \\ 0 & 2/\sqrt{6} \end{bmatrix}, \quad R = \begin{bmatrix} \sqrt{2} & 1/\sqrt{2} \\ 0 & \sqrt{3/2} \end{bmatrix}$

Remark

The Gram-Schmidt process, though conceptually simple, can be numerically unstable due to rounding errors. Modified Gram-Schmidt and Householder reflections are preferred for computation. The QR factorization is crucial for solving least squares problems and computing eigenvalues via the QR algorithm.