The Gram-Schmidt Process for Orthonormal Basis

The Gram-Schmidt process turns any basis of a subspace into an orthonormal basis by successively removing the projections of each new vector onto the ones already constructed.

Orthogonal basis: a set of vectors that are pairwise orthogonal. Orthonormal basis: an orthogonal basis in which every vector has norm \(1\).

The Gram-Schmidt Process and Formulas

The Gram-Schmidt process is used to produce an orthonormal basis for a subspace. Given a basis \[ A = \{ \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n \} \] for a subspace \( V \), the vectors \( \mathbf{y}_1, \mathbf{y}_2, \dots, \mathbf{y}_n \) defined by

\[ \begin{aligned} \mathbf{y}_1 &= \mathbf{v}_1 \\ \mathbf{y}_2 &= \mathbf{v}_2 - \frac{\mathbf{v}_2 \cdot \mathbf{y}_1}{\mathbf{y}_1 \cdot \mathbf{y}_1}\mathbf{y}_1 \\ \mathbf{y}_3 &= \mathbf{v}_3 - \frac{\mathbf{v}_3 \cdot \mathbf{y}_1}{\mathbf{y}_1 \cdot \mathbf{y}_1}\mathbf{y}_1 - \frac{\mathbf{v}_3 \cdot \mathbf{y}_2}{\mathbf{y}_2 \cdot \mathbf{y}_2}\mathbf{y}_2 \\ &\vdots \\ \mathbf{y}_n &= \mathbf{v}_n - \sum_{i=1}^{n-1} \frac{\mathbf{v}_n \cdot \mathbf{y}_i}{\mathbf{y}_i \cdot \mathbf{y}_i}\mathbf{y}_i \end{aligned} \]

form an orthogonal basis for the subspace \( V \), i.e.

\[ \operatorname{span}\{ \mathbf{v}_1, \dots, \mathbf{v}_n \} = \operatorname{span}\{ \mathbf{y}_1, \dots, \mathbf{y}_n \}. \]

The orthonormal basis \( Y_O \) is then obtained by dividing each vector in \( Y \) by its norm:

\[ Y_O = \left\{ \frac{\mathbf{y}_1}{\|\mathbf{y}_1\|}, \frac{\mathbf{y}_2}{\|\mathbf{y}_2\|}, \dots, \frac{\mathbf{y}_n}{\|\mathbf{y}_n\|} \right\}. \]

Key idea. At each step, subtract from \( \mathbf{v}_k \) its projections onto all previously constructed orthogonal vectors \( \mathbf{y}_1, \dots, \mathbf{y}_{k-1} \). The result is orthogonal to every one of them.

Examples with Solutions

Example 1 — Orthonormal Basis of a 2-D Subspace

Subspace \( V \) is defined by \( \operatorname{span}\{\mathbf{v}_1, \mathbf{v}_2\} \) where

\[ \mathbf{v}_1 = \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix}, \qquad \mathbf{v}_2 = \begin{bmatrix} -2 \\ -4 \\ -4 \end{bmatrix}. \]

Use the Gram-Schmidt process to determine an orthonormal basis \( Y_O \) for \( V \).

View Solution to Example 1

Let \( Y = \{ \mathbf{y}_1, \mathbf{y}_2 \} \) be the orthogonal basis to be constructed.

Step 1. Set \( \mathbf{y}_1 = \mathbf{v}_1 \):

\[ \mathbf{y}_1 = \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix}. \]

Step 2. Compute \( \mathbf{y}_2 = \mathbf{v}_2 - \dfrac{\mathbf{v}_2 \cdot \mathbf{y}_1}{\mathbf{y}_1 \cdot \mathbf{y}_1}\mathbf{y}_1 \).(see formulas above)

\[ \frac{\mathbf{v}_2 \cdot \mathbf{y}_1}{\mathbf{y}_1 \cdot \mathbf{y}_1} = \frac{(-2)(1) + (-4)(2) + (-4)(0)}{1^2 + 2^2 + 0^2} = \frac{-10}{5} = -2. \]

