The preview activity illustrates the main idea behind an algorithm, known as
Gram-Schmidt orthogonalization, that begins with a basis for some subspace of
\(\real^m\) and produces an orthogonal or orthonormal basis. The algorithm relies on our construction of the orthogonal projection. Remember that we formed the orthogonal projection
\(\bhat\) of
\(\bvec\) onto a subspace
\(W\) by requiring that
\(\bvec-\bhat\) is orthogonal to
\(W\) as shown in
Figure 6.4.3.
Activity 6.4.2.
Suppose that \(W\) is a three-dimensional subspace of \(\real^4\) with basis:
\begin{equation*}
\vvec_1 = \fourvec1111,\hspace{24pt}
\vvec_2 = \fourvec1322,\hspace{24pt}
\vvec_3 = \fourvec1{-3}{-3}{-3}\text{.}
\end{equation*}
We can see that this basis is not orthogonal by noting that \(\vvec_1\cdot\vvec_2 = 8\text{.}\) Our goal is to create an orthogonal basis \(\wvec_1\text{,}\) \(\wvec_2\text{,}\) and \(\wvec_3\) for \(W\text{.}\)
To begin, we declare that
\(\wvec_1=\vvec_1\text{,}\) and we call
\(W_1\) the line defined by
\(\wvec_1\text{.}\)
-
Find the vector
\(\vhat_2\) that is the orthogonal projection of
\(\vvec_2\) onto
\(W_1\text{,}\) the line defined by
\(\wvec_1\text{.}\)
-
Form the vector
\(\wvec_2 = \vvec_2-\vhat_2\) and verify that it is orthogonal to
\(\wvec_1\text{.}\)
-
Explain why
\(\laspan{\wvec_1,\wvec_2} =
\laspan{\vvec_1,\vvec_2}\) by showing that any linear combination of
\(\vvec_1\) and
\(\vvec_2\) can be written as a linear combination of
\(\wvec_1\) and
\(\wvec_2\) and vice versa.
-
The vectors
\(\wvec_1\) and
\(\wvec_2\) are an orthogonal basis for a two-dimensional subspace
\(W_2\) of
\(\real^4\text{.}\) Find the vector
\(\vhat_3\) that is the orthogonal projection of
\(\vvec_3\) onto
\(W_2\text{.}\)
-
Verify that
\(\wvec_3 = \vvec_3-\vhat_3\) is orthogonal to both
\(\wvec_1\) and
\(\wvec_2\text{.}\)
-
Explain why
\(\wvec_1\text{,}\) \(\wvec_2\text{,}\) and
\(\wvec_3\) form an orthogonal basis for
\(W\text{.}\)
-
Now find an orthonormal basis for
\(W\text{.}\)
As this activity illustrates, Gram-Schmidt orthogonalization begins with a basis
\(\vvec_1\vvec_2,\ldots,\vvec_n\) for a subspace
\(W\) of
\(\real^m\) and creates an orthogonal basis for
\(W\text{.}\) Let’s work through a second example.
Example 6.4.4.
Let’s start with the basis
\begin{equation*}
\vvec_1=\threevec{2}{-1}2,\hspace{24pt}
\vvec_2=\threevec{-3}{3}0,\hspace{24pt}
\vvec_3=\threevec{-2}71\text{,}
\end{equation*}
which is a basis for \(\real^3\text{.}\)
To get started, we’ll simply set \(\wvec_1=\vvec_1=\threevec{2}{-1}2\text{.}\) We construct \(\wvec_2\) from \(\vvec_2\) by subtracting its orthogonal projection onto \(W_1\text{,}\) the line defined by \(\wvec_1\text{.}\) This gives
\begin{equation*}
\wvec_2 = \vvec_2 -
\frac{\vvec_2\cdot\wvec_1}{\wvec_1\cdot\wvec_1}\wvec_1 =
\vvec_2 + \wvec_1 = \threevec{-1}22\text{.}
\end{equation*}
Notice that we found \(\vvec_2 = -\wvec_1 + \wvec_2\text{.}\) Therefore, we can rewrite any linear combination of \(\vvec_1\) and \(\vvec_2\) as
\begin{equation*}
c_1\vvec_1 + c_2\vvec_2 = c_1\wvec_1 + c_2(-\wvec_1+\wvec_2)
= (c_1-c_2)\wvec_1 + c_2\wvec_2\text{,}
\end{equation*}
a linear combination of \(\wvec_1\) and \(\wvec_2\text{.}\) This tells us that
\begin{equation*}
W_2 = \laspan{\wvec_1,\wvec_2} =
\laspan{\vvec_1,\vvec_2}\text{.}
\end{equation*}
In other words, \(\wvec_1\) and \(\wvec_2\) is a orthogonal basis for \(W_2\text{,}\) the 2-dimensional subspace that is the span of \(\vvec_1\) and \(\vvec_2\text{.}\)
Finally, we form \(\wvec_3\) from \(\vvec_3\) by subtracting its orthogonal projection onto \(W_2\text{:}\)
\begin{equation*}
\wvec_3 = \vvec_3 -
\frac{\vvec_3\cdot\wvec_1}{\wvec_1\cdot\wvec_1}\wvec_1 -
\frac{\vvec_3\cdot\wvec_2}{\wvec_2\cdot\wvec_2}\wvec_2
= \vvec_3 + \wvec_1 - 2\wvec_2
= \threevec22{-1}\text{.}
\end{equation*}
We can now check that
\begin{equation*}
\wvec_1=\threevec2{-1}2,\hspace{24pt}
\wvec_2=\threevec{-1}22,\hspace{24pt}
\wvec_3=\threevec22{-1},\hspace{24pt}
\end{equation*}
is an orthogonal set. Furthermore, we have, as before, \(\laspan{\wvec_1,\wvec_2,\wvec_3}
= \laspan{\vvec_1,\vvec_2,\vvec_3}\text{,}\) which says that we have found a new orthogonal basis for \(\real^3\text{.}\)
To create an orthonormal basis, we form unit vectors parallel to each of the vectors in the orthogonal basis:
\begin{equation*}
\uvec_1 = \threevec{2/3}{-1/3}{2/3},\hspace{24pt}
\uvec_2 = \threevec{-1/3}{2/3}{2/3},\hspace{24pt}
\uvec_3 = \threevec{2/3}{2/3}{-1/3}\text{.}
\end{equation*}
More generally, if we have a basis \(\vvec_1,\vvec_2,\ldots,\vvec_n\) for a subspace \(W\) of \(\real^m\text{,}\) the Gram-Schmidt algorithm creates an orthogonal basis for \(W\) in the following way:
\begin{align*}
\wvec_1 \amp = \vvec_1\\
\wvec_2 \amp = \vvec_2 -
\frac{\vvec_2\cdot\wvec_1}{\wvec_1\cdot\wvec_1}\wvec_1\\
\wvec_3 \amp = \vvec_3 -
\frac{\vvec_3\cdot\wvec_1}{\wvec_1\cdot\wvec_1}\wvec_1 -
\frac{\vvec_3\cdot\wvec_2}{\wvec_2\cdot\wvec_2}\wvec_2\\
\amp \vdots\\
\wvec_n \amp = \vvec_n -
\frac{\vvec_n\cdot\wvec_1}{\wvec_1\cdot\wvec_1}\wvec_1 -
\frac{\vvec_n\cdot\wvec_2}{\wvec_2\cdot\wvec_2}\wvec_2 -
\ldots -
\frac{\vvec_n\cdot\wvec_{n-1}}
{\wvec_{n-1}\cdot\wvec_{n-1}}\wvec_{n-1}
\text{.}
\end{align*}
Activity 6.4.3.
Sage can automate these computations for us. Before we begin, however, it will be helpful to understand how we can combine things using a
list in Python. For instance, if the vectors
v1,
v2, and
v3 form a basis for a subspace, we can bundle them together using square brackets:
[v1, v2, v3]. Furthermore, we could assign this to a variable, such as
basis = [v1, v2, v3].
Evaluating the following cell will load in some special commands.
-
There is a command to apply the projection formula:
projection(b, basis) returns the orthogonal projection of
b onto the subspace spanned by
basis, which is a list of vectors.
-
The command
unit(w) returns a unit vector parallel to
w.
-
Given a collection of vectors, say,
v1 and
v2, we can form the matrix whose columns are
v1 and
v2 using
matrix([v1, v2]).T. When given a
list of vectors, Sage constructs a matrix whose
rows are the given vectors. For this reason, we need to apply the transpose.
Let’s now consider \(W\text{,}\) the subspace of \(\real^5\) having basis
\begin{equation*}
\vvec_1 = \fivevec{14}{-6}{8}2{-6},\hspace{24pt}
\vvec_2 = \fivevec{5}{-3}{4}3{-7},\hspace{24pt}
\vvec_3 = \fivevec{2}30{-2}1.
\end{equation*}
-
Apply the Gram-Schmidt algorithm to find an orthogonal basis
\(\wvec_1\text{,}\) \(\wvec_2\text{,}\) and
\(\wvec_3\) for
\(W\text{.}\)
-
Find
\(\bhat\text{,}\) the orthogonal projection of
\(\bvec =
\fivevec{-5}{11}0{-1}5\) onto
\(W\text{.}\)
-
Explain why we know that \(\bhat\) is a linear combination of the original vectors \(\vvec_1\text{,}\) \(\vvec_2\text{,}\) and \(\vvec_3\) and then find weights so that
\begin{equation*}
\bhat = c_1\vvec_1 + c_2\vvec_2 + c_3\vvec_3.
\end{equation*}
-
Find an orthonormal basis
\(\uvec_1\text{,}\) \(\uvec_2\text{,}\) for
\(\uvec_3\) for
\(W\) and form the matrix
\(Q\) whose columns are these vectors.
-
Find the product
\(Q^TQ\) and explain the result.
-
Find the matrix
\(P\) that projects vectors orthogonally onto
\(W\) and verify that
\(P\bvec\) gives
\(\bhat\text{,}\) the orthogonal projection that you found earlier.
