The Gram-Schmidt Procedure

Section 3.2 The Gram-Schmidt Procedure

Given an nonzero vector

u

and a vector

v,

the projection of

v

onto

u

is given by

\begin{matrix} (3.2.1) & {proj}_{u} v = (\frac{v \cdot u}{‖ u ‖^{2}}) u . \end{matrix}

Note that this looks just like one of the terms in Fourier expansion theorem.

🔗

The motivation for the projection is as follows: Given the vectors

v

and

u,

we want to find vectors

w

and

z

with the following properties:

The vector $w$ is parallel to the vector $u .$
🔗

🔗
The vectors $w$ and $z$ add to $v .$
🔗

🔗
The vectors $w$ and $z$ are orthogonal.
🔗

🔗

🔗

The diagram shows two given vectors u and v, along with vectors w and z. The vectors w is parallel to u, while the vector z is orthogonal to u, and the two vectors sum to the vector v. The vector w is the projection of v onto u. — Figure 3.2.1. Illustrating the concept of orthogonal projection.
🔗

Motivation for the construction comes from Physics, where one needs to be able to decompose a force vector into parts that are parallel and orthogonal to a given direction.

🔗

To derive the formula, we note that the vector

w

must be a scalar multiple of

u,

since it is parallel to

u,

w = c u

for some scalar

c .

Next, since

w,

z,

and

v

form a right triangle,

Assuming that the angle

θ

is acute. If it is obtuse, the scalar

c

is negative, but so is the dot product, so the signs work out.

we know that

‖ w ‖ = c ‖ u ‖ = ‖ v ‖ \cos (θ) .

But

\cos (θ) = \frac{v \cdot u}{‖ v ‖ ‖ u ‖} .

Plugging this in, and solving for

c,

we get the formula in (3.2.1).

🔗

Exercise 3.2.2.

On the left, pairs of vectors

u, v

are given, and on the right, pairs of vectors

w, z .

Match each pair on the left with the pair on the right such that

w = {proj}_{u} v,

and

z = v - w .

🔗

You can solve this problem without actually computing any projections. Think about the relationships between the different vectors.

$u = ⟨ 4, 0, 2 ⟩,$ $v = ⟨ 3, 2, - 1 ⟩$
$w = ⟨ 2, 0, 1 ⟩,$ $z = ⟨ 1, 2, - 2 ⟩$
$u = ⟨ 2, 4, - 2 ⟩,$ $v = ⟨ 2, 1, 1 ⟩$
$w = ⟨ 1 / 2, 1, - 1 / 2 ⟩,$ $z = ⟨ 3 / 2, 0, 3 / 2 ⟩$
$u = ⟨ - 1, 2, 1 ⟩,$ $v = ⟨ 5, - 4, - 5 ⟩$
$w = ⟨ 3, - 6, - 3 ⟩,$ $z = ⟨ 2, 2, - 2 ⟩$

🔗

An important part of the projection construction is that the vector

z = v - {proj}_{u} v

is orthogonal to

u .

Our next result is a generalization of this observation.

🔗

Theorem 3.2.3. Orthogonal Lemma.

Let

{v_{1}, v_{2}, \dots, v_{m}}

be an orthogonal set of vectors in

R^{n},

and let

x

be any vector in

R^{n} .

Define the vector

v_{m + 1}

v_{m + 1} = x - (\frac{x \cdot v_{1}}{‖ v_{1} ‖^{2}} v_{1} + \dots + \frac{x \cdot v_{m}}{‖ v_{m} ‖^{2}} v_{m}) .

Then:

$v_{m + 1} \cdot v_{i} = 0$ for each $i = 1, \dots, m .$
🔗

🔗
If $x \notin span {v_{1}, \dots, v_{m}},$ then $v_{m + 1} \neq 0,$ and therefore, ${v_{1}, \dots, v_{m}, v_{m + 1}}$ is an orthogonal set.
🔗