\[ \mathbf{y}_2 = \begin{bmatrix} -2 \\ -4 \\ -4 \end{bmatrix} - (-2)\begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ -4 \end{bmatrix}. \]

Hence \( Y = \left\{ \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ -4 \end{bmatrix} \right\} \).

Step 3. Normalize each vector: \( \|\mathbf{y}_1\| = \sqrt{5} \) and \( \|\mathbf{y}_2\| = 4 \), so

\[ Y_O = \left\{ \frac{1}{\sqrt{5}}\begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix}, \frac{1}{4}\begin{bmatrix} 0 \\ 0 \\ -4 \end{bmatrix} \right\}. \]

Verification. \(\mathbf{y}_1 \cdot \mathbf{y}_2 = 1(0) + 2(0) + 0(-4) = 0\), so the two vectors are orthogonal. Both are unit vectors after normalization. Hence \(Y_O\) is an orthonormal basis for \(V\).

Example 2 — Orthonormal Basis of a 4-D Subspace in \( \mathbb{R}^5 \)

Subspace \( V \) is defined by \( \operatorname{span}\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, \mathbf{v}_4\} \), where

\[ \mathbf{v}_1 = \begin{bmatrix} -1 \\ -1 \\ 2 \\ 2 \\ 3 \end{bmatrix}, \quad \mathbf{v}_2 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \end{bmatrix}, \quad \mathbf{v}_3 = \begin{bmatrix} 0 \\ 0 \\ -1 \\ -1 \\ 0 \end{bmatrix}, \quad \mathbf{v}_4 = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 1 \end{bmatrix}. \]

Use the Gram-Schmidt process to determine an orthonormal basis \( Y_O \) for \( V \).

View Solution to Example 2

Let \( Y = \{ \mathbf{y}_1, \mathbf{y}_2, \mathbf{y}_3, \mathbf{y}_4 \} \) be the orthogonal basis.

Step 1. \( \mathbf{y}_1 = \mathbf{v}_1 = \begin{bmatrix} -1 \\ -1 \\ 2 \\ 2 \\ 3 \end{bmatrix} \).

Step 2. Compute \( \mathbf{y}_2 \) from \( \mathbf{v}_2 \) (see formulas above):

\[ \frac{\mathbf{v}_2 \cdot \mathbf{y}_1}{\mathbf{y}_1 \cdot \mathbf{y}_1} = \frac{(1)(-1) + (1)(-1) + (1)(2) + (1)(2) + 0}{1 + 1 + 4 + 4 + 9} = \frac{2}{19}. \]

\[ \mathbf{y}_2 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \end{bmatrix} - \frac{2}{19}\begin{bmatrix} -1 \\ -1 \\ 2 \\ 2 \\ 3 \end{bmatrix} = \begin{bmatrix} 21/19 \\ 21/19 \\ 15/19 \\ 15/19 \\ -6/19 \end{bmatrix}. \]

