13.15. THE SINGULAR VALUE DECOMPOSITION 373

where σ denotes an r× r diagonal matrix of the formσ1 0

. . .

0 σ k

and the bottom row of zero matrices in the partitioned matrix, as well as the right columnsof zero matrices are each of the right size so that the resulting matrix is m× n. Eithercould vanish completely. However, I will write it in the above form. It is easy to make thenecessary adjustments in the other two cases.

Theorem 13.15.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, arranged in order of decreasing size.

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

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

i > 0 for i = 1, · · · ,k,σ i > 0, and equalszero if i > k. Let the eigenvalues σ2

i be arranged in decreasing order. It is desired to have

AV =U

(σ 00 0

)

and so if U =(

u1 · · · um

), one needs to have for j ≤ k, σ ju j = Av j. Thus let

u j ≡ σ−1j Av j, j ≤ k

Then for i, j ≤ k,

(ui,u j) = σ−1j σ

−1i (Avi,Av j) = σ

−1j σ

−1i (A∗Avi,v j)

= σ−1j σ

−1i σ

2i (vi,v j) = δ i j

Now extend to an orthonormal basis of Fm,{u1, · · · ,uk,uk+1, · · · ,um} . If i > k,

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

so Avi = 0. Then for σ given as above in the statement of the theorem, it follows that

AV =U

(σ 00 0

), U∗AV =

(σ 00 0

)■

The singular value decomposition has as an immediate corollary the following interest-ing result.