Gram-Schmidt Orthogonalization

In Orthogonality and Projections we said that a set \(\{ \vec {f}_1, \vec {f}_2, \dots , \vec {f}_m\}\) of nonzero vectors in \(\RR ^n\) is called an orthogonal set if \(\vec {f}_i \dotp \vec {f}_j =0\) for all \(i \neq j\). In this section we will prove that every orthogonal set is linearly independent, and therefore it is a basis for its span. We have already seen that the expansion of a vector as a linear combination of orthogonal basis vectors is easy to obtain because formulas exist for the coefficients. Hence the orthogonal bases are the “nice” bases. Our next task is to show that every subspace of \(\RR ^n\) has an orthogonal basis. We will start with intuitive explorations in lower dimensions, then proceed to formalize our results for subspaces of \(\RR ^n\).

A Visual Guide to Creating an Orthogonal Basis

Given an arbitrary basis \(\{\vec {v}_1, \vec {v}_2\}\) of \(\RR ^2\), let’s start building our orthogonal basis, \(\{\vec {f}_1, \vec {f}_2\}\), by setting \(\vec {f}_1 = \vec {v}_1\). To find the next element of our orthogonal basis, consider the orthogonal projection of \(\vec {v}_2\) onto \(\vec {f}_1\). (See the figure below.)

[Picture] [Picture]

Next, let \(\vec {f}_2=\vec {v}_2-\mbox {proj}_{\vec {f}_1}\vec {v}_2\). Observe that \(\vec {f}_2\) is orthogonal to \(\vec {f}_1\) (See Theorem ?? of Orthogonality and Projections). This gives us an orthogonal collection \(\mathcal {B}=\{\vec {f}_1,\vec {f}_2\}\). It is intuitively clear that \(\vec {f}_1\) and \(\vec {f}_2\) are linearly independent. Therefore \(\mathcal {B}\) is an orthogonal basis of \(\RR ^2\).

The following exploration illustrates this process dynamically.

Choose an arbitrary basis \(\{\vec {v}_1, \vec {v}_2\}\) of \(\RR ^2\) by dragging the tips of vectors \(\vec {v}_1\) and \(\vec {v}_2\) to desired positions. Use the navigation bar at the bottom of the interactive window to go through the steps of constructing an orthogonal basis of \(\RR ^2\).

We can apply this process to any two-dimensional subset of \(\RR ^n\). The following exploration will guide you through the process of constructing an orthogonal basis for a plane spanned by two arbitrary vectors in \(\RR ^3\).

Let \(W =\mbox {span}\left ({\bf v}_1,{\bf v}_2\right )\). \(W\) is a plane through the origin in \(\RR ^3\). Use the navigation bar at the bottom of the interactive window to go through the steps of constructing an orthogonal basis for \(W\). RIGHT-CLICK and DRAG to rotate the image for a better view.

In the next exploration, we take the process of constructing an orthogonal basis to the edge of the visual realm and construct an orthogonal basis for \(\RR ^3\).

In the GeoGebra interactive below \(\{\vec {v}_1, \vec {v}_2, \vec {v}_3\}\) is a basis of \(\RR ^3\). Use check boxes to go through the steps for constructing an orthogonal basis starting with the given basis. RIGHT-CLICK and DRAG to rotate the image for a better view.

Gram-Schmidt Orthogonalization Algorithm

In Orthogonality and Projections we have repeatedly assumed that our subspaces of \(\RR ^n\) have an orthogonal basis. We will now prove that this is indeed the case. Recall that to be a basis of a subspace, a set of vectors must be linearly independent and it must span the subspace. We will start by demonstrating that a set of orthogonal vectors must be linearly independent.

To show that this set is linearly independent, we need to demonstrate that the only solution to the following equation is the trivial solution.

\[ a_1 \vec {w}_1 + a_2 \vec {w}_2 + \cdots + a_k \vec {w}_k = \vec {0} \]
To accomplish this, we need to show that all \(a_i = 0\) for all \(0\leq i\leq k\). To do so we take the dot product of each side of the above equation with the vector \(\vec {w}_i\) and obtain the following.
\begin{eqnarray*} \vec {w}_i \dotp (a_1 \vec {w}_1 + a_2 \vec {w}_2 + \cdots + a_k \vec {w}_k ) &=& \vec {w}_i \dotp \vec {0}\\ a_1 (\vec {w}_i \dotp \vec {w}_1) + a_2 (\vec {w}_i \dotp \vec {w}_2) + \cdots + a_k (\vec {w}_i \dotp \vec {w}_k) &=& 0 \end{eqnarray*}

Now since the set is orthogonal, \(\vec {w}_i \dotp \vec {w}_m = 0\) for all \(m \neq i\), so we have:

\[ a_1 (0) + \cdots + a_i(\vec {w}_i \dotp \vec {w}_i) + \cdots + a_k (0) = 0 \]
\[ a_i \norm {\vec {w}_i}^2 = 0 \]

We know that \(\norm {\vec {w}_i}^2 \neq 0\), so it follows that \(a_i =0\). Since \(i\) was chosen arbitrarily, \(a_i =0\) for all \(i\) \((0\leq i\leq k)\). This proves that \(\{ \vec {w}_1, \vec {w}_2, \cdots , \vec {w}_k \}\) is linearly independent.

The following theorem shows how to start with an arbitrary basis of a subspace \(W\) of \(\RR ^n\) and find an orthogonal basis for \(W\). To better understand the notation and the process presented in this theorem, you may want to match the steps of the theorem to the steps of Exploration .

Using the definition of projection onto a subspace, the iterative procedure above may be written:

\begin{equation}\label {eqn:GSproof} \begin{array}{ccl} \vec {f}_{1} &=& \vec {v}_{1} \\ \vec {f}_{2} &=& \vec {v}_{2} - \frac {\vec {v}_{2} \dotp \vec {f}_{1}}{\norm {\vec {f}_{1}}^2}\vec {f}_{1} \\ \vec {f}_{3} &=& \vec {v}_{3} - \frac {\vec {v}_{3} \dotp \vec {f}_{1}}{\norm {\vec {f}_{1}}^2}\vec {f}_{1} - \frac {\vec {v}_{3} \dotp \vec {f}_{2}}{\norm {\vec {f}_{2}}^2}\vec {f}_{2} \\ \vdots &&\\ \vec {f}_{k} &=& \vec {v}_{k} - \frac {\vec {v}_{k} \dotp \vec {f}_{1}}{\norm {\vec {f}_{1}}^2}\vec {f}_{1} - \frac {\vec {v}_{k} \dotp \vec {f}_{2}}{\norm {\vec {f}_{2}}^2}\vec {f}_{2} - \dots -\frac {\vec {v}_{k} \dotp \vec {f}_{k-1}}{\norm {\vec {f}_{k-1}}^2}\vec {f}_{k-1} \\ \vdots && \end{array} \end{equation}
We see immediately that \(\mbox {span}\{\vec {f}_{1}\}=W_1\) and that \(\mbox {span}\{\vec {f}_{1},\vec {f}_{2}\}=W_2\) because \(\vec {f}_{2}\) is a linear combination of \(\vec {v}_{1}\) and \(\vec {v}_{2}\). In fact, for any value of \(k\), we see that \(\mbox {span}\{\vec {f}_{1},\vec {f}_{2},\ldots ,\vec {f}_{k}\}=W_k\), because each \(\vec {f}_{k}\) is a linear combination of the vectors \(\{\vec {v}_{1},\vec {v}_{2},\ldots ,\vec {v}_{k-1}\}\).

Repeated application of Corollary ?? shows that the set \(\{\vec {f}_{1},\vec {f}_{2},\ldots ,\vec {f}_{m}\}\) is orthogonal. Linear independence follows from orthogonality by Theorem 1.

We conclude that \(\{\vec {f}_{1},\vec {f}_{2},\ldots ,\vec {f}_{m}\}\) is a linearly independent orthogonal set that spans \(W\).

The Gram-Schmidt algorithm demonstrates in a constructive way that every subspace of \(\RR ^n\) has an orthogonal basis. We formalize this in one final theorem.

Suppose \(\{\vec {f}_{1}, \dots , \vec {f}_{m}\}\) is an orthogonal subset of \(W\). If \(\mbox {span}\left (\vec {f}_{1}, \dots , \vec {f}_{m}\right ) = W\), it is already a basis. Otherwise, there exists \(\vec {x}\) in \(W\) outside \(\mbox {span}\left (\vec {f}_{1}, \dots , \vec {f}_{m}\right )\). Using the Gram-Schmidt procedure we define \(\vec {f}_{m+1} = \vec {x} - \mbox {proj}_{W_{m}}(\vec {x})\), where \(W_m = \mbox {span}\{\vec {f}_{1},\vec {f}_{2},\ldots ,\vec {f}_{m}\}\). If \(\mbox {span}\left (\vec {f}_{1}, \dots , \vec {f}_{m}, \vec {f}_{m+1}\right ) = W\), we are done. Otherwise, the process continues to create larger and larger orthogonal subsets of \(W\). They are all linearly independent by Theorem 3, so we have a basis when we reach a subset containing \(\mbox {dim}(W)\) vectors.

The process described in the proof of this theorem is used in this final example.

Practice Problems

Try Example 11 again starting with some other vector \(\vec {v}_4 \in \RR ^4\).

Problems -

In each case, use the Gram-Schmidt algorithm to convert the given basis \(\mathcal {B}\) of \(V\) to an orthogonal basis.

\(V = \RR ^2\), \(\mathcal {B} = \left \{\begin{bmatrix}1\\ -1\end{bmatrix}, \begin{bmatrix}2\\ 1\end{bmatrix}\right \}\)
\(V = \RR ^2\), \(\mathcal {B} = \left \{\begin{bmatrix}2\\ 1\end{bmatrix}, \begin{bmatrix}1\\ 2\end{bmatrix}\right \}\)
\(V = \RR ^3\), \(\mathcal {B} = \left \{\begin{bmatrix}1\\ -1\\ 1\end{bmatrix}, \begin{bmatrix}1\\ 0\\ 1\end{bmatrix}, \begin{bmatrix}1\\ 1\\ 2\end{bmatrix}\right \}\)
\(V = \RR ^3\), \(\mathcal {B} = \left \{\begin{bmatrix}0\\ 1\\ 1\end{bmatrix}, \begin{bmatrix}1\\ 1\\ 1\end{bmatrix}, \begin{bmatrix}1\\ -2\\ 2\end{bmatrix}\right \}\)

Text Source

This section was adapted from the first part of Section 8.1 of Keith Nicholson’s Linear Algebra with Applications. (CC-BY-NC-SA)

W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition, p. 415