Hermitian matrices and honeycombs

Allen Knutson Mathematics Department

Brandeis University

Terence Tao Mathematics Department

UCLA

www.math.ucla.edu/∼tao/preprints

The purpose of this talk is to:

• State Horn’s conjecture on the sum of two Hermitian matrices

• Describe the honeycomb model, which gives a geometric reformulation of the Hermitian matrices problem

• Discuss (briefly) connections with representation theory and Schubert calculus

• Outline the proof of the saturation conjecture, which is one of the key steps in the proof of Horn’s conjecture.

Weyl’s problem

• In 1912 Weyl posed the following problem: If A, B, C are Hermitian n×n matrices such that A+B = C, what is the complete set of relationships between the eigenvalues of A, B, and C?

• This problem historically arose from the problem of determining the moments of inertia of a compound object from the moments of its components.

• A precise statement is as follows. For any three ntuples a_{1} ≥ … ≥ a_{n}, b_{1} ≥ … ≥ b_{n}, c_{1} ≥ … ≥ c_{n} of reals, define (a_{1}, …, a_{n}) + (b_{1}, …, b_{n}) ∼ (c_{1}, …, c_{n}) to be the statement that there exist Hermitian matrices A, B, C with eigenvalues (a_{1}, …, a_{n}), (b_{1}, …, b_{n}), (c_{1}, …, c_{n}) respectively, such that A + B = C.

• Weyl’s problem is to find an effective description of this relation.

Some necessary conditions

• In order for (a_{1}, …, a_{n}) + (b_{1}, …, b_{n}) ∼ (c_{1}, …, c_{n}) to be true, we must have the identity

a_{1} + …+ a_{n} + b_{1} + …+ b_{n} = c_{1} + …+ c_{n}

from trace considerations.

• Also, we must have c_{1} ≤ a_{1} + b_{1}, since c_{1} is the operator norm of C, etc.

• Similarly, we have c_{1}+c_{2} ≤ a_{1}+a_{2}+b_{1}+b_{2}, etc., since c_{1}+c_{2} is the largest partial trace of C when restricted to a two-dimensional subspace, etc. This inequality generalizes in the obvious manner (Ky Fan, 1949)

• A less obvious necessary condition is c_{2} ≤ a_{2} + b_{1}. This follows from a minimax characterization

c_{2} = max_{dim V =2} min_{v∈V,|v|=1}⟨Cv, v⟩

where V ranges over all two-dimensional subspaces. More generally, we have the inequalities

c_{i+j−1} ≤ a_{i} + b_{j}

for all 1 ≤ i, j such that i + j − 1 ≤ n (Weyl, 1912).

• Numerous other inequalities are known. From minimax methods one can also prove

c_{i_{1}} + …+ c_{i_{r}} ≤ a_{i_{1}} + …+ a_{i_{r}} + b_{1} + …+ b_{r}

for any i_{1} < … < i_{r} (Berezin, Gelfand, Lidskii, Wielandt, c. 1950).

• All the known inequalities can be proven by minimax methods, although some of the minimax characterizations are quite subtle. For instance, the proof of the inequality

c_{2} + c_{5} ≤ a_{1} + a_{4} + b_{1} + b_{4}

requires the characterization

c_{2} + c_{5} = min_{V_{2}⊂V_{5}} max_{W_{2}:dim(W_{2}∩V_{2})=1,dim(W_{2}∩V_{5})=2}tr(C|_{W_{2}})

where V_{2}, W_{2} denote two-dimensional subspaces, and V_{5} denotes a five-dimensional subspace.

Positive results

• The previous list of necessary conditions consisted of one linear equality (the trace identity) and several linear inequalities. Thus we expect the solution set of (a_{1}, …, a_{n}) + (b_{1}, …, b_{n}) ∼ (c_{1}, …, c_{n}) to be a convex polytope. This turns out to be the case, but there is no elementary proof of this.

• However, it is fairly easy to show that the solution set is a finite union of polytopes. Indeed, we have

