422 CHAPTER 19. EIGENVALUES AND EIGENVECTORS

What does it mean to say that UTU = I which is the definition for U to be orthogonal?

This says that for U =(u1 · · · un

),UT =

 uT1...uT

n

 and so from the way we multiply

matrices in which the i jth entry of the product is the product of the ith row of the matrix onthe left with the jth column of the matrix on the right, we have uT

i u j = δ i j. In other words,the columns of U are orthonormal. From this simple observation, the following theorem isobtained.

Theorem 19.8.3 Let {u1, · · · ,un} be orthonormal. Then it is linearly independent.

Proof: We know from the above discussion that U =(u1 · · · un

)is orthogo-

nal. Thus if Ux= 0, you can multiply on the left on both sides with UT and obtainx = UTUx = UT0 = 0. Thus, from the definition of linear independence, Definition18.5.1, it follows that the columns of U comprise an independent set of vectors.

The proof of the following theorem is based on the Gram Schmidt process.

Theorem 19.8.4 Let {x1, · · · ,xn} be linearly independent in Rp, p≥ n. Then thereexist orthonormal vectors {u1, · · · ,un} which have the property that for each k ≤ n,span(x1, · · · ,xk) = span(u1, · · · ,uk) .

Proof: Let u1 ≡ x1/ |x1| . Thus for k = 1, span(u1) = span(x1) and {u1} is anorthonormal set. Now suppose for some k < n, u1, · · · , uk have been chosen such that(u j,ul) = δ jl and span(x1, · · · ,xk) = span(u1, · · · ,uk). Then define

uk+1 ≡xk+1 −∑

kj=1 (xk+1 ·u j)u j∣∣∣xk+1 −∑kj=1 (xk+1 ·u j)u j

∣∣∣ , (19.2)

where the denominator is non-zero because the sum is in the span of the {x1, · · · ,xk}. Thusby induction,

uk+1 ∈ span(u1, · · · ,uk,xk+1) = span(x1, · · · ,xk,xk+1) .

Also, xk+1 ∈ span(u1, · · · ,uk,uk+1) from solving 19.2 for xk+1, and it follows

span(x1, · · · ,xk,xk+1) = span(u1, · · · ,uk,uk+1) .

If l ≤ k,

(uk+1 ·ul) =C

((xk+1 ·ul)−

k

∑j=1

(xk+1 ·u j)(u j ·ul)

)=

C

((xk+1 ·ul)−

k

∑j=1

(xk+1 ·u j)δ l j

)=C ((xk+1 ·ul)− (xk+1 ·ul)) = 0.

The vectors,{u j}n

j=1 , generated in this way are therefore orthonormal because each vectorhas unit length.