\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}