Gram-Schmidt Orthogonalization
In Orthogonality and Projections we said that a set of nonzero vectors in is called an orthogonal set if for all . 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 has an orthogonal basis. We will start with intuitive explorations in lower dimensions, then proceed to formalize our results for subspaces of .
A Visual Guide to Creating an Orthogonal Basis
Given an arbitrary basis of , let’s start building our orthogonal basis, , by setting . To find the next element of our orthogonal basis, consider the orthogonal projection of onto . (See the figure below.)
Next, let . Observe that is orthogonal to (See Theorem th:orthDecompX of Orthogonality and Projections). This gives us an orthogonal collection . It is intuitively clear that and are linearly independent. Therefore is an orthogonal basis of .
The following exploration illustrates this process dynamically.
Choose an arbitrary basis of by dragging the tips of vectors and 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 .
We can apply this process to any two-dimensional subset of . The following exploration will guide you through the process of constructing an orthogonal basis for a plane spanned by two arbitrary vectors in .
Let . is a plane through the origin in . Use the navigation bar at the bottom of the
interactive window to go through the steps of constructing an orthogonal basis for .
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 .
In the GeoGebra interactive below is a basis of . 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 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.
- Proof
- To show that this set is linearly independent, we need to demonstrate
that the only solution to the following equation is the trivial solution. To
accomplish this, we need to show that all for all . To do so we take the dot
product of each side of the above equation with the vector 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, for all , so we have:
We know that , so it follows that . Since was chosen arbitrarily, for all . This proves that is linearly independent.
The following theorem shows how to start with an arbitrary basis of a subspace of and find an orthogonal basis for . 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 exp:orth3.
Gram-Schmidt Orthogonalization If is any basis of a subspace of , consider the
following sequence of subspaces: \begin{equation*} \begin{array}{ccl} W_1&=&\mbox{span}\{\vec{v}_{1}\} \\ W_2&=&\mbox{span}\{\vec{v}_{1},\vec{v}_{2}\} \\ W_3&=&\mbox{span}\{\vec{v}_{1},\vec{v}_{2},\vec{v}_{3}\} \\ \vdots &&\\ W_m &=& \mbox{span}\{\vec{v}_{1},\vec{v}_{2},\vec{v}_{3},\ldots ,\vec{v}_{m}\} \end{array} \end{equation*}
Then we can construct an orthogonal basis for for each by adding one vector at a time successively as follows: \begin{equation*} \begin{array}{ccl} \vec{f}_{1} &=& \vec{v}_{1} \\ \vec{f}_{2} &=& \vec{v}_{2} - \mbox{proj}_{W_1}(\vec{v}_2) \\ \vec{f}_{3} &=& \vec{v}_{3} - \mbox{proj}_{W_2}(\vec{v}_3) \\ \vdots &&\\ \vec{f}_{m} &=& \vec{v}_{m} - \mbox{proj}_{W_{m-1}}(\vec{v}_m) \end{array} \end{equation*}
Then, will be an orthogonal basis for .
- Proof
- 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 and that because is a linear combination of and . In fact,
for any value of , we see that , because each is a linear combination of the vectors
.
Repeated application of Corollary cor:orthProjOntoW shows that the set is orthogonal. Linear independence follows from orthogonality by Theorem orthbasis.
We conclude that is a linearly independent orthogonal set that spans .
Erhardt Schmidt (1876–1959) was a German mathematician who studied under the
great David Hilbert. He first described the present algorithm in 1907. Jörgen
Pederson Gram (1850–1916) was a Danish actuary.
Find an orthogonal basis of the row space of .
Let , , denote the rows of and observe that is linearly independent. Take . The
algorithm gives
\begin{eqnarray*} \vec{f}_{2} &=& \vec{v}_{2} - \frac{\vec{v}_{2} \dotp \vec{f}_{1}}{\norm{\vec{f}_{1}}^2}\vec{f}_{1} = [3, 2, 0, 1] - \frac{4}{4}[1, 1, -1, -1] = [2, 1, 1, 2] \\ \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} = \vec{v}_{3} - \frac{0}{4}\vec{f}_{1} - \frac{3}{10}\vec{f}_{2} = \frac{1}{10}[4, -3, 7, -6] \end{eqnarray*}
Hence is the orthogonal basis provided by the algorithm. In hand calculations it may be convenient to eliminate fractions (see the Remark below), so is also an orthogonal basis for .
Observe that the vector is unchanged if a nonzero scalar multiple of is used in place
of . Hence, if a newly constructed is multiplied by a nonzero scalar at some stage of
the Gram-Schmidt algorithm, the subsequent s will be unchanged. This is useful in
actual calculations.
The Gram-Schmidt algorithm demonstrates in a constructive way that every subspace of has an orthogonal basis. We formalize this in one final theorem.
Let be a subspace of . Then has an orthogonal basis. In fact, every orthogonal
subset in can be extended to an orthogonal basis for .
- Proof
- Suppose is an orthogonal subset of . If , it is already a basis. Otherwise, there exists in outside . Using the Gram-Schmidt procedure we define , where . If , we are done. Otherwise, the process continues to create larger and larger orthogonal subsets of . They are all linearly independent by Theorem th:GS, so we have a basis when we reach a subset containing vectors.
The process described in the proof of this theorem is used in this final example.
In Example exa:023743, given , we showed that an orthogonal basis for is given by
Choose any vector not in , and apply the Gram-Schmidt algorithm to produce a vector such that is an orthogonal basis for .
Let . (How would you check that is not in ?) To get a vector orthogonal to the row
space, we perform an iteration of Gram-Schmidt:
\begin{eqnarray*} \vec{f} &=& \vec{v}_{4} - \frac{\vec{v}_{4} \dotp \vec{f}_{1}}{\norm{\vec{f}_{1}}^2}\vec{f}_{1} - \frac{\vec{v}_{4} \dotp \vec{f}_{2}}{\norm{\vec{f}_{2}}^2}\vec{f}_{2} - \frac{\vec{v}_{4} \dotp \vec{f}_{3}}{\norm{\vec{f}_{3}}^2}\vec{f}_{3} \\ &=& [1, 0, 0, 0] - \frac{1}{4}[1, 1, -1, -1] - \frac{2}{10}[2, 1, 1, 2] - \frac{4}{110}[4, -3, 7, -6] \\ &=&\frac{1}{44}[9, -15, -9, 3] \end{eqnarray*}
Since any multiple of will suffice, we are free to choose to get rid of the fraction. It
is easy to check that is an orthogonal set, and it follows from Theorem orthbasis that this set
is a basis for .
Suppose instead of we had started with . This vector is in , as it is the sum of
those three vectors. But if we were to try to proceed as above, we would get
\begin{eqnarray*} \vec{f} &=& \vec{v}_{4} - \frac{\vec{v}_{4} \dotp \vec{f}_{1}}{\norm{\vec{f}_{1}}^2}\vec{f}_{1} - \frac{\vec{v}_{4} \dotp \vec{f}_{2}}{\norm{\vec{f}_{2}}^2}\vec{f}_{2} - \frac{\vec{v}_{4} \dotp \vec{f}_{3}}{\norm{\vec{f}_{3}}^2}\vec{f}_{3} \\ &=& [7, -1, 7, -5] - \frac{4}{4}[1, 1, -1, -1] - \frac{10}{10}[2, 1, 1, 2] - \frac{110}{110}[4, -3, 7, -6] \\ &=&[0,0,0,0] \end{eqnarray*}
We could not add a multiple of to to get an orthogonal basis for .
Practice Problems
In each case, use the Gram-Schmidt algorithm to convert the given basis of to an orthogonal basis.
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
2024-09-11 17:58:23