Orthogonality, Orthogonal Projections and the Gram-Schmidt Algorithm

Question 1

Define orthogonality of sets.

Answer 1

A set of vectors {u1, u2, · · · , um} is called orthogonal if
ui.uj = 0, for all 1 ≤ i < j ≤ m and uj 6≠0 for 1 ≤ j ≤ m.
(They are all non-zero vectors and pairwise orthogonal).

Question 2

What is a fact about orthogonality and norms?

Answer 2

If {u1, u2, · · · , um} is an orthogonal set, then
||u1+u2+···+um||^2 = ||u1||^2 + ||u2||^2 + · · · + ||um||^2,
where ||ui||^2 = ui.ui for 1 ≤ i ≤ m.

Question 3

What are general facts about orthogonality of sets? (3)

Answer 3

1. Any orthogonal set of vectors is linearly independent,
2. Any orthogonal set of vectors in R^n has at most n vectors,
3. Any orthogonal set of vectors in R^n is a basis for R^n, which is called an orthogonal basis.

Question 4

The Expansion Theorem

Suppose {u1, · · · , um} is an orthogonal basis for a subspace W of R^n. Then…

Answer 4

Any vector v∈W can be written as
v = (v.u1/||u1||^2)u1 + … + (v.um/||um||^2)um
where the coefficients of u1, · · · , um are the coordinates of v relative to the basis. There are also called the Fourier coefficients.

Question 5

Orthogonal Projection onto a Subspace

Let W be a subspace of R^n and {u1, · · · , um} an orthogonal basis for W . Then,

Answer 5

For every v∈R^n, the orthogonal projection of v onto W is given by
Projw(v) = (v.u1/||u1||^2)u1 + … + (v.um/||um||^2)um

Question 6

Best Approximation Theorem

Let W be a subspace of R^n and v∈R^n. Then… (5)

Answer 6

1. ProjW(v) ∈ W ,
2. v − ProjW (v) is orthogonal to every vector in W ,
3. ProjW (v) is the best approximation to v by vectors in W (ProjW (v) is the closest vector in W to v),
4. ProjW (v) is the only vector in R^n which satisfies (1) and (2) above (It cannot even be scaled).
5. The orthogonal projection does not depend on a choice of orthogonal basis and with different bases we will obtain exactly the same projection.

Question 7

Give the intuition behind the Gram-Schmidt Algorithm.

Answer 7

Every subspace W of R^n has an orthogonal basis.

The Gram-Schmidt algorithm takes any basis of W as input and outputs an orthogonal basis of W .

Question 8

Gram-Schmidt Algorithm: Finding Orthogonal Basis

Suppose {u1, · · · , um} is any basis of W: (4)

Answer 8

1. w1 = u1 and V1 = Span{w1},
2. w2 = u2− ProjV1(u2) and V2=Span{w1, w2},
3. w3 = u3− ProjV2(u3) and V3 = Span{w1, w2, w3}
   m. wm = um− ProjVm−1(um) and Vm=Span{w1, w2,···,wm}
   Then, {w1, w2, · · · , wm} is an orthogonal basis for W .

Question 9

How else can one produce an orthogonal basis using the gram-schmidt algorithm?

Answer 9

One could also scale each of the vectors wi by dividing by their norm to produce an orthonornal basis:
{w1/||w1||, w2/||w2||, … wm/||wm||}, ||wi||= √(wi.wi)

Question 10

Give a general formula for the gram-schmidt algorithm.

Answer 10

see notes