1.3. Eigenvalues and sums 39

1.3. Eigenvalues and sums of Hermitian matrices

Let A be a Hermitian n × n matrix. By the spectral theorem for Hermit-

ian matrices (which, for sake of completeness, we prove below), one can

diagonalise A using a

sequence11

λ1(A) ≥ . . . ≥ λn(A)

of n real eigenvalues, together with an orthonormal basis of eigenvectors

u1(A),...,un(A) ∈

Cn.

The set {λ1(A),...,λn(A)} is known as the spec-

trum of A.

A basic question in linear algebra asks the extent to which the eigenval-

ues λ1(A),...,λn(A) and λ1(B),...,λn(B) of two Hermitian matrices A, B

constrain the eigenvalues λ1(A+B),...,λn(A+B) of the sum. For instance,

the linearity of trace

tr(A + B) = tr(A) + tr(B),

when expressed in terms of eigenvalues, gives the trace constraint

(1.52) λ1(A + B) + · · · + λn(A + B) = λ1(A) + · · · + λn(A)

+λ1(B) + · · · + λn(B);

the identity

(1.53) λ1(A) = sup

|v|=1

v∗Av

(together with the counterparts for B and A + B) gives the inequality

(1.54) λ1(A + B) ≤ λ1(A) + λ1(B),

and so forth.

The complete answer to this problem is a fascinating one, requiring a

strangely recursive description (once known as Horn’s conjecture, which is

now solved), and connected to a large number of other fields of mathemat-

ics, such as geometric invariant theory, intersection theory, and the combi-

natorics of a certain gadget known as a “honeycomb”. See [KnTa2001] for

a survey of this topic.

In typical applications to random matrices, one of the matrices (say, B) is

“small” in some sense, so that A+B is a perturbation of A. In this case, one

does not need the full strength of the above theory, and instead relies on a

simple aspect of it pointed out in [HeRo1995], [To1994], which generates

several of the eigenvalue inequalities relating A, B, and A + B, of which

11The eigenvalues are uniquely determined by A, but the eigenvectors have a little ambiguity

to them, particularly if there are repeated eigenvalues; for instance, one could multiply each

eigenvector by a complex phase eiθ. In this text we are arranging eigenvalues in descending order;

of course, one can also arrange eigenvalues in increasing order, which causes some slight notational

changes in the results below.