\documentstyle[amssymb,amsfonts,psfig,12pt]{article}
\input MathMacro.tex 
\newcommand{\eqn}[1]{(\ref{#1})}
\newcommand{\is}{$I^{s}\;$}
\newcommand{\mbf}[1]{\mbox{\boldmath ${#1}$}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{  \end{center}}
\newcommand{\page}{\vfil \break}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{  \end{itemize}}
\newcommand{\benum}{\begin{enumerate}}
\newcommand{\eenum}{  \end{enumerate}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{  \end{description}}
\def\rp{{r^\prime}}
\def\rpt{{\tilde r^\prime}}
\def\rtil{{\tilde r}}
\def\qtil{{\tilde q}}
\def\kp{{k^\prime}}
\def\kt{{\tilde{k}}}
\def\qp{{q^\prime}}
\def\pp{{p^\prime}}
\def\qpt{{\tilde q^\prime}}
\def\R{{\hbox{\bf R}}}
\def\C{{\hbox{\bf C}}}
\def\rn{{\R^n}}
\def\Z{{\hbox{\bf Z}}}
\def\eps{{\varepsilon}}
\def\implies{{\Rightarrow}}
\def\RR{{\frak R}}
% \newcommand{\lesssim}{\mbox{$\,\stackrel{\textstyle{<}}{\sim}\,$}}

\renewcommand {\theequation}{\thesection.\arabic{equation}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{conjecture}{Conjecture}[section]
\newtheorem{remark}{Remark}[section]

\begin{document}
\Large
\vskip 1in
\bc
{\bf \LARGE  Hermitian matrices and honeycombs}
 
\bigskip
\bigskip
Allen Knutson \\
\bigskip
{\it Mathematics Department \\ \bigskip Brandeis University \\ }  
\bigskip
Terence Tao \\
\bigskip
{\it Mathematics Department \\ \bigskip UCLA \\ }  
\bigskip
\bigskip
\ 
\bigskip
{\tt www.math.ucla.edu/$\sim$tao/preprints } 
\ec

\page

\noindent
{\LARGE
The purpose of this talk is to:
}
\bigskip
\bi
 \item State Horn's conjecture on the sum of two Hermitian matrices

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

 \item Discuss (briefly) connections with representation theory and
Schubert calculus

 \item Outline the proof of the saturation conjecture, which is one of the key
steps in the proof of Horn's conjecture.

\ei

\page

\noindent
Weyl's problem

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

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

\item A precise statement is as follows.  For any three $n$-tuples
$a_1 \geq \ldots \geq a_n$, $b_1 \geq \ldots \geq b_n$, 
$c_1 \geq \ldots \geq c_n$ of
reals, define $(a_1, \ldots, a_n) + (b_1, \ldots, b_n) \sim (c_1, \ldots, c_n)$
to be the statement that there exist Hermitian matrices $A$, $B$, $C$
with eigenvalues $(a_1, \ldots, a_n)$, $(b_1, \ldots, b_n)$, $(c_1, \ldots,c_n)$ respectively, such that $A+B=C$.  

\item Weyl's problem is to find an effective description of this
relation.

\ei

\page

\bigskip
\noindent

Some necessary conditions

\bi

\item In order for $(a_1, \ldots, a_n) + (b_1, \ldots, b_n) \sim 
(c_1, \ldots, c_n)$ to be true, we must have the identity
$$ a_1 + \ldots + a_n + b_1 + \ldots + b_n = c_1 + \ldots + c_n$$
from trace considerations.

\item Also, we must have $c_1 \leq a_1 + b_1$, since $c_1$
is the operator norm of $C$, etc.

\item Similarly, we have $c_1 + c_2 \leq 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)

\item A less obvious necessary condition is $c_2 \leq a_2 + b_1$.  This
follows from a minimax characterization
$$ c_2 = \max_{\dim V = 2} \min_{v \in V, |v| = 1} \langle Cv,v\rangle$$
where $V$ ranges over all two-dimensional subspaces.  More generally,
we have the inequalities
$$ c_{i+j-1} \leq a_i + b_j$$
for all $1 \leq i,j$ such that $i+j-1 \leq n$ (Weyl, 1912).

\item Numerous other inequalities are known.  From minimax methods one
can also prove
$$ c_{i_1} + \ldots + c_{i_r} \leq a_{i_1} + \ldots + a_{i_r} + b_1 + \ldots
+ b_r$$
for any $i_1 < \ldots < i_r$ (Berezin, Gelfand, Lidskii, Wielandt, c. 1950).

\item 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 \leq a_1 + a_4 + b_1 + b_4$$
requires the characterization
$$ c_2 + c_5 = \min_{V_2 \subset V_5} \max_{W_2: \dim(W_2 \cap V_2) = 1,
\dim(W_2 \cap V_5) = 2} tr(C|_{W_2})$$
where $V_2$, $W_2$ denote two-dimensional subspaces, and $V_5$ denotes
a five-dimensional subspace.
\ei

\page

Positive results

\bi 
\item  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, \ldots, a_n) + (b_1, \ldots, b_n)
\sim (c_1, \ldots, c_n)$ to be a convex polytope.  This turns out to be the
case, but there is no elementary proof of this.

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

\begin{proposition}  If $A+B=C$ and $A$, $B$, $C$ have eigenvalues
$a_1 \geq \ldots \geq a_n$, etc. respectively, then $(a_1, \ldots, 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} + \ldots + a_{i_r} + b_{j_1} + \ldots + b_{j_r} =
c_{k_1} + \ldots + c_{k_r}.$$
\end{proposition}

\item 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. 

\item  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
\be{1}
 a_{i_1} + \ldots + a_{i_r} + b_{j_1} + \ldots + b_{j_r} \leq
c_{k_1} + \ldots + c_{k_r}.
\end{equation}
But which inequalities (1) are actually true?  For instance,
$a_1 + b_1 \leq c_n$ is not true.  Also, some inequalities of the form
(1) are true but redundant, e.g. $a_1 + b_2 \leq c_1$ is true
but is redundant since $a_1 + b_1 \leq c_1$.

\ei

\page

Horn's conjecture

\bi
 \item Obviously one has $(a_1,\ldots,a_n) + (b_1, \ldots, b_n)
\sim (c_1, \ldots, c_n)$ when $c = \alpha(a) + \beta(b)$ for some
permutations $\alpha,\beta \in S_n$.  This allows one to eliminate
many relations of the form (1).  For instance, one can
quickly see that one requires
$$ k_r \leq i_r + j_r - r$$
and (to get a non-redundant condition) one needs
$$ k_1 + \ldots + k_r + \frac{r(r+1)}{2} = 
i_1 + \ldots + i_r + j_1 + \ldots + 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:

\begin{conjecture}[Horn]  The solution set to Weyl's problem for $n \times n$
matrices is given by the trace identity
all the inequalities of the form (1) such that $1 \leq r < n$ and
$$ (i_1 - 1, \ldots, i_r - r) + (j_1 - 1, \ldots, j_r - r)
\sim (k_1 - 1, \ldots, k_r - r).$$
\end{conjecture}

\item  This conjecture describes the solution set to the $n \times n$
problem recursively in terms of the (integer) solution set to the $r \times r$
problem for $1 \leq r < n$.  Horn verified this conjecture for all $n \leq 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.

\ei

\page
\noindent

Honeycombs

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

\item Consider the plane $\{ (a,b,c) \in \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.

\item A {\it 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.

\item 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).

\item 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.

\item 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.

\ei

\page
\noindent

Connection with Weyl's problem

\bi

\item Each edge of the honeycomb is of the form $a = const$, $b = const$,
or $c = const$.  We call this constant the {\it 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.

\item In particular, the infinite edges are of the form $a = a_1, \ldots, a_n$,
$b = b_1, \ldots, b_n$, $c = c_1, \ldots, c_n$, possibly with multiplicity.
We call these numbers the {\it boundary data} of the honeycomb.

\item 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
\be{sum}
 (a_1, \ldots, a_n) + (b_1, \ldots, b_n) + (c_1, \ldots, c_n) \sim 0
\end{equation}
if there exist Hermitian matrices $A, B, C$ with eigenvalues
$a_1 \geq \ldots \geq a_n$, etc. such that $A+B+C = 0$.  Clearly
this relation is equivalent to 
$$ (a_1, \ldots, a_n) + (b_1, \ldots, b_n) \sim (-c_n, \ldots, -c_1).$$

\begin{theorem} The relationship (2) holds if and only if there
exists a honeycomb with boundary data
$(a_1, \ldots, a_n)$, $(b_1, \ldots, b_n)$, $(c_1, \ldots, c_n)$.
\end{theorem}

\item One can easily verify this theorem in the cases $n=1,2$.
\ei

\page

\bi

\item 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.

\item 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 + \ldots + a_n + b_1 + \ldots + b_n + c_1 + \ldots + c_n = 0.$$
This comes from the fact that the constant co-ordinates at any vertex
sums to zero.

\item Now we show the inequality $c_1 \leq a_1 + b_1$, which in
the symmetric setting becomes $a_1 + b_1 + c_n \geq 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.

\item A similar argument shows, for instance, Weyl's inequality
$a_i + b_j + c_k \geq 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.

\ei

\page

\bi

\item 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 {\it integer point}
of this plane.  We say that a honeycomb is an {\it integral honeycomb}
if all of its vertices are integral points.

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

\begin{proposition}  If there exists an integral honeycomb of order
$r$, with boundary values $(i_1-1, \ldots, i_r-r)$, $(j_1-1, \ldots, j_r-r)$,
$(n-k_r, n-1-k_{r-1}, \ldots, n-r+1-k_1)$, then the inequality 
(1) holds for
these values of $i_1$, \ldots, $k_r$.
\end{proposition}

\item 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:

\begin{conjecture}[Saturation conjecture]  If $(a_1, \ldots, c_r)$ are
integers, and there exists a honeycomb with
data $(a_1, \ldots, c_r)$, then there exists an integral honeycomb
with the same data.
\end{conjecture}

\item 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.

\item 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.

\ei

\page

Interpretation of integral honeycombs

\bi

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

\item If $a = (a_1, \ldots, 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, \ldots, -c_1)$, then the
representation $V_{c^*}$ occurs in the tensor product $V_a \otimes V_b$.
Equivalently, the tensor product $V_a \otimes V_b \otimes V_c$ contains
a $GL_n(\C)$-invariant vector.

\item 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 \otimes V_b$, or the dimension of the invariant
space of $V_a \otimes V_b \otimes V_c$.  This multiplicity
is known as a Littlewood-Richardson coefficient (or Clebsch-Gordan
coefficient), and has been extensively studied.

\item 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.

\item 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.

\ei

\page

Overlays

\bi

\item 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 = -\alpha(a) - \beta(b)$
for some permutations $\alpha$, $\beta$, then the honeycomb degenerates
to the overlay of $n$ honeycombs of order 1s.  

\item 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, \ldots, c_n)$.  We believe that this overlay operation
corresponds to the direct sum operation on the matrix level.

\item 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 honeycomb-based
proof of Horn's conjecture.  

\ei

\page

Proof of saturation

\bi

\item 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.

\item 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.

\item 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.
\ei
\end{document}
