Given two Hermitian matrices whose eigenvalues we know, what might be the
eigenvalues of the sum? In 1912 Weyl gave a short list of necessary conditions,
and in 1962 Horn conjectured an explicit list of necessary and sufficient
linear inequalities relating the spectra of the inputs to that of the sum.
In the early 1990's Klyachko proved a different (and less explicit) list
to be necessary and sufficient, but his list is redundant -- some of his
inequalities imply others. This problem is also intimately related to the
following question: when we tensor together two irreducible representations
of GL(n), which irreps occur in the product?
We introduce a new combinatorial object called a _honeycomb_ to study these
problems. Using honeycombs, we prove Horn's conjecture, determine which of
Klyachko's (and Horn's) conditions are redundant, and show that there
are no nasty surprises on going from the Hermitian matrix problem to
the tensor product problem. We comment on some other problems that
admit easy study via honeycombs.
This work is joint with Terry Tao of UCLA and Chris Woodward of Rutgers
and MSRI.