Proposition 0.1 If A + B = C and A, B, C have eigenvalues a_{1} ≥ … ≥ a_{n}, etc. respectively, then (a_{1}, …, c_{n}) is in the interior of the solution set unless A, B, C are simultaneously block diagonalizable. In particular, the boundary of the solution set lies on the union of hyperplanes of the form

a_{i_{1}} + …+ a_{i_{r}} + b_{j_{1}} + …+ b_{j_{r}} = c_{k_{1}} + …+ c_{k_{r}}.

• The proof of this proposition relies on the study of the vector space [A, u(n)], which is the tangent space of infinitesimal rotations of A. The point is that [A, u(n)] and [B, u(n)] are transverse in a certain sense unless A, B (and hence C) are simultaneously block diagonalizable.

• This leads one to conjecture that the solution set to Weyl’s problem is completely determined by the trace identity and a set of inequalities of the form

1a_{i_{1}} +…+a_{i_{r}} +b_{j_{1}} +…+b_{j_{r}} ≤ c_{k_{1}} +…+c_{k_{r}}. (0.1)

But which inequalities (1) are actually true? For instance, a_{1} + b_{1} ≤ c_{n} is not true. Also, some inequalities of the form (1) are true but redundant, e.g. a_{1}+b_{2} ≤ c_{1} is true but is redundant since a_{1}+b_{1} ≤ c_{1}.

Horn’s conjecture

• Obviously one has (a_{1}, …, a_{n})+(b_{1}, …, b_{n}) ∼ (c_{1}, …, c_{n}) when c = α(a) + β(b) for some permutations α, β ∈ S_{n}. This allows one to eliminate many relations of the form (1). For instance, one can quickly see that one requires

k_{r} ≤ i_{r} + j_{r} − r

and (to get a non-redundant condition) one needs

k_{1} + …+ k_{r} + \frac{r(r + 1)}{2} = i_{1} + …+ i_{r} + j_{1} + …+ j_{r}

In 1962 Horn noticed that these conditions are reminiscent of the conditions for Weyl’s problem. He then conjectured the following recursive solution of Weyl’s problem:

Conjecture 0.1 (Horn) The solution set to Weyl’s problem for n×n matrices is given by the trace identity all the inequalities of the form (1) such that 1 ≤ r < n and

(i_{1}−1, …, i_{r}−r)+(j_{1}−1, …, j_{r}−r) ∼ (k_{1}−1, …, k_{r}−r).

• This conjecture describes the solution set to the n×n problem recursively in terms of the (integer) solution set to the r × r problem for 1 ≤ r < n. Horn verified this conjecture for all n ≤ 8. A major breakthrough on the conjecture was made by Klyachko in 1994, in which the problem was reduced to a simpler problem known as the saturation conjecture. This conjecture was proven last year, thus completing the proof of Horn’s conjecture.

Honeycombs

• There is a geometrical reformulation of Weyl’s relation which makes it much easier to handle, involving an object which we call a honeycomb.

• Consider the plane {(a, b, c) ∈ R^{3} : a + b + c = 0}. This plane has three pairs of cardinal directions, given by the lines a = const, b = const, and c = const, at 120 degree angles to each other. We call these directions Northwest-Southeast, Northeast-Southwest, and North-South respectively.

• A honeycomb is a finite collection of line segments in this plane oriented in the six cardinal directions, with a positive integral multiplicity. We assume the “zero-tension” property. Basically, if we associate to each edge a tension proportional to its multiplicity, then the vector sum of the tension at any point is zero.

• Line segments may be infinite at one end. However, edges are only allowed to be infinite in three of the six cardinal directions (Northwest, Northeast, and South).

• Zero-length edges are allowed to exist, and one can always break up an edge into two or more sub-edges. We consider two honeycombs to be equivalent if they can be transformed by such operations.