🔗

🔗

Strategy.

For the first part, try calculating the dot product, using the definition of

v_{m + 1} .

Don’t forget that

v_{i} \cdot v_{j} = 0

i \neq j,

since you are assuming you have an orthogonal set of vectors.

🔗

For the second part, what does the Fourier Expansion Theorem say?

🔗

Proof.

For any $i = 1, \dots m,$ we have

$v_{m + 1} \cdot v_{i} = x \cdot v_{i} - \frac{x \cdot v_{i}}{‖ v_{i} ‖^{2}} (v_{i} \cdot v_{i}) = 0,$

since $v_{i} \cdot v_{j} = 0$ for $i \neq j .$

🔗

🔗
It follows from the Fourier expansion theorem that $v_{m + 1} = 0$ if and only if $x \in span {v_{1}, \dots, v_{m}},$ and the fact that ${v_{1}, \dots, v_{m}, v_{m + 1}}$ is an orthogonal set then follows from the first part.
🔗

🔗

🔗

It follows from the Orthogonal Lemma that for any subspace

U \subseteq R^{n},

any set of orthogonal vectors in

U

can be extended to an orthogonal basis of

U .

Since any set containing a single nonzero vector is orthogonal, it follows that every subspace has an orthogonal basis. (If

U = {0},

we consider the empty basis to be orthogonal.)

🔗

The procedure for creating an orthogonal basis is clear. Start with a single nonzero vector

x_{1} \in U,

which we’ll also call

v_{1} .

U \neq span {v_{1}},

choose a vector

x_{2} \in U

with

x_{2} \notin span {v_{1}} .

The Orthogonal Lemma then provides us with a vector

v_{2} = x_{2} - \frac{x_{2} \cdot v_{1}}{‖ v_{1} ‖^{2}} v_{1}

such that

{v_{1}, v_{2}}

is orthogonal. If

U = span {v_{1}, v_{2}},

we’re done. Otherwise, we repeat the process, choosing

x_{3} \notin span {v_{1}, v_{2}},

and then using the Orthogonal Lemma to obtain

v_{3},

and so on, until an orthogonal basis is obtained.

🔗

With one minor modification, the above procedure provides us with a major result. Suppose

U

is a subspace of

R^{n},

and start with any basis

{x_{1}, \dots, x_{m}}

U .

By choosing our

x_{i}

in the procedure above to be these basis vectors, we obtain the Gram-Schmidt algorithm for constructing an orthogonal basis.

🔗

Theorem 3.2.4. Gram-Schmidt Orthonormalization Algorithm.

Let

U

be a subspace of

R^{n},

and let

{x_{1}, \dots, x_{m}}

be a basis of

U .

Define vectors

v_{1}, \dots, v_{m}

U

as follows:

\begin{aligned} v_{1} & = x_{1} \\ v_{2} & = x_{2} - \frac{x_{2} \cdot v_{1}}{‖ v_{1} ‖^{2}} v_{1} \\ v_{3} & = x_{3} - \frac{x_{3} \cdot v_{1}}{‖ v_{1} ‖^{2}} v_{1} - \frac{x_{3} \cdot v_{2}}{‖ v_{2} ‖^{2}} v_{2} \\ ⋮ \\ v_{m} & = x_{m} - \frac{x_{m} \cdot v_{1}}{‖ v_{1} ‖^{2}} v_{1} - \dots - \frac{x_{m} \cdot v_{m - 1}}{‖ v_{m - 1} ‖^{2}} v_{m - 1} . \end{aligned}

Then

{v_{1}, \dots, v_{m}}

is an orthogonal basis for

U .

Moreover, for each

k = 1, 2, \dots, m,

we have

span {v_{1}, \dots, v_{k}} = span {x_{1}, \dots, x_{k}} .

🔗