Multiplying by a nonzero scalar does not change orthogonality, so choose \( \mathbf{y}_2' = \tfrac{19}{3}\mathbf{y}_2 = \begin{bmatrix} 7 \\ 7 \\ 5 \\ 5 \\ -2 \end{bmatrix} \).

Step 3. Compute \( \mathbf{y}_3 \) from \( \mathbf{v}_3 \), using \( \mathbf{y}_1 \) and \( \mathbf{y}_2' \) (see formulas above):

\[ \frac{\mathbf{v}_3 \cdot \mathbf{y}_1}{\mathbf{y}_1 \cdot \mathbf{y}_1} = \frac{-4}{19}, \qquad \frac{\mathbf{v}_3 \cdot \mathbf{y}_2'}{\mathbf{y}_2' \cdot \mathbf{y}_2'} = \frac{-10}{152}. \]

\[ \mathbf{y}_3 = \begin{bmatrix} 0 \\ 0 \\ -1 \\ -1 \\ 0 \end{bmatrix} - \frac{-4}{19}\begin{bmatrix} -1 \\ -1 \\ 2 \\ 2 \\ 3 \end{bmatrix} - \frac{-10}{152}\begin{bmatrix} 7 \\ 7 \\ 5 \\ 5 \\ -2 \end{bmatrix} = \begin{bmatrix} 1/4 \\ 1/4 \\ -1/4 \\ -1/4 \\ 1/2 \end{bmatrix}. \]

Choose \( \mathbf{y}_3' = 4\mathbf{y}_3 = \begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \\ 2 \end{bmatrix} \).

Step 4. Compute \( \mathbf{y}_4 \) from \( \mathbf{v}_4 \) (see formulas above):

\[ \frac{\mathbf{v}_4 \cdot \mathbf{y}_1}{\mathbf{y}_1 \cdot \mathbf{y}_1} = \frac{5}{19}, \qquad \frac{\mathbf{v}_4 \cdot \mathbf{y}_2'}{\mathbf{y}_2' \cdot \mathbf{y}_2'} = \frac{3}{152}, \qquad \frac{\mathbf{v}_4 \cdot \mathbf{y}_3'}{\mathbf{y}_3' \cdot \mathbf{y}_3'} = \frac{1}{8}. \]

\[ \mathbf{y}_4 = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 1 \end{bmatrix} - \frac{5}{19}\begin{bmatrix} -1 \\ -1 \\ 2 \\ 2 \\ 3 \end{bmatrix} - \frac{3}{152}\begin{bmatrix} 7 \\ 7 \\ 5 \\ 5 \\ -2 \end{bmatrix} - \frac{1}{8}\begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \\ 2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ -1/2 \\ 1/2 \\ 0 \end{bmatrix}. \]

Choose \( \mathbf{y}_4' = 2\mathbf{y}_4 = \begin{bmatrix} 0 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} \).

Orthogonal basis:

\[ Y = \left\{ \begin{bmatrix} -1 \\ -1 \\ 2 \\ 2 \\ 3 \end{bmatrix}, \begin{bmatrix} 7 \\ 7 \\ 5 \\ 5 \\ -2 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \\ 2 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} \right\}. \]

Orthonormal basis:

\[ Y_O = \left\{ \frac{1}{\sqrt{19}}\begin{bmatrix} -1 \\ -1 \\ 2 \\ 2 \\ 3 \end{bmatrix}, \frac{1}{2\sqrt{38}}\begin{bmatrix} 7 \\ 7 \\ 5 \\ 5 \\ -2 \end{bmatrix}, \frac{1}{2\sqrt{2}}\begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \\ 2 \end{bmatrix}, \frac{1}{\sqrt{2}}\begin{bmatrix} 0 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} \right\}. \]

Why \(Y\) spans the same subspace as \(V\). The vectors \(\mathbf{y}_1, \mathbf{y}_2', \mathbf{y}_3', \mathbf{y}_4'\) are linear combinations of \(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, \mathbf{v}_4\): \[ \begin{aligned} \mathbf{y}_1 &= \mathbf{v}_1, \\ \mathbf{y}_2' &= -\tfrac{2}{3}\mathbf{v}_1 + \tfrac{19}{3}\mathbf{v}_2, \\ \mathbf{y}_3' &= \tfrac{2}{3}\mathbf{v}_1 + \tfrac{5}{3}\mathbf{v}_2 + 4\mathbf{v}_3, \\ \mathbf{y}_4' &= -\tfrac{2}{3}\mathbf{v}_1 - \tfrac{2}{3}\mathbf{v}_2 - \mathbf{v}_3 + 2\mathbf{v}_4. \end{aligned} \] Therefore \( \operatorname{span}\{V\} = \operatorname{span}\{Y\} \).

More References and Links

  1. Vector Spaces – Questions with Solutions
  2. Orthonormal Basis
  3. Linear Algebra and its Applications – 5th Edition – David C. Lay, Steven R. Lay, Judi J. McDonald
  4. Elementary Linear Algebra – 7th Edition – Howard Anton and Chris Rorres
  5. Introduction to Linear Algebra – Fifth Edition (2016) – Gilbert Strang
  6. Linear Algebra Done Right – Third Edition (2015) – Sheldon Axler
  7. Linear Algebra with Applications (2012) – Gareth Williams