• Despite the apparent flexibility of this definition of a honeycomb, the combinatorics of the honeycomb is actually fairly rigid. Firstly, from the zero-tension laws, the honeycomb must have the same number of infinite NW directions as NE directions or S directions (counting multiplicity); this number is called n, the order of the honeycomb. Secondly, the honeycomb is equivalent to some deformation of the regular honeycomb of order n (see applet). In fact, one can obtain any honeycomb of order n from the regular honeycomb by the linear operations of enlarging or shrinking a hexagon; edges are allowed to degenerate to zero, but cannot become negative. In particular, the space of honeycombs can be embedded in a vector space (e.g. parameterizing the honeycomb by the lengths of its edges, including degenerate ones), and becomes a convex polytope.

Connection with Weyl’s problem

• Each edge of the honeycomb is of the form a = const, b = const, or c = const. We call this constant the constant co-ordinate of the edge. Note that at any vertex which contains edges in all three directions, the constant co-ordinates of the a, b, and c-oriented edges add up to zero.

• In particular, the infinite edges are of the form a = a_{1}, …, a_{n}, b = b_{1}, …, b_{n}, c = c_{1}, …, c_{n}, possibly with multiplicity. We call these numbers the boundary data of the honeycomb.

• We can now give the fundamental connection between Weyl’s problem and honeycombs. We first rephrase Weyl’s relation in a symmetric way. We write

sum(a_{1}, …, a_{n}) + (b_{1}, …, b_{n}) + (c_{1}, …, c_{n}) ∼ 0

(0.2)

if there exist Hermitian matrices A, B, C with eigenvalues a_{1} ≥ … ≥ a_{n}, etc. such that A + B + C = 0. Clearly this relation is equivalent to

(a_{1}, …, a_{n}) + (b_{1}, …, b_{n}) ∼ (−c_{n}, …, −c_{1}).

Theorem 0.1 The relationship (2) holds if and only if there exists a honeycomb with boundary data (a_{1}, …, a_{n}), (b_{1}, …, b_{n}), (c_{1}, …, c_{n}).

• One can easily verify this theorem in the cases n = 1, 2.

• The proof of this theorem is very indirect. Roughly speaking, one can compute the probability that a randomly rotated triplet of matrices A, B, C with the specified eigenvalues will sum to zero. One can also compute the volume of the set of all honeycombs with the given boundary data (which happens to be a sub-polytope of the polytope of honeycombs). The two formulae happen to match up to a constant; in particular, one is non-zero if and only if the other one is. (We’re working on finding a more direct and insightful connection). There is a related proof using the Littlewood-Richardson rule, but that is also quite opaque.

• To justify the relationship, we will reprove some of the necessary conditions mentioned earlier. We begin with the trace identity, which in the symmetric setting becomes

a_{1} + …+ a_{n} + b_{1} + …+ b_{n} + c_{1} + …+ c_{n} = 0.

This comes from the fact that the constant co-ordinates at any vertex sums to zero.

• Now we show the inequality c_{1} ≤ a_{1} + b_{1}, which in the symmetric setting becomes a_{1} + b_{1} + c_{n} ≥ 0.

The easiest proof is to extend the b_{1} line all the way down to intersect the a_{1} line. By looking at a suitable sequence of line segments in the honeycomb, one can even measure the exact deviation a_{1} + b_{1} + c_{n} as the sum of lengths of line segments in the honeycomb.

• A similar argument shows, for instance, Weyl’s inequality a_{i} + b_{j} + c_{k} ≥ 0 whenever i + j + k = n + 2. Note that the collection of line segments needed to do this resembles a honeycomb of order 1. This goes a little way toward explaining the recursive nature of the Horn conjecture.

• Recall that honeycombs lie in the plane {(a, b, c) : a + b + c = 0}. If a, b, c are integers, we say that (a, b, c) is an integer point of this plane. We say that a honeycomb is an integral honeycomb if all of its vertices are integral points.

• By generalizing the argument used for the Weyl inequalities, it is possible to show:

Proposition 0.2 If there exists an integral honeycomb of order r, with boundary values (i_{1}−1, …, i_{r}− r), (j_{1} − 1, …, j_{r} − r), (n − k_{r}, n − 1 − k_{r−1}, …, n − r + 1 − k_{1}), then the inequality (1) holds for these values of i_{1}, …, k_{r}.

• This is close to Horn’s conjecture: it says that integral honeycombs give defining inequalities for Weyl’s problem. One also has to show the converse, that the inequalities obtained in this way are complete. Also, one has to show the following equivalence between honeycombs and integral honeycombs:

Conjecture 0.2 (Saturation conjecture) If (a_{1}, …, c_{r}) are integers, and there exists a honeycomb with data (a_{1}, …, c_{r}), then there exists an integral honeycomb with the same data.

• This conjecture is stating that a certain kind of polytope always contains a lattice point. We’ll explain why this conjecture is true at the end of the talk.

• The reduction of Horn to saturation was first obtained by Klyachko in 1994, but by powerful geometric invariant theory techniques rather than by honeycomb methods.

Interpretation of integral honeycombs

• It turns out that integral honeycombs have their own interpretation which does not appear directly related to Hermitian matrices.

• If a = (a_{1}, …, a_{n}) are a non-increasing sequence of integers, then there is a unique (up to isomorphism) irreducible representation V_{a} of GL_{n}(C) with weight a. If there is an integral honeycomb with boundary data a, b, c^{∗} = (−c_{n}, …, −c_{1}), then the representation V_{c^{∗}} occurs in the tensor product V_{a} ⊗ V_{b}. Equivalently, the tensor product V_{a} ⊗ V_{b} ⊗ V_{c} contains a GL_{n}(C)-invariant vector.

• In fact, we can say a little more: the number of integral honeycombs with this boundary data is equal to the multiplicity of V_{c^{∗}} in V_{a} ⊗ V_{b}, or the dimension of the invariant space of V_{a} ⊗ V_{b} ⊗ V_{c}. This multiplicity is known as a Littlewood-Richardson coefficient (or Clebsch-Gordan coefficient), and has been extensively studied.

• This equivalence is the quantum analogue of the equivalence of non-integer honeycombs with Weyl’s problem. Again, we do not have a direct explanation for this link, and can only prove this by counting arguments.

• These Littlewood-Richardson coefficients also come up in other problems in algebraic geometry, abelian group theory, and commutative ring theory, but we will not discuss them here.

Overlays

• If one degenerates enough edges of a honeycomb, then the honeycomb eventually becomes the superposition (or “overlay”) of two honeycombs of lesser order. For instance, if c = −α(a) − β(b) for some permutations α, β, then the honeycomb degenerates to the overlay of n honeycombs of order 1s.

• We conjecture that there is a canonical way to assign to each triplet of matrices A+B+C = 0 a honeycomb with boundary data (a_{1}, …, c_{n}). We believe that this overlay operation corresponds to the direct sum operation on the matrix level.

• Recall how we showed that a triplet of matrices could only reach boundary of the solution set for Weyl’s problem when the matrices were block diagonalizable (i.e. split as direct sum of smaller matrices). One can show the corresponding statement for honeycombs, that the honeycomb is at the boundary of the solution set only when it is an overlay of two smaller honeycombs. This is a key step in the honeycombbased proof of Horn’s conjecture.

Proof of saturation

• We now sketch how the saturation conjecture is proven. Suppose we have a honeycomb whose boundary data is integral. We have to show that there exists an integral honeycomb with the same boundary data.

• The set of all honeycombs with given boundary data is a convex polytope. We have to find an integral point of this polytope. An obvious thing to try is just to pick a vertex of this polytope; however there are examples where the vertex is non-integral even if the boundary data is integral.

• However, if one picks the vertex properly, one can always guarantee that the vertex will be integral. The idea is to always expand the hexagons of the honeycomb until an extremal point is obtained. When this occurs, the honeycomb degenerates to a cubic graph, and it is easy to show that the vertices of the honeycomb depend in an integral fashion on the boundary data, and are thus integer.