4.2 The Gram-Schmidt Process

1Reading¶

Material related to this page, as well as additional exercises, can be found in ALA 4.2.

2Learning Objectives¶

By the end of this page, you should know:

the Gram-Schmidt process for finding an orthogonal basis of a vector space

3The Gram-Schmidt Process¶

Hopefully we’ve convinced you that orthogonal bases are useful, so now the natural question becomes: how do I compute one? That’s where the famed Gram-Schmidt Process (GSP) comes into play.

The idea behind GSP is farily straightforward: given an initial basis for a vector space, iteratively modify until it is orthogonal. Let’s start with a simple concrete example, and then introduce the general algorithm:

Example 1 (Finding an orthogonal basis)

Let $W = \text{span}\{\vv{x_1}, \vv{x_2}\}$ , where $\vv{x_1} = \bm 3\\6\\0 \em$ and $\vv{x_2} = \bm 1\\2\\2 \em$ .

Since $\vv{x_1}$ and $\vv{x_2}$ are linearly independent (why?), they form a basis for the subspace $W \subseteq \mathbb{R}^3$ , where $\text{dim}(W) = 2$ .

However, $\vv{x_1}$ and $\vv{x_2}$ are not orthogonal because

\begin{align*} \langle \vv{x_1}, \vv{x_2}\rangle = 3(1) + 6(2) + 0(2) = 15. \end{align*}

(1)

Let’s use $\{\vv{v_1}, \vv{v_2} \}$ for our new basis, and set $\vv{v_1} = \vv{x_1}$ . We need to find a vector $\vv{v_2}$ that is orthogonal to $\vv{v_1}$ such that $\text{span}\{\vv{v_1}, \vv{v_2}\} = W$ .

Our idea here is to “extract out” the components of $x_2$ that are parallel to $\vv v_1$ and subtract them off of $\vv x_2$ , so that what’s left is orthogonal.

Let’s look at a picture first:

From this picture, we observe that we can write $\vv{x_2} = \vv p +\vv{v_2}$ where $\vv{p}$ is the component of $\vv{x_2}$ parallel with $\vv{x_1}$ and $\vv{v_2}$ is what’s left over, i.e., the part of $\vv{x_2}$ that is orthogonal to $\vv{x_1} = \vv{v_1}$ .

If $\vv p$ is parallel with $\vv{v_1}$ , then we must have that $\vv{p} = c\vv{v_1}$ for some constant $c$ , and therefore $\vv{v_2} = \vv{x_2} - \vv p = \vv{x_2} - c\vv{v_1}$ .

Now from our previous discussion, we know that $c = \frac{\langle \vv{x_2}, \vv{v_1}\rangle}{\|\vv{v_1}\|^2}$ (why?) but let’s see a different way of computing $c$ . We want $\langle \vv{v_2}, \vv{v_1} \rangle = 0$ , so we must have:

\begin{align*} \langle \vv{v_2}, \vv{v_1} \rangle = \langle \vv{x_2} - c\vv{v_1}, \vv{v_1}\rangle = \langle \vv{x_2}, \vv{v_1} \rangle - c\|\vv{v_1}\|^2 = 0 \end{align*}

(2)

or equivalently, $c = \frac{\langle \vv{x_2}, \vv{v_1}\rangle}{\|\vv{v_1}\|^2}$ . Therefore, $\vv{v_2} = \vv{x_2} - \frac{\langle \vv{x_2}, \vv{v_1} \rangle}{\|\vv{v_1}\|^2} \vv{v_1}$ .

By construction, we have that $\langle \vv{v_1}, \vv{v_2}\rangle = 0$ , and since $\vv{v_1} = \vv{x_1}$ and $\vv{v_2} = \vv{x_2} - c\vv{x_1}$ , both $\vv{v_1}, \vv{v_2} \in W$ . So $\vv{v_1}$ and $\vv{v_2}$ are linearly independent and contained in $W$ (a subspace of dimension 2), so form a basis for $W$ .

After actually plugging in our values of $\vv{x_1}$ and $\vv{x_2}$ , you can verify that

\begin{align*} \vv{v_1} = \bm 3\\6\\0 \em, \quad \vv{v_2} = \bm 0\\0\\2 \em \end{align*}

(3)

is an orthogonal basis for $\text{span}\left\{\bm 3\\6\\0 \em, \bm 1\\2\\2 \em\right\}$ .

The Gram-Schmidt process simply repeats this process over and over if there are more than two vectors, but the idea remains the same: at each step you subtract off the directions of the current vector that are parallel with previous ones.

Definition 1 (The Gram-Schmidt Process)

Given a basis $\{\vv{x_1}, ..., \vv{x_p}\}$ for a nonzero subspace $W$ of $\mathbb{R}^n$ , define

\begin{align*} \vv{v_1} &= \vv{x_1}\\ \vv{v_2} &= \vv{x_2} - \frac{\langle \vv{x_2}, \vv{v_1} \rangle}{\langle \vv{v_1}, \vv{v_1}\rangle} \vv{v_1}\\ \vv{v_3} &= \vv{x_3} - \frac{\langle \vv{x_3}, \vv{v_1} \rangle}{\langle \vv{v_1}, \vv{v_1}\rangle} \vv{v_1} - \frac{\langle \vv{x_3}, \vv{v_2} \rangle}{\langle \vv{v_2}, \vv{v_2}\rangle} \vv{v_2}\\ \vdots\\ \vv{v_p} &= \vv{x_p} - \frac{\langle \vv{x_p}, \vv{v_1} \rangle}{\langle \vv{v_1}, \vv{v_1}\rangle} \vv{v_1} - \frac{\langle \vv{x_p}, \vv{v_2} \rangle}{\langle \vv{v_2}, \vv{v_2}\rangle} \vv{v_2} - ... - \frac{\langle \vv{x_p}, \vv{v_{p-1}} \rangle}{\langle \vv{v_{p-1}}, \vv{v_{p-1}}\rangle} \vv{v_{p-1}} \end{align*}