Of course, once we’ve used Gram-Schmidt to find an orthogonal basis, we can normalize each vector to get an orthonormal basis. The Gram-Schmidt algorithm is ideal when we know how to find a basis for a subspace, but we need to know an orthogonal basis. For example, suppose we want an orthonormal basis for the nullspace of the matrix

A = [\begin{matrix} 2 & - 1 & 3 & 0 & 5 \\ 0 & 2 & - 3 & 1 & 4 \\ - 4 & 2 & - 6 & 0 & - 10 \\ 2 & 1 & 0 & 1 & 9 \end{matrix}] .

First, we find any basis for the nullspace.

🔗

xxxxxxxxxx
 
import sympy as sy
sy.init_printing()
A = sy.Matrix([[2,-1,3,0,5],
            [0,2,-3,1,4],
            [-4,2,-6,0,-10],
            [2,1,0,1,9]])
A.nullspace()

Let’s make that basis look a little nicer by using some scalar multiplication to clear fractions.

B = {x_{1} = [\begin{matrix} 3 \\ - 6 \\ - 4 \\ 0 \\ 0 \end{matrix}], x_{2} = [\begin{matrix} 1 \\ 2 \\ 0 \\ - 4 \\ 0 \end{matrix}], x_{3} = [\begin{matrix} 7 \\ 4 \\ 0 \\ 0 \\ - 2 \end{matrix}]}

This is definitely not an orthogonal basis. So we take

v_{1} = x_{1},

and

\begin{aligned} v_{2} & = x_{2} - (\frac{x_{2} \cdot v_{1}}{‖ v_{1} ‖^{2}}) v_{1} \\ = [\begin{array}{c} 1 \\ 2 \\ 0 \\ - 4 \\ 0 \end{array}] - \frac{- 9}{61} [\begin{array}{c} 3 \\ - 6 \\ - 4 \\ - 0 \\ 0 \end{array}], \end{aligned}

which equals something we probably don’t want to try to simplify. Finally, we find

v_{3} = x_{3} - (\frac{x_{3} \cdot v_{1}}{‖ v_{1} ‖^{2}}) v_{1} - (\frac{x_{3} \cdot v_{2}}{‖ v_{2} ‖^{2}}) v_{2} .

And now we probably get about five minutes into the fractions and say something that shouldn’t appear in print. This sounds like a job for the computer.

🔗

xxxxxxxxxx
 
B = A.nullspace()
sy.GramSchmidt(B)

What if we want our vectors normalized? Turns out the GramSchmidt function has an optional argument of true or false. The default is false, which is to not normalize. Setting it to true gives an orthonormal basis:

🔗

xxxxxxxxxx
 
sy.GramSchmidt(B,true)

OK, so that’s nice, and fairly intimidating looking. Did it work? We can specify the vectors in our list by giving their positions, which are 0, 1, and 2, respectively.

🔗

xxxxxxxxxx
 
L=sy.GramSchmidt(B)
L[0],L[1],L[2]

Let’s compute dot products:

🔗

xxxxxxxxxx
 
L[0].dot(L[1]),L[1].dot(L[2]),L[0].dot(L[2])

Let’s also confirm that these are indeed in the nullspace.

🔗

xxxxxxxxxx
 
A*L[0],A*L[1],A*L[2]

Boom. Let’s try another example. This time we’ll keep the vectors a little smaller in case you want to try it by hand.

🔗

Example 3.2.5.

Confirm that the set

B = {(1, - 2, 1), (3, 0, - 2), (- 1, 1, 2)}

is a basis for

R^{3},

and use the Gram-Schmidt Orthonormalization Algorithm to find an orthonormal basis.

🔗

Solution.

First, note that we can actually jump right into the Gram-Schmidt procedure. If the set

B

is not a basis, then it won’t be independent, and when we attempt to construct the third vector in our orthonormal basis, its projection on the the subspace spanned by the first two will be the same as the original vector, and we’ll get zero when we subtract the two.

🔗

We let

