2 CHARLES BORDENAVE AND DJALIL

CHAFA¨

I

by

sk(A) := λk(

√

AA∗)

for all 1 ≤ k ≤ n, where A∗ =

¯

A is the conjugate-transpose. We have

s1(A) ≥ · · · ≥ sn(A) ≥ 0.

The matrices A, A ,

A∗

have the same singular values. The Hermitian matrix

HA :=

0 A

A∗ 0

is 2n ×2n with eigenvalues s1(A), −s1(A),...,sn(A), −sn(A). This turns out to be

useful because the mapping A → HA is linear in A, in contrast with the mapping

A →

√

AA∗. If A ∈ {0, 1}n×n then A is the adjacency matrix of a graph, while

HA is the adjacency matrix of a bipartite nonoriented graph. Geometrically, the

matrix A maps the unit sphere to an ellipsoid, the half-lengths of its principal axes

being exactly the singular values of A. The operator norm or spectral norm of A is

A

2→2

:= max

x

2

=1

Ax

2

= s1(A) while sn(A) = min

x

2

=1

Ax

2

.

The rank of A is equal to the number of non-zero singular values. If A is non-singular

then

si(A−1)

=

sn−i(A)−1

for all 1 ≤ i ≤ n and sn(A) =

s1(A−1)−1

=

A−1

−1

2→2

.

A

Figure 1.

Largest and smallest singular values of A ∈ M2(R). Taken from

[CGLP] and used with permission of the Soci´ et´ e Math´ ematique de France.

Since the singular values are the eigenvalues of a Hermitian matrix, we have

variational formulas for all of them, often called the Courant-Fischer variational

formulas [HJ, Theorem 3.1.2]. Namely, denoting Gn,i the Grassmannian of all

i-dimensional subspaces, we have

si(A) = max

E∈Gn,i

min

x∈E

x

2

=1

Ax

2

= max

E,F ∈Gn,i

min

(x,y)∈E×F

x

2

= y

2

=1

Ax, y .

Most useful properties of the singular values are consequences of their Hermitian

nature via these variational formulas, which are valid in Cn if A ∈ Mn(C), and

in Rn if A ∈ Mn(R). In contrast, there are no such variational formulas for the

eigenvalues in great generality, beyond the case of normal matrices. It follows

from the Schur unitary

triangularization1

that for any fixed A ∈ Mn(C), we have

si(A) = |λi(A)| for every 1 ≤ i ≤ n if and only if A is normal (i.e.

AA∗

=

A∗A)2.

Beyond normal matrices, the relationships between eigenvalues and singular values

are captured by a set of inequalities due to Weyl, which can be obtained by using

the Schur unitary triangularization, see for instance [HJ, Th. 3.3.2 p. 171].

1If

A ∈ Mn(C) then there exists a unitary matrix U such that T = UAU

∗

is upper triangular.

2We

always use the word normal in this way, and never as a synonym for Gaussian.