1.3. Eigenvalues and sums 51

inner product

uj(An−1)∗X

is small. This type of observation is useful to

achieve eigenvalue repulsion—to show that it is unlikely that the gap be-

tween two adjacent eigenvalues is small. We shall see examples of this in

later sections.

1.3.6. Singular values. The theory of eigenvalues of n × n Hermitian

matrices has an analogue in the theory of singular values of p × n non-

Hermitian matrices. We first begin with the counterpart to the spectral

theorem, namely the singular value decomposition.

Theorem 1.3.9 (Singular value decomposition). Let 0 ≤ p ≤ n, and let A

be a linear transformation from an n-dimensional complex Hilbert space U

to a p-dimensional complex Hilbert space V . (In particular, A could be an

p × n matrix with complex entries, viewed as a linear transformation from

Cn

to

Cp.)

Then there exist non-negative real numbers

σ1(A) ≥ · · · ≥ σp(A) ≥ 0

(known as the singular values of A) and orthonormal sets u1(A),...,up(A) ∈

U and v1(A),...,vp(A) ∈ V (known as singular vectors of A), such that

Auj = σjvj;

A∗vj

= σjuj

for all 1 ≤ j ≤ p, where we abbreviate uj = uj(A), etc.

Furthermore, Au = 0 whenever u is orthogonal to all u1(A),...,up(A).

We adopt the convention that σi(A) = 0 for i p. The above theorem

only applies to matrices with at least as many rows as columns, but one

can also extend the definition to matrices with more columns than rows

by adopting the convention σi(A∗) := σi(A) (it is easy to check that this

extension is consistent on square matrices). All of the results below extend

(with minor modifications) to the case when there are more columns than

rows, but we have not displayed those extensions here in order to simplify

the notation.

Proof. We induct on p. The claim is vacuous for p = 0, so suppose that

p ≥ 1 and that the claim has already been proven for p − 1.

We follow a similar strategy to the proof of Theorem 1.3.1. We may

assume that A is not identically zero, as the claim is obvious otherwise. The

function u → Au

2

is continuous on the unit sphere of U, so there exists

a unit vector u1 which maximises this quantity. If we set σ1 := Au1 0,

one easily verifies that u1 is a critical point of the map u → Au

2

−σ1

2

u

2,

which then implies that

A∗Au1

= σ1u1.

2

Thus, if we set v1 := Au1/σ1, then

Au1 = σ1v1 and

A∗v1

= σ1u1. This implies that A maps the orthogonal

complement u1

⊥

of u1 in U to the orthogonal complement v1

⊥

of v1 in V .

By induction hypothesis, the restriction of A to u1

⊥

(and v1

⊥)

then admits