x_{1} = (1, - 2, 1), x_{2} = (3, 0, - 2), x_{3} = (- 1, 1, 2),

and set

v_{1} = x_{1} .

Then we have

\begin{aligned} v_{2} & = x_{2} - (\frac{x_{2} \cdot v_{1}}{‖ v_{1} ‖^{2}}) v_{1} \\ = (3, 0, - 2) - \frac{1}{6} (1, - 2, 1) \\ = \frac{1}{6} (17, 2, - 13) . \end{aligned}

🔗

Aside

Next, we compute

v_{3} .

\begin{aligned} v_{3} & = x_{3} - (\frac{x_{3} \cdot v_{1}}{‖ v_{1} ‖^{2}}) v_{1} - (\frac{x_{3} \cdot v_{2}}{‖ v_{2} ‖^{2}}) v_{2} \\ = (- 1, 1, 2) - \frac{- 1}{6} (1, - 2, 1) - \frac{- 41}{36} (17, 2, - 13) \\ = \frac{1}{462} ((- 462, 462, 924) + (77, - 154, 77) + (697, 82, - 533)) \\ = \frac{1}{462} (312, 390, 468) = \frac{1}{77} (52, 65, 78) . \end{aligned}

🔗

We got it done! But doing this sort of thing by hand makes it possible that we made a calculation error somewhere. To check our work, we can turn to the computer.

🔗

xxxxxxxxxx
 
sy.init_printing()
L=(sy.Matrix([1,-2,1]),sy.Matrix([3,0,-2]),sy.Matrix([-1,1,2]))
sy.GramSchmidt(L)

Success! Full disclosure: there was indeed a mistake in the manual computation. Whether it was a typo or a miscalculation, the

- 13 / 6

entry was originally written as

- 3 / 6 .

This led, as you might expect, to some very wrong answers for

v_{3} .

🔗

Exercises Exercises

1.

Let

x_{1} = [\begin{matrix} - 5 \\ 3 \\ 0 \\ - 3 \\ 0 \\ 1 \end{matrix}], x_{2} = [\begin{matrix} - 3 \\ 0 \\ 2 \\ 3 \\ 0 \\ - 1 \end{matrix}], and x_{3} = [\begin{matrix} - 1 \\ 0 \\ 0 \\ 0 \\ 4 \\ - 4 \end{matrix}] .

🔗

Use the Gram-Schmidt procedure to produce an orthogonal set with the same span.

🔗

2.

Let

x_{1} = [\begin{matrix} 3 \\ 0 \\ 4 \\ 0 \\ 4 \\ - 3 \end{matrix}], x_{2} = [\begin{matrix} 3 \\ - 4 \\ 2 \\ 0 \\ 4 \\ 0 \end{matrix}], and x_{3} = [\begin{matrix} 3 \\ 0 \\ 4 \\ - 1 \\ 1 \\ 0 \end{matrix}] .

🔗

Use the Gram-Schmidt procedure to produce an orthogonal set with the same span.

🔗

3.

Let

x_{1} = [\begin{matrix} 0 \\ 0 \\ 3 \\ 11 \\ 1 \\ 0 \end{matrix}], x_{2} = [\begin{matrix} 1 \\ 0 \\ 2 \\ 0 \\ 2 \\ 2 \end{matrix}], and x_{3} = [\begin{matrix} 2 \\ 14 \\ 2 \\ 0 \\ 2 \\ 0 \end{matrix}] .

🔗

Use the Gram-Schmidt procedure to produce an orthogonal set with the same span.

🔗

4.

Let

A = [\begin{array}{cccc} 3 & - 1 & 0 & 1 \\ 6 & 1 & - 9 & 5 \\ 3 & - 2 & 3 & 0 \\ 6 & - 1 & - 3 & 3 \end{array}] .

🔗

Find orthonormal bases of the kernel and image of

A .

🔗

You have attempted 1 of 6 activities on this page.

🔗

Prev Top Next