Linear Algebra/Gram-Schmidt Orthogonalization

Linear Algebra
 ← Orthogonal Projection Onto a Line Gram-Schmidt Orthogonalization Projection Onto a Subspace → 

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 decomposes a vector into two parts

Linalg projection and orthog.png

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

Definition 2.1

Vectors are mutually orthogonal when any two are orthogonal: if then the dot product is zero.

Theorem 2.2

If the vectors in a set are mutually orthogonal and nonzero then that set is linearly independent.

Proof

Consider a linear relationship . If then taking the dot product of with both sides of the equation

shows, since is nonzero, that is zero.

Corollary 2.3

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

Proof

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

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

Example 2.4

The members and of this basis for are not orthogonal.

Linalg non orthog basis R2.png

However, we can derive from a new basis for the same space that does have mutually orthogonal members. For the first member of the new basis we simply use .

For the second member of the new basis, we take away from its part in the direction of ,

Linalg non orthog basis R2 2.png

which leaves the part, pictured above, of that is orthogonal to (it is orthogonal by the definition of the projection onto the span of ). Note that, by the corollary, is a basis for .

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

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

We get by starting with the given second vector and subtracting away the part of it in the direction of .

Finally, we get by taking the third given vector and subtracting the part of it in the direction of , and also the part of it in the direction of .

Again the corollary gives that

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 (we are restricted to only because we have not given a definition of orthogonality for other vector spaces).

Theorem 2.7 (Gram-Schmidt orthogonalization)

If is a basis for a subspace of then, where

the 's form an orthogonal basis for the same subspace.

Proof

We will use induction to check that each is nonzero, is in the span of and is orthogonal to all preceding vectors: . With those, and with Corollary 2.3, we will have that is a basis for the same space as .

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

The case is trivial— setting equal to makes it a nonzero vector since 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 case, expand the definition of .

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

because this projection is orthogonal.

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

shows that is nonzero and is in the span. A calculation shows that is orthogonal to the preceding vector .

(Here's the difference from the case— the second line has two kinds of terms. The first term is zero because this projection is orthogonal, as in the case. The second term is zero because is orthogonal to and so is orthogonal to any vector in the line spanned by .) The check that is also orthogonal to the other preceding vector 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.

Besides its intuitive appeal, and its analogy with the standard basis for , an orthonormal basis also simplifies some computations. See Exercise 9, for example.

ExercisesEdit

Problem 1

Perform the Gram-Schmidt process on each of these bases for  .

  1.  
  2.  
  3.  

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  .

  1.  
  2.  

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  : the plane  .

Problem 4

Find an orthonormal basis for this subspace of  .

 
Problem 5

Show that any linearly independent subset of   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   be a set of mutually orthogonal vectors in  .

  1. Prove that for any   in the space, the vector   is orthogonal to each of  , ...,  .
  2. Illustrate the prior item in   by using   as  , using   as  , and taking   to have components  ,  , and  .
  3. Show that   is the vector in the span of the set of  's that is closest to  . Hint. To the illustration done for the prior part, add a vector   and apply the Pythagorean Theorem to the resulting triangle.
Problem 8

Find a vector in   that is orthogonal to both of these.

 
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.

  1. For this vector and this non-orthogonal basis for  
     
    first represent the vector with respect to the basis. Then project the vector onto the span of each basis vector   and  .
  2. With this orthogonal basis for  
     
    represent the same vector   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.
  3. Let   be an orthogonal basis for some subspace of  . Prove that for any   in the subspace, the  -th component of the representation   is the scalar coefficient   from  .
  4. Prove that  .
Problem 10

Bessel's Inequality. Consider these orthonormal sets

 

along with the vector   whose components are  ,  ,  , and  .

  1. Find the coefficient   for the projection of   onto the span of the vector in  . Check that  .
  2. Find the coefficients   and   for the projection of   onto the spans of the two vectors in  . Check that  .
  3. Find  ,  , and   associated with the vectors in  , and  ,  ,  , and   for the vectors in  . Check that   and that  .

Show that this holds in general: where   is an orthonormal set and   is coefficient of the projection of a vector   from the space then  . Hint. One way is to look at the inequality   and expand the  's.

Problem 11

Prove or disprove: every vector in   is in some orthogonal basis.

Problem 12

Show that the columns of an   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  )?

Problem 14

Theorem 2.7 describes a change of basis from any basis   to one that is orthogonal  . Consider the change of basis matrix  .

  1. Prove that the matrix   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.
  2. 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   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

Linear Algebra
 ← Orthogonal Projection Onto a Line Gram-Schmidt Orthogonalization Projection Onto a Subspace →