5.8. SHUR’S THEOREM 87

be a basis for Fn. Then there exists an orthonormal basis for Fn,

{u1, · · · ,un}

which has the property that for each k ≤ n,

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

Proof: Let {x1, · · · ,xn} be a basis for Fn. Let u1 ≡ x1/ |x1| . Thus for k = 1, span(u1) =span(x1) and {u1} is an orthonormal set. Now suppose for some k < n, u1, · · · , uk havebeen 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

∣∣∣ , (5.8.24)

where the denominator is not equal to zero because the x j form a basis and so

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

Thus by induction,

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

Also, xk+1 ∈ span(u1, · · · ,uk,uk+1) which is seen easily by solving 5.8.24 for xk+1 and itfollows

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 an orthonormal basis becauseeach vector has unit length.

The process by which these vectors were generated is called the Gram Schmidt process.Recall the following definition.

Definition 5.8.2 An n×n matrix, U, is unitary if UU∗ = I =U∗U where U∗ is defined tobe the transpose of the conjugate of U.

Theorem 5.8.3 Let A be an n×n matrix. Then there exists a unitary matrix, U such that

U∗AU = T, (5.8.25)

where T is an upper triangular matrix having the eigenvalues of A on the main diagonallisted according to multiplicity as roots of the characteristic equation.