Linear Algebra, Gram-Schmidt Orthogonalization

This subsection is optional. It requires material from the prior, also optional, subsection. The work done here will only be needed in the final two sections of Chapter Five.

The prior subsection suggests
that projecting onto the line spanned by \overset{→}{s}
decomposes a vector \overset{→}{v} into two parts

that are orthogonal and so are "not interacting".
We will now develop that suggestion.

Definition 2.1

Vectors {\overset{→}{v}}_{1} , … , {\overset{→}{v}}_{k} ∈ {ℝ}^{n} are mutually orthogonal when any two are orthogonal: if i ≠ j then the dot product {\overset{→}{v}}_{i} ⋅ {\overset{→}{v}}_{j} is zero.

Theorem 2.2

If the vectors in a set \{ {\overset{→}{v}}_{1} , … , {\overset{→}{v}}_{k} \} ⊂ {ℝ}^{n} are mutually orthogonal and nonzero then that set is linearly independent.

Proof

Consider a linear relationship
{c}_{1} {\overset{→}{v}}_{1} + {c}_{2} {\overset{→}{v}}_{2} + … + {c}_{k} {\overset{→}{v}}_{k} = \overset{→}{0}.
If i ∈ [ 1.. k ] then taking the dot product of {\overset{→}{v}}_{i}
with both sides of the equation

\begin{matrix}{\overset{→}{v}}_{i} ⋅ ( {c}_{1} {\overset{→}{v}}_{1} + {c}_{2} {\overset{→}{v}}_{2} + … + {c}_{k} {\overset{→}{v}}_{k} ) & = {\overset{→}{v}}_{i} ⋅ \overset{→}{0} \\ {c}_{i} ⋅ ( {\overset{→}{v}}_{i} ⋅ {\overset{→}{v}}_{i} ) & = 0\end{matrix}

shows, since {\overset{→}{v}}_{i} is nonzero, that {c}_{i} is zero.

Corollary 2.3

If the vectors in a size k subset of a k dimensional space are mutually orthogonal and nonzero then that set is a basis for the space.

Proof

Any linearly independent size k subset of a k dimensional space is a basis.

Of course, the converse of Corollary 2.3
does not hold— not every basis of every subspace
of {ℝ}^{n} is made of mutually orthogonal vectors.
However, we can get the partial converse
that for every subspace of {ℝ}^{n} there is at least one basis
consisting of mutually orthogonal vectors.

Example 2.4

The members {\overset{→}{β}}_{1} and {\overset{→}{β}}_{2} of this basis for {ℝ}^{2}
are not orthogonal.

However, we can derive from B
a new basis for the same space that does have mutually orthogonal members.
For the first member of the new basis we simply use {\overset{→}{β}}_{1}.

{\overset{→}{κ}}_{1} = ( \begin{matrix}4 \\ 2\end{matrix} )

For the second member of the new basis,
we take away from {\overset{→}{β}}_{2} its part in the direction of
{\overset{→}{κ}}_{1},

which leaves the part, {\overset{→}{κ}}_{2} pictured above, of {\overset{→}{β}}_{2} that is orthogonal to {\overset{→}{κ}}_{1} (it is orthogonal by the definition of the projection onto the span of {\overset{→}{κ}}_{1}). Note that, by the corollary, \{ {\overset{→}{κ}}_{1} , {\overset{→}{κ}}_{2} \} is a basis for {ℝ}^{2}.

Definition 2.5

An orthogonal basis for a vector space is a basis of mutually orthogonal vectors.

Example 2.6

To turn this basis for {ℝ}^{3}

⟨ ( \begin{matrix}1 \\ 1 \\ 1\end{matrix} ) , ( \begin{matrix}0 \\ 2 \\ 0\end{matrix} ) , ( \begin{matrix}1 \\ 0 \\ 3\end{matrix} ) ⟩

into an orthogonal basis, we take the first vector as it is given.

{\overset{→}{κ}}_{1} = ( \begin{matrix}1 \\ 1 \\ 1\end{matrix} )

