13.2. FUNDAMENTAL THEORY AND GENERALIZATIONS 307

Proof: The theorem is clearly true if A is a 1×1 matrix. Just let U = 1, the 1×1 matrixwhich has entry 1. Suppose it is true for (n−1)× (n−1) matrices, n ≥ 2 and let A be ann×n matrix. Then let v1 be a unit eigenvector for A. Then there exists λ 1 such that

Av1 = λ 1v1, |v1|= 1.

Extend {v1} to a basis and then use the Gram - Schmidt process to obtain

{v1, · · · ,vn}

an orthonormal basis of Cn. Let U0 be a matrix whose ith column is vi so that U0 is unitary.Consider U∗0 AU0

U∗0 AU0 =

v∗1...

v∗n

( Av1 · · · Avn

)=

v∗1...

v∗n

( λ 1v1 · · · Avn

)

Thus U∗0 AU0 is of the form (λ 1 a0 A1

)where A1 is an n− 1× n− 1 matrix. Now by induction, there exists an (n−1)× (n−1)unitary matrix Ũ1 such that Ũ∗1 A1Ũ1 = Tn−1, an upper triangular matrix. Consider

U1 ≡

(1 00 Ũ1

).

Then

U∗1 U1 =

(1 00 Ũ∗1

)(1 00 Ũ1

)=

(1 00 In−1

)Also

U∗1 U∗0 AU0U1 =

(1 00 Ũ∗1

)(λ 1 ∗0 A1

)(1 00 Ũ1

)

=

(λ 1 ∗0 Tn−1

)≡ T

where T is upper triangular. Then let U =U0U1. It is clear that this is unitary because bothmatrices preserve distance. Therefore, so does the product and hence U . Alternatively,

I =U0U1U∗1 U∗0 = (U0U1)(U0U1)∗

and so, it follows that A is similar to T and that U0U1 is unitary. Hence A and T have thesame characteristic polynomials, and since the eigenvalues of T (A) are the diagonal entrieslisted with multiplicity, this proves the main conclusion of the theorem. In case A is realwith all real eigenvalues, the above argument can be repeated word for word using only thereal dot product to show that U can be taken to be real and orthogonal. ■

As a simple consequence of the above theorem, here is an interesting lemma.