208 CHAPTER 11. MATRICES AND THE INNER PRODUCT

With this definition and lemma here is the main theorem on the singular value decom-position.

Theorem 11.7.3 Let A be an m×n matrix. Then there exist unitary matrices, U and V ofthe appropriate size such that

U∗AV =

(σ 00 0

)where σ is of the form

σ =

σ1 0

. . .

0 σ k

for the σ i the singular values of A.

Proof: By the above lemma and Theorem 11.4.7 there exists an orthonormal basis,{vi}n

i=1 such that A∗Avi = σ2i vi where σ2

i > 0 for i = 1, · · · ,k,(σ i > 0) and equals zero ifi > k. Thus for i > k, Avi = 0 because

(Avi,Avi) = (A∗Avi,vi) = (0,vi) = 0.

For i = 1, · · · ,k, define ui ∈ Fm by

ui ≡ σ−1i Avi.

Thus Avi = σ iui. Now

(ui,u j) =(

σ−1i Avi,σ

−1j Av j

)=(

σ−1i vi,σ

−1j A∗Av j

)=

(σ−1i vi,σ

−1j σ

2jv j

)=

σ j

σ i(vi,v j) = δ i j.

Thus {ui}ki=1 is an orthonormal set of vectors in Fm. Also,

AA∗ui = AA∗σ−1i Avi = σ

−1i AA∗Avi = σ

−1i Aσ

2i vi = σ

2i ui.

Now extend {ui}ki=1 to an orthonormal basis for all of Fm,{ui}m

i=1 and let

U ≡ (u1 · · ·um)

while V ≡ (v1 · · ·vn) . Thus U is the matrix which has the ui as columns and V is definedas the matrix which has the vi as columns. Then

U∗AV =



u∗1...u∗k...

u∗m

A(v1 · · ·vn) =



u∗1...u∗k...

u∗m

(σ1u1 · · ·σ kuk,0 · · ·0) =

(σ 00 0

)

where σ is given in the statement of the theorem. ■The singular value decomposition has as an immediate corollary the following interest-

ing result.