We get {\overset{→}{κ}}_{2} by starting with the given second vector
{\overset{→}{β}}_{2} and
subtracting away the part of it in the direction of {\overset{→}{κ}}_{1}.

{\overset{→}{κ}}_{2} = ( \begin{matrix}0 \\ 2 \\ 0\end{matrix} ) − {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( ( \begin{matrix}0 \\ 2 \\ 0\end{matrix} ) ) = ( \begin{matrix}0 \\ 2 \\ 0\end{matrix} ) − ( \begin{matrix}2 / 3 \\ 2 / 3 \\ 2 / 3\end{matrix} ) = ( \begin{matrix}− 2 / 3 \\ 4 / 3 \\ − 2 / 3\end{matrix} )

Finally, we get {\overset{→}{κ}}_{3}
by taking the third given vector and subtracting the part of it
in the direction of {\overset{→}{κ}}_{1}, and also the part
of it in the direction of {\overset{→}{κ}}_{2}.

{\overset{→}{κ}}_{3} = ( \begin{matrix}1 \\ 0 \\ 3\end{matrix} ) − {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( ( \begin{matrix}1 \\ 0 \\ 3\end{matrix} ) ) − {\text{proj}}_{[ {\overset{→}{κ}}_{2} ]} ( ( \begin{matrix}1 \\ 0 \\ 3\end{matrix} ) ) = ( \begin{matrix}− 1 \\ 0 \\ 1\end{matrix} )

Again the corollary gives that

⟨ ( \begin{matrix}1 \\ 1 \\ 1\end{matrix} ) , ( \begin{matrix}− 2 / 3 \\ 4 / 3 \\ − 2 / 3\end{matrix} ) , ( \begin{matrix}− 1 \\ 0 \\ 1\end{matrix} ) ⟩

is a basis for the space.

The next result verifies that
the process used in those examples works with any basis for any
subspace of an {ℝ}^{n}
(we are restricted to {ℝ}^{n} only because we have not given a
definition of orthogonality for other vector spaces).

Theorem 2.7 (Gram-Schmidt orthogonalization)

If ⟨ {\overset{→}{β}}_{1} , … {\overset{→}{β}}_{k} ⟩
is a basis for a subspace of {ℝ}^{n} then, where

\begin{matrix}{\overset{→}{κ}}_{1} & = {\overset{→}{β}}_{1} \\ {\overset{→}{κ}}_{2} & = {\overset{→}{β}}_{2} − {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( {\overset{→}{β}}_{2} ) \\ {\overset{→}{κ}}_{3} & = {\overset{→}{β}}_{3} − {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( {\overset{→}{β}}_{3} ) − {\text{proj}}_{[ {\overset{→}{κ}}_{2} ]} ( {\overset{→}{β}}_{3} ) \\ & ⋮ \\ {\overset{→}{κ}}_{k} & = {\overset{→}{β}}_{k} − {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( {\overset{→}{β}}_{k} ) − ⋯ − {\text{proj}}_{[ {\overset{→}{κ}}_{k − 1} ]} ( {\overset{→}{β}}_{k} )\end{matrix}

the $\overset{→}{κ} $'s form an orthogonal basis for the same subspace.

Proof

We will use induction to check that each {\overset{→}{κ}}_{i} is nonzero,
is in the span of ⟨ {\overset{→}{β}}_{1} , … {\overset{→}{β}}_{i} ⟩
and is orthogonal to all preceding vectors:
{\overset{→}{κ}}_{1} ⋅ {\overset{→}{κ}}_{i} = ⋯ = {\overset{→}{κ}}_{i − 1} ⋅ {\overset{→}{κ}}_{i} = 0.
With those, and with
Corollary 2.3, we will have that
⟨ {\overset{→}{κ}}_{1} , … {\overset{→}{κ}}_{k} ⟩
is a basis for the same space as
⟨ {\overset{→}{β}}_{1} , … {\overset{→}{β}}_{k} ⟩.

We shall cover the cases up to i = 3, which give the
sense of the argument.
Completing the details is Problem 15.

The i = 1 case is trivial— setting {\overset{→}{κ}}_{1} equal to
{\overset{→}{β}}_{1}
makes it a nonzero vector since {\overset{→}{β}}_{1} is a member of a basis,
it is obviously in the desired span,
and the "orthogonal to all preceding vectors" condition is vacuously met.

For the i = 2 case, expand the definition of {\overset{→}{κ}}_{2}.

{\overset{→}{κ}}_{2} = {\overset{→}{β}}_{2} − {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( {\overset{→}{β}}_{2} ) = {\overset{→}{β}}_{2} − \frac{{\overset{→}{β}}_{2} ⋅ {\overset{→}{κ}}_{1}}{{\overset{→}{κ}}_{1} ⋅ {\overset{→}{κ}}_{1}} ⋅ {\overset{→}{κ}}_{1} = {\overset{→}{β}}_{2} − \frac{{\overset{→}{β}}_{2} ⋅ {\overset{→}{κ}}_{1}}{{\overset{→}{κ}}_{1} ⋅ {\overset{→}{κ}}_{1}} ⋅ {\overset{→}{β}}_{1}

This expansion shows that {\overset{→}{κ}}_{2} is nonzero or else this
would be a non-trivial linear dependence among the \overset{→}{β}'s
(it is nontrivial because the coefficient of {\overset{→}{β}}_{2} is 1)
and also shows that
{\overset{→}{κ}}_{2} is in the desired span.
Finally, {\overset{→}{κ}}_{2} is orthogonal to the only preceding vector

{\overset{→}{κ}}_{1} ⋅ {\overset{→}{κ}}_{2} = {\overset{→}{κ}}_{1} ⋅ ( {\overset{→}{β}}_{2} − {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( {\overset{→}{β}}_{2} ) ) = 0

because this projection is orthogonal.

The i = 3 case is the same as the i = 2 case except for one detail.
As in the i = 2 case, expanding the definition

\begin{matrix}{\overset{→}{κ}}_{3} & = {\overset{→}{β}}_{3} − \frac{{\overset{→}{β}}_{3} ⋅ {\overset{→}{κ}}_{1}}{{\overset{→}{κ}}_{1} ⋅ {\overset{→}{κ}}_{1}} ⋅ {\overset{→}{κ}}_{1} − \frac{{\overset{→}{β}}_{3} ⋅ {\overset{→}{κ}}_{2}}{{\overset{→}{κ}}_{2} ⋅ {\overset{→}{κ}}_{2}} ⋅ {\overset{→}{κ}}_{2} \\ & = {\overset{→}{β}}_{3} − \frac{{\overset{→}{β}}_{3} ⋅ {\overset{→}{κ}}_{1}}{{\overset{→}{κ}}_{1} ⋅ {\overset{→}{κ}}_{1}} ⋅ {\overset{→}{β}}_{1} − \frac{{\overset{→}{β}}_{3} ⋅ {\overset{→}{κ}}_{2}}{{\overset{→}{κ}}_{2} ⋅ {\overset{→}{κ}}_{2}} ⋅ ( {\overset{→}{β}}_{2} − \frac{{\overset{→}{β}}_{2} ⋅ {\overset{→}{κ}}_{1}}{{\overset{→}{κ}}_{1} ⋅ {\overset{→}{κ}}_{1}} ⋅ {\overset{→}{β}}_{1} )\end{matrix}

shows that {\overset{→}{κ}}_{3} is nonzero and is in the span.
A calculation shows that
{\overset{→}{κ}}_{3} is orthogonal to the preceding vector {\overset{→}{κ}}_{1}.

\begin{matrix}{\overset{→}{κ}}_{1} ⋅ {\overset{→}{κ}}_{3} & = {\overset{→}{κ}}_{1} ⋅ ( {\overset{→}{β}}_{3} − {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( {\overset{→}{β}}_{3} ) − {\text{proj}}_{[ {\overset{→}{κ}}_{2} ]} ( {\overset{→}{β}}_{3} ) ) \\ & = {\overset{→}{κ}}_{1} ⋅ ( {\overset{→}{β}}_{3} − {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( {\overset{→}{β}}_{3} ) ) − {\overset{→}{κ}}_{1} ⋅ {\text{proj}}_{[ {\overset{→}{κ}}_{2} ]} ( {\overset{→}{β}}_{3} ) \\ & = 0\end{matrix}

(Here's the difference from the i = 2 case— the second line has
two kinds of terms.
The first term is zero because this projection is orthogonal, as in the
i = 2 case.
The second term is zero because {\overset{→}{κ}}_{1} is orthogonal
to {\overset{→}{κ}}_{2} and so is orthogonal to any vector
in the line spanned by {\overset{→}{κ}}_{2}.)
The check that {\overset{→}{κ}}_{3} is also
orthogonal to the other preceding vector {\overset{→}{κ}}_{2} is similar.

Beyond having the vectors in the basis be orthogonal, we can do more; we can arrange for each vector to have length one by dividing each by its own length (we can normalize the lengths).

Example 2.8

Normalizing the length of each vector in the orthogonal basis of
Example 2.6
produces this orthonormal basis.

⟨ ( \begin{matrix}1 / \sqrt{3} \\ 1 / \sqrt{3} \\ 1 / \sqrt{3}\end{matrix} ) , ( \begin{matrix}− 1 / \sqrt{6} \\ 2 / \sqrt{6} \\ − 1 / \sqrt{6}\end{matrix} ) , ( \begin{matrix}− 1 / \sqrt{2} \\ 0 \\ 1 / \sqrt{2}\end{matrix} ) ⟩

Besides its intuitive appeal, and its analogy with the
standard basis {ℰ}_{n} for {ℝ}^{n}, an orthonormal basis also simplifies
some computations.
See Exercise 9, for example.

Exercises

Problem 1

Perform the Gram-Schmidt process on each of these bases
for {ℝ}^{2}.

• ⟨ ( \begin{matrix}1 \\ 1\end{matrix} ) , ( \begin{matrix}2 \\ 1\end{matrix} ) ⟩
• ⟨ ( \begin{matrix}0 \\ 1\end{matrix} ) , ( \begin{matrix}− 1 \\ 3\end{matrix} ) ⟩
• ⟨ ( \begin{matrix}0 \\ 1\end{matrix} ) , ( \begin{matrix}− 1 \\ 0\end{matrix} ) ⟩

Then turn those orthogonal bases into orthonormal bases.

This exercise is recommended for all readers.

Problem 2

Perform the Gram-Schmidt process on each of these bases
for {ℝ}^{3}.

• ⟨ ( \begin{matrix}2 \\ 2 \\ 2\end{matrix} ) , ( \begin{matrix}1 \\ 0 \\ − 1\end{matrix} ) , ( \begin{matrix}0 \\ 3 \\ 1\end{matrix} ) ⟩
• ⟨ ( \begin{matrix}1 \\ − 1 \\ 0\end{matrix} ) , ( \begin{matrix}0 \\ 1 \\ 0\end{matrix} ) , ( \begin{matrix}2 \\ 3 \\ 1\end{matrix} ) ⟩

Then turn those orthogonal bases into orthonormal bases.

This exercise is recommended for all readers.

Problem 3

Find an orthonormal basis for this subspace of {ℝ}^{3}: the
plane x − y + z = 0.

Problem 4

Find an orthonormal basis for this subspace of {ℝ}^{4}.

\{ ( \begin{matrix}x \\ y \\ z \\ w\end{matrix} ) \ | \ x − y − z + w = 0 \text{ and } x + z = 0 \}

Problem 5

Show that any linearly independent subset of {ℝ}^{n} can be
orthogonalized without changing its span.

This exercise is recommended for all readers.

Problem 6

What happens if we apply the Gram-Schmidt process to
a basis that is already orthogonal?

Problem 7

Let ⟨ {\overset{→}{κ}}_{1} , … , {\overset{→}{κ}}_{k} ⟩
be a set of mutually orthogonal vectors in {ℝ}^{n}.

• Prove that for any \overset{→}{v} in the space, the vector
  \overset{→}{v} − ( {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( \overset{→}{v} \ ) + … + {\text{proj}}_{[ {\overset{→}{v}}_{k} ]} ( \overset{→}{v} \ ) )
  is orthogonal to each of {\overset{→}{κ}}_{1}, ..., {\overset{→}{κ}}_{k}.
• Illustrate the prior item in {ℝ}^{3} by using {\overset{→}{e}}_{1} as

{\overset{→}{κ}}_{1}, using {\overset{→}{e}}_{2} as {\overset{→}{κ}}_{2}, and
taking \overset{→}{v} to have components 1, 2, and 3.

• Show that {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( \overset{→}{v} \ ) + … + {\text{proj}}_{[ {\overset{→}{v}}_{k} ]} ( \overset{→}{v} \ ) is the vector in the
  span of the set of \overset{→}{κ}'s that is closest to \overset{→}{v}.
  Hint. To the illustration done for the prior part,
  add a vector {d}_{1} {\overset{→}{κ}}_{1} + {d}_{2} {\overset{→}{κ}}_{2}
  and apply the Pythagorean Theorem to the resulting triangle.

Problem 8

Find a vector in {ℝ}^{3} that is orthogonal to both of these.

( \begin{matrix}1 \\ 5 \\ − 1\end{matrix} ) \ ( \begin{matrix}2 \\ 2 \\ 0\end{matrix} )

This exercise is recommended for all readers.

Problem 9

One advantage of orthogonal bases is that they simplify finding the
representation of a vector with respect to that basis.

• For this vector and this non-orthogonal basis for {ℝ}^{2}

\overset{→}{v} = ( \begin{matrix}2 \\ 3\end{matrix} ) \ B = ⟨ ( \begin{matrix}1 \\ 1\end{matrix} ) , ( \begin{matrix}1 \\ 0\end{matrix} ) ⟩

first represent the vector with respect to the basis.
Then project the vector onto the span of each basis vector
[ {\overset{→}{β}}_{1} ] and [ {\overset{→}{β}}_{2} ].

• With this orthogonal basis for {ℝ}^{2}

K = ⟨ ( \begin{matrix}1 \\ 1\end{matrix} ) , ( \begin{matrix}1 \\ − 1\end{matrix} ) ⟩

represent the same vector \overset{→}{v} with respect to the basis.
Then project the vector onto the span of each basis vector.
Note that the coefficients in the representation and the projection
are the same.

• Let
  K = ⟨ {\overset{→}{κ}}_{1} , … , {\overset{→}{κ}}_{k} ⟩
  be an orthogonal basis for some subspace of {ℝ}^{n}.
  Prove that for any \overset{→}{v} in the subspace,
  the i-th component of the representation {R e p}_{K} ( \overset{→}{v} \ )
  is the scalar coefficient ( \overset{→}{v} ⋅ {\overset{→}{κ}}_{i} ) / ( {\overset{→}{κ}}_{i} ⋅ {\overset{→}{κ}}_{i} )
  from {\text{proj}}_{[ {\overset{→}{κ}}_{i} ]} ( \overset{→}{v} \ ).
• Prove that

\overset{→}{v} = {\text{proj}}_{[ {\overset{→}{κ}}_{1} ]} ( \overset{→}{v} \ ) + … + {\text{proj}}_{[ {\overset{→}{κ}}_{k} ]} ( \overset{→}{v} \ ).

Problem 10

Bessel's Inequality.
Consider these orthonormal sets

{B}_{1} = \{ {\overset{→}{e}}_{1} \} \ {B}_{2} = \{ {\overset{→}{e}}_{1} , {\overset{→}{e}}_{2} \} \ {B}_{3} = \{ {\overset{→}{e}}_{1} , {\overset{→}{e}}_{2} , {\overset{→}{e}}_{3} \} \ {B}_{4} = \{ {\overset{→}{e}}_{1} , {\overset{→}{e}}_{2} , {\overset{→}{e}}_{3} , {\overset{→}{e}}_{4} \}

along with the vector \overset{→}{v} ∈ {ℝ}^{4} whose components are
4, 3, 2, and 1.

Find the coefficient {c}_{1} for the projection of
\overset{→}{v} onto the span of the vector in {B}_{1}.
Check that | \overset{→}{v} \ {|}^{2} ≥ | {c}_{1} {|}^{2}.

Find the coefficients {c}_{1} and {c}_{2} for the projection of \overset{→}{v}
onto the spans of the two vectors in {B}_{2}.
Check that | \overset{→}{v} \ {|}^{2} ≥ | {c}_{1} {|}^{2} + | {c}_{2} {|}^{2}.

• Find {c}_{1}, {c}_{2}, and {c}_{3} associated with the vectors in
  {B}_{3}, and {c}_{1}, {c}_{2}, {c}_{3}, and {c}_{4} for the vectors in {B}_{4}.
  Check that
  | \overset{→}{v} \ {|}^{2} ≥ | {c}_{1} {|}^{2} + … + | {c}_{3} {|}^{2} and
  that
  | \overset{→}{v} \ {|}^{2} ≥ | {c}_{1} {|}^{2} + … + | {c}_{4} {|}^{2}.

Show that this holds in general: where
\{ {\overset{→}{κ}}_{1} , … , {\overset{→}{κ}}_{k} \}
is an orthonormal set and {c}_{i} is coefficient of
the projection of a vector \overset{→}{v} from the space
then
| \overset{→}{v} \ {|}^{2} ≥ | {c}_{1} {|}^{2} + … + | {c}_{k} {|}^{2}.
Hint. One way is to look at the inequality
{}0 ≤ | \overset{→}{v} − ( {c}_{1} {\overset{→}{κ}}_{1} + … + {c}_{k} {\overset{→}{κ}}_{k} ) {|}^{2}
and expand the c's.

Problem 11

Prove or disprove: every vector in {ℝ}^{n} is in some orthogonal
basis.

Problem 12

Show that the columns of an n \ × \ n matrix form an orthonormal
set if and only if the inverse of the matrix is its transpose.
Produce such a matrix.

Problem 13

Does the proof of Theorem 2.2 fail to consider the
possibility that the set of vectors is empty (i.e., that k = 0)?

Problem 14

Theorem 2.7 describes a change of basis
from any basis B = ⟨ {\overset{→}{β}}_{1} , … , {\overset{→}{β}}_{k} ⟩
to one that is orthogonal
K = ⟨ {\overset{→}{κ}}_{1} , … , {\overset{→}{κ}}_{k} ⟩.
Consider the change of basis matrix {R e p}_{B , K} ( \text{id} ).

• Prove that the matrix {R e p}_{K , B} ( \text{id} )
  changing bases in the direction opposite to that of the theorem
  has an upper triangular shape— all
  of its entries below the main diagonal are zeros.
• Prove that the inverse of an upper triangular matrix is

also upper triangular (if the matrix is invertible, that is).
This shows that the matrix {R e p}_{B , K} ( \text{id} ) changing bases
in the direction described in the theorem is upper triangular.

Problem 15

Complete the induction argument in the proof of
Theorem 2.7.

Solutions

Where this page came from

This page was imported from Wikibooks. From “Linear Algebra” on Wikibooks, by its contributors, under CC BY-SA 4.0. Changed here: set as a page; navigation and edit links left out; each image under its own licence, credited in its caption.

Nobody has written it yet — it is the source material at a new address, which is why search engines are asked to skip it and why no one earns from it. It is up for grabs: take it on, and it is yours to rewrite and to earn from.