(4)

Then $\{ \vv{v_1}, ..., \vv{v_p} \}$ is an orthogonal basis for $W$ . In addition

\begin{align*} \text{span} \left\{ \vv{v_1}, ..., \vv{v_k} \right\} = \text{span} \left\{ \vv{x_1}, ..., \vv{x_k} \right\} \quad\text{for $1 \leq k \leq p$}. \end{align*}

(5)

Exercise 1 (Finding an orthonormal basis for a subspace of

\mathbb{R}^4

)

A typical use case is to find an orthonormal basis, with respect to the standard dot product, for the subspace $W\subseteq \mathbb{R}^4$ consisting all vectors that are orthogonal to the vector $\vv a = (1, 2, -1, -3)$ .

Solution to Exercise 1

The first task is to find a basis for $W$ . A vector $\vv x = (x_1, x_2, x_3, x_4)$ is orthogonal to $\vv a$ if and only if

\begin{align*} \vv x \cdot \vv a = x_1 + 2x_2 - x_3 - 3x_4 = 0 \end{align*}

(7)

Solving this in the usual way (i.e., writing $x_1$ in terms of $x_2$ , $x_3$ , $x_4$ ), we observe that the free variables are $x_2, x_3, x_4$ , so that a (non-orthogonal) basis for the subspace is

\begin{align*} \vv{w_1} = \bm -2\\1\\0\\0\em, \quad \vv{w_2} = \bm 1\\0\\1\\0\em, \quad\vv{w_3} = \bm 3\\0\\0\\1\em \end{align*}

(8)

because

\begin{align*} \bm x_1 \\x_2\\x_3\\x_4\em = x_2 \bm -2\\1\\0\\0\em + x_3\bm 1\\0\\1\\0\em + x_4\bm 3\\0\\0\\1 \em \end{align*}

(9)

Now we apply Gram-Schmidt to obtain an orthogonal basis: first we set $\vv{v_1} = \vv{w_1}$ . To get $\vv{v_2}$ , we compute:

\begin{align*} \vv{v_2} = \vv{w_2} - \frac{\langle \vv{w_2}, \vv{v_1}\rangle}{\langle \vv{v_1}, \vv{v_1}\rangle} \vv{v_1} = \bm 1\\0\\1\\0 \em - \frac{-2}{5}\bm -2\\1\\0\\0 \em = \bm 1/5 \\ 2/5 \\ 1 \\ 0\em \end{align*}

(10)

Finally, we compute $\vv{v_3}$ :

\begin{align*} \vv{v_3} &= \vv{w_3} - \frac{\langle \vv{w_3} ,\vv{v_1}\rangle}{\langle \vv{v_1}, \vv{v_1}\rangle}\vv{v_1} - \frac{\langle \vv{w_3}, \vv{v_2}\rangle}{\langle \vv{v_2}, \vv{v_2}\rangle}\vv{v_2} \\ &= \bm 3\\0\\0\\1\em - \frac{-6}{5}\bm -2\\1\\0\\0 \em - \frac{3/5}{6/5} \bm 1/5\\2/5\\1\\0 \em\\ &= \bm 1/2\\1\\-1/2\\1 \em \end{align*}

(11)

To get our hands on an orthonormal basis, we simply normalize the $\vv{v_i}$ by dividing them by their norms. An orthonormal basis is given by $\vv{u_1}, \vv{u_2}, \vv{u_3}$ , where

\begin{align*} \vv{u_1} = \frac{\vv{v_1}}{\|\vv{v_1}\|} = \boxed{\frac{1}{\sqrt 5} \bm -2\\1\\0\\0\em}\\ \vv{u_2} = \frac{\vv{v_2}}{\|\vv{v_2}\|} = \boxed{\frac{1}{\sqrt{6/5}} \bm 1/5 \\ 2/5 \\ 1 \\ 0\em }\\ \vv{u_3} = \frac{\vv{v_3}}{\|\vv{v_3}\|} = \boxed{\frac{1}{\sqrt{5/2}} \bm 1/2\\1\\-1/2\\1\em } \end{align*}

(12)

3.1Python break!¶

In the following code, we demonstrate the Gram-Schmidt Process to obtain an orthogonal (and orthonormal) basis from a basis that is not orthogonal using a for loop in Python.

# The Gram Schmidt process

import numpy as np

x1 = np.array([-2, 1, 0, 0])
x2 = np.array([1, 0, 1, 0])
x3 = np.array([3, 0, 0, 1])

x = [x1, x2, x3] # basis that is not orthogonal
v = [x1] # initialize the basis that is orthogonal
u = [x1/np.linalg.norm(x1)] # initialize the basis that is orthogonal

for i in range(1, len(x)):
    v_i = x[i]
    for j in range(i):
        v_i = v_i - (np.dot(x[i], v[j])/np.dot(v[j], v[j]))*v[j]
    v.append(v_i)
    u.append(v_i/np.linalg.norm(v_i))

print("Orthogonal basis (not orthonormal): \n", v)
print("Orthonormal basis: \n", u)

Orthogonal basis (not orthonormal): 
 [array([-2,  1,  0,  0]), array([0.2, 0.4, 1. , 0. ]), array([ 0.5,  1. , -0.5,  1. ])]
Orthonormal basis: 
 [array([-0.89442719,  0.4472136 ,  0.        ,  0.        ]), array([0.18257419, 0.36514837, 0.91287093, 0.        ]), array([ 0.31622777,  0.63245553, -0.31622777,  0.63245553])]