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.
Previous Page Next Page