# Honeycombs from Hermitian matrix pairs, with interpretations of path operators and S [L.sub.n] crystals.

1 Introduction

In Horn [2] the following problem was considered: characterize the possible spectra ([mu], v, [lambda]) of a triple of Hermitian matrices (M, N, L), where M + N + L = 0. Horn proposed a recursively defined set of inequalities whose solutions would determine such spectra. Many contributions went into proving this conjecture, culminating in the work of Knutson and Tao [4] where they established the "Horn Theorem", namely, if a Hermitian triple (M, N, L) exists, then their respective spectra ([mu], v, [lambda]) would form the edge weights for a combinatorial object called a hive, or equivalently, it was shown, a weighted graph called a honeycomb (again, with edge weights ([mu], v, [lambda])). The proof of the Horn Theorem depended on some deep connections to representation theory and symplectic geometry. They also proved the "Honeycomb Theorem", that the edge weights of hives and honeycombs satisfy Horn's inequalities. This was proved by means of some ingenious combinatorial ideas and methods in convex geometry.

However, an explicit map from Hermitian triples (M, N, L) to a hive was not established, though by studying special cases it seemed likely that under any such map, Hermitian triples composed of simultaneous direct sums of blocks should correspond to the overlay of their associated honeycombs. Indeed, in a later paper Knutson, Tao, and Woodward [5] wrote: "...The analogy between the Hermitian direct sum operation and the honeycomb overlay operation is even tighter than this: at the critical values of "take eigenvalues" that are not at extrema, one also finds transverse overlays, and the index of the Hessian can be computed from the number of intersections that are clockwise. However, until a tighter connection is found someday in the form of, say, a measure-preserving map from zero-sum Hermitian triples to the polytope of honeycombs, the Hermitian and honeycomb theorems will have to be proven independently."

Subsequent work by Speyer[8] studied the relationship between Hermitian triples and hives, and showed that, in a sense, the tropicalization of the Vinnikov curve det(xM + yN + zL) = 0 produced a hive which satisfied the overlay property. The proof utilized not only tropical geometry (and the methods of Viro's patchworking techniques) but studied the problem over power series rings so that methods from logic could help determine the the behavior of curves under the tropicalization process.

Here, we present an explicit construction of hives from Hermitian matrices whose proofs require little more than linear algebra. Because hives and honeycombs already have connections to problems in representation theory, we have the means to study these problems in new ways. In particular, we shall show how the dynamics of Hermitian matrices under rotations of eigenvectors illuminates some basic constructions in the theory of crystal graphs and path operators associated to the representation theory of S [L.sub.n](C)

2 From Hermitian Matrix Pairs to Hives and Honeycombs

DEFINITION 2.1 Let W be an n-dimensional complex vector space, and let p, q be two non-negative integers, p [less than or equal to] q [less than or equal to] n. The we shall denote by

[F.sub.pq](W)

the set of all pairs of subspaces (U, V) of W such that U [subset or equal to] V, dim(U) = p, and dim(V) = q.

It is, of course, only necessary to consider the pair of Hermitian matrices (M, N), from which we may always determine the third matrix L of the triple. Given a Hermitian operator M on a vector space V with a subspace U [subset or equal to] V, let [pr.sub.U]: V [right arrow] U denote the orthogonal projection, and then denote by [M.sub.U] the Hermitian operator on U given by [M.sub.U] = [pr.sub.U] [omicron] M [omicron] [pr.sub.U]. With this, we have the following:

THEOREM 2.2 For any pair of r x r Hermitian matrices M and N, let us set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where i = r - j - k. Then the numbers H (M, N) = {[H.sub.ijk]} form a hive (in the sense of Knutson and Tao [4]).

Furthermore, let [sigma](M) denote the spectrum of a Hermitian matrix M. If [sigma](M) = [mu], [sigma](N) = v, and [sigma](M + N) = [lambda], then the hive H(M, N) = {[H.sub.ijk]} is of type ([mu], v, [lambda]).

DEFINITION 2.3 A hive of size r is a triangular array of numbers [([H.sub.ijk]).sub.i+j+k=r] that satisfy the rhombus inequalities:

1. (right) [H.sub.ijk] + [H.sub.(i+1)(j-2)(k+1)] [less than or equal to] [H.sub.(i+i)(j-i)k] + [H.sub.i(j-1)(k+1)].

2. (left) [H.sub.ijk] + [H.sub.(i+1)(j+1)(k-2)] [less than or equal to] [H.sub.(i+1)j(k-1)] + [H.sub.i(j+1)(k-1)].

3. (top) [H.sub.ijk] + [H.sub.(i-2)(j+1)(k+1)] [less than or equal to] [H.sub.(i-1)(j+1)k] + [H.sub.(i-1)j(k+1)].

A hive of size 5 is depicted below.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that we will typically normalize hives so that [H.sub.r00] = 0.

The rhombus inequalities are so named because the terms in each inequality form a rhombus in the hive, made by adjacent entries in the array such that that the upper acute angle points to the right, vertically, and to the left, respectively. In each case the inequality asserts that the sum of the entries of the obtuse vertices of the rhombus is greater than or equal to the sum of the acute vertices.

Let HIVE denote the set of nonnegative integer-valued hive. We shall say a hive H is of type [tau](H) = ([mu], v, [lambda]) (for sequences of nonnegative integers [mu], v, and [lambda] of length r) when

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let

Hive([mu], v, [lambda]) = {H [member of] HIVE: [tau](H) = ([mu], v, [lambda])}.

As a consequence of the rhombus inequalities, the type of a hive H will be a triple of partitions of weakly decreasing nonnegative integers and, thus, form a triple of partitions, referred to as the edge weighs of the hive. Given our choice of determining the edge weights, a necessary condition for the existence of a hive H [member of] HIVE([mu], v, [lambda]) is:

[absolute value of [mu]] + [absolute value of v] = [absolute value of [lambda]].

This choice of edge weights will necessitate that we study Hermitian triples (M, N, L) of the form M + N = L, instead of triples that sum to zero. The choice is in many ways arbitrary, and this one has been adopted to make formulas involving Littlewood-Richardson coefficients [c.sup.[lambda].sub.[mu]v], for which [absolute value of [mu]] + [absolute value of v] = [absolute value of [lambda]] hold as well, more tractable.

Let us now outline some of the elements of the proof of Theorem 2.2. Let us first recall the variational definition of eigenvalues. In particular, if M is an operator on a vector space W of dimension r, with eigenvalues [[mu].sub.1] [greater than or equal to] [[mu].sub.2] [greater than or equal to] *** [greater than or equal to] [mu], then for every k with 0 < k [less than or equal to] r we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

So, along the left side of the hive we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

while along the bottom row of the hive we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and along the right slope

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using the boundary values described above, we see Theorem 2.2 yields a hive of the required type, provided it is a hive. Thus, it remains to prove the rhombus inequalities. We will sketch the method of proof. For example, to prove the "right"-slanted inequality:

[H.sub.ijk] + [H.sub.(i+1)(j-2)(k+1)] [less than or equal to] [H.sub.(i+1)(j-1)k] + [H.sub.i(j-1)(k+1)],

we first find subspaces that realize the maxima of the left hand side of the inequality. That is, find two subspace pairs ([U.sup.*], [V.sup.*]) and ([U.sup.**], [V.sup.**]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By dimension counting arguments we construct orthonormal bases of the [U.sup.*], [V.sup.*], [U.sup.**], [V.sup.**] so that by rearranging the basis elements, we build two more subspace pairs U', V', U", V" such that the union of the bases for the [U.sup.*], [V.sup.*], [U.sup.**], [V.sup.**] equals the union of the bases of the U', V', U", V", but further such that

(U', V') [member of] [F.sub.(j-1)(j+k-1)] and (U", v") [member of] [F.sub.(j-1)(j+k)].

From this, we then conclude

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The other rhombus inequalities follow similarly. Such techniques are currently being investigated by the authors to provide simpler means to associate hives as invariants of matrix problems in other settings, such as generalizing earlier results (see [3]) associating Littlewood-Richardson fillings to matrix pairs over discrete valuation rings to pid's and other integral domains. The simplicity of the construction, along with the overlay property (to be discussed below), suggests some approaches to providing a more self-contained proof of the Horn conjectures. We shall also see that relating rotations of eigenvectors to the dynamics of the hive structures suggests a constructive proof of the sufficiency of the inequalities. These ideas will be developed more fully below.

As before, we let Hive([mu], v, [lambda]) denote the set of hives of type ([mu], v, [lambda]). With this, let us set:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

There are numerous bijections from Hive([mu], v) to other sets of combinatorial interest, also indexed by partitions. Let us begin with honeycombs.

Honeycombs are finite, trivalent graphs whose edges are assigned weights of "zero-tension". In fact, we may think of a honeycomb as lying on the plane S = {(x, y, z) [member of] [R.sup.3]: x + y = z}. Every edge of a honeycomb has its x, y, or z coordinate constant along that edge, and we assign the weight of the edge this constant coordinate. Under Knutson and Tao's map from hives to honeycombs, the weights along the left side of the honeycomb correspond to u, along the bottom to v, and along the right side to T, as they do in the hive:

In [1] Danilov and Koshevoy proved that the overlay of two honeycombs corresponds to the convolution of the associated hives, that is if H = {[H.sub.ijk]} and H' = {[H'.sub.ijk]} are two hives, with associated honeycombs Hon and Hon', then the overlay of Hon and Hon' corresponds to the hive H * H', given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As mentioned above, it has long been thought the overlay of honeycombs should correspond to the direct sums of matrix blocks. This turns out to be the case. We present the (quite short) proof in full:

THEOREM 2.4 Let [M.sub.1] and [N.sub.1] be two s x s Hermitian matrices, and let [M.sub.2] and [N.sub.2] be two t x t Hermitian matrices. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: Define B as the s-dimensional space on which [M.sub.1] and [N.sub.1] both act, and similarly let C be the t- dimensional orthogonal complement on which [M.sub.2] and [N.sub.2]. act. Then we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Corollary 2.5 The honeycomb corresponding to the direct sum of pairs of Hermitian matrices is the overlay of the honeycombs corresponding to each summand.

3 Applications to Crystals and Littelmann Operators

The original work of Knutson and Tao [4] describes the bijection between hives and honeycombs. Pak and Vallejo [7] constructed several interesting combinatorial bijections, and in particular determined the maps from hives of type ([mu], v, [lambda]) and Littlewood-Richardson fillings of the skew shape [lambda]/[mu] with content v, which determine the Littlewood-Richardson coefficient cpv. Littelmann [6] considered another combinatorial enumeration of [c.sup.[lambda].sub.[mu]v] via a class of semi-standard, p-dominant tableaux of shape v. Let SSYT(v) denote the set of all semi-standard tableaux of shape v. Then we have:

DEFINITION 3.1 1. Given a semi-standard Young tableau T [member of] SSTY([mu]), we will define the weight of T, denoted wt(T), as the sequence of non-negative integers ([a.sub.1], [a.sub.2], ...) where [a.sub.i] is the number of i's that appear in T. More generally, given any finite set of tableaux S = {[T.sub.1], [T.sub.2], ...} where we allow the elements of S to have different shapes, we shall let wt(S) = ([a.sub.1], [a.sub.2], ...) denote the joint weight of S where [a.sub.i] equals the total number of i's appearing in all the elements of S.

2. Given a tableau T [member of] SSYT (v), we will let [T.sup.(i)] denote the semi-standard tableau obtained from T by removing its first i columns. We set [T.sup.(0)] = T.

3. We say a tableau T [member of] S STY (v) is [mu]-dominant if the composition wt({[max.sub.[mu]], [T.sup.(i)]}), for all i [greater than or equal to] 0 and less than the number of columns of T, is also a partition.

4. Let LRTab([mu], v) denote the set of all [mu]-dominant semi-standard tableaux of shape v

THEOREM 3.2 ([6]) Let [c.sup.[lambda].sub.[mu]v] denote the classical Littlewood-Richardson coefficient. Then

[c.sup.[lambda].sub.[mu]v] = #{T [member of] LRTab([mu], v): wt({[max.sub.[mu]], T}) = [lambda]}.

Littelmann [6] analyzed the combinatorics of Littlewood-Richardson coefficients and crystals associated to the representation theory of S[L.sub.n](C) by the action of operators (there called path operators). We will not need the entire strength of that theory, and will content ourselves with the action of Littelmann operators on elements of SS YT(v). In what follows, we shall use the symbol [??] to represent a null or empty tableau.

DEFINITION 3.3 Let v be a partition with r rows. For each i, 1 [less than or equal to] i [less than or equal to] r - 1, let us define a map [f.sub.i]: SS YT(v) [right arrow] SSYT(v) [union] {[??]} by

[f.sub.i](T) = T',

where T' is the tableau obtained by finding in T the top-most, right-most i in T that is not over an i + 1, and changing this i to an i + 1. If no such i exists, then T' = [??].

DEFINITION 3.4 Given a partition v, let [max.sub.v] denote the element [max.sub.v] [member of] SSYT (v) whose first row is [v.sub.1]-many 1's, whose second row is [v.sub.2]-many 2's, etc.

THEOREM 3.5 ([6]) The set SSYT (v) [union] {[??]} is spanned by the image of [max.sub.v] under all finite applications of the Littelmann operators [f.sub.i], 1 [less than or equal to] i [less than or equal to] r - 1.

The set of images of [max.sub.v] under the [f.sub.i] can be regarded as a model for a type of crystal, and the exploration of these ideas has resulted in an enormous deepening of our understanding of representations of algebraic and Lie groups, along with their quantized generalizations. Our needs, however, will be more prosaic, and will be adapted to the application of Littelmann operators to the study of Littlewood-Richardson coefficients.

Let us fix [mu] = [12,6,0] and v = [5,3,0]. Then, for example, the action of the [f.sub.1] on [max.sub.v] produces

while the action of [f.sub.2] on [max.sub.v] produces

If we replace these images in Honey([mu], v) we find

so its images under the map [f.sub.1] become:

Not the lower "rank-one" honeycomb that is fixed under the deformation. The images of Hon([max.sub.v]) under the map [f.sub.2] become:

Here, the upper rank-one honeycomb is preserved.

We will, therefore, represent the images of LRTab([mu], v), Honey([mu], v) in the "dominant chamber" of the plane D = {([[lambda].sub.1], [[lambda].sub.2], [[lambda].sub.3]) [member of] [R.sup.3]: [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] > [[lambda].sub.3]}, sending each object to the partition [lambda] the object determines. We will denote the (common) image of these sets [LAMBDA]([mu], v). We will not plot the image of th entire crystal of [mu] = [12,6,0] and v = [5,3,0] in [LAMBDA]([mu], v), but will show its boundary, with a few interior points. As a set in D, the boundary of the crystal would be constructed as:

Plotting the honeycombs under the deformations induced from the Littelmann operators we obtain:

In the interior of the diagram, which we do not depict here, multiplicities in Littlewood-Richardson coefficients are represented by finding multiple paths that result in different honeycombs (corresponding to distinct Littlewood-Richardson fillings) for which the same [lambda] denotes the right-hand edge weight of the honeycomb. The portions of the graph printed in black denote the overlaid honeycomb that is fixed along the path each edges deformation. The right edge of the honeycomb has weights given by [lambda], for a partition such that [absolute value of [lambda]] = [absolute value of [mu]] + [absolute value of v]. Moving along the path of the [f.sub.1] operator, we see [[lambda].sub.1] decrease by one, [[lambda].sub.2] increase by one, and A3 remain fixed. Along the [f.sub.2]-deformation path (moving upward to the left), we see [[lambda].sub.1] remain fixed (as part of a fixed rank-one honeycomb), while [[lambda].sub.2] decreases and [[lambda].sub.3] increases. However, the deformation paths that slant upward and to the right are not the result of a deformation of a single Littelmann operator. The lower right upward sloping path is the result of repeated applications of the composition [f.sub.1] [omicron] [f.sub.2], that is, first moving up and left, and then horizontally to the right. The left-hand upward path is obtained by application of [f.sub.2] [omicron] [f.sub.1], first moving horizontally along the right, then upward to the left. However, in both cases, we see that the associated honeycomb deformation is the result first fixing an inner rank-one honeycomb, whose [lambda]-value is just [[lambda].sub.2], with a deformation of the other two, in which [[lambda].sub.1] decreases and [[lambda].sub.3] increases.

We find that, in all cases, moving in the [f.sub.1]-direction produces a deformation that "pinches" [[lambda].sub.1] and [[lambda].sub.2] closer together, while the [f.sub.2] operator produces a deformation path that pinches [[lambda].sub.2] and [[lambda].sub.3]. Moving along any composition [f.sub.1] [omicron] [f.sub.2] or [f.sub.2] [omicron] [f.sub.1] pinches [[lambda].sub.1] and [[lambda].sub.3].

This can be interpreted, perhaps more simply, by generating this graph (crystal) by the honeycomb image of Hermitian matrices under rotations of their eigenvectors. For our example of [mu] = [12,6,0] and v = [5, 3,0] we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We then define the rotation matrices

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let Hon(M, N) denote the honeycomb associated to any Hermitian matrix pair (via its associated hive). We the obtain deformations of honeycombs that correspond to the conjugation of N by the [U.sub.i]([theta]). So, for example, along the [U.sub.1]-deformation path given by Hon(M, N) [??] Hon [M, [U.sub.1]([theta]) x N x [U.sub.1][([theta]).sup.-1] we obtain

while along the [U.sub.2] deformation path we see

Further, both of the deformation paths moving upwards to the right are the result of the rotation deformation under [U.sub.3](0) defined above, each applied to a different starting matrix. We see that the endpoints of the crystal [LAMBDA](u, v) all correspond to the spectra of the sum of diagonal matrices or, equivalently by the overlay property, to honeycombs that are overlays of rank-one honeycombs. Indeed, the endpoint of Hon([max.sub.v]) under the [U.sub.3]([theta]) deformation corresponds to the matrix whose diagonal writes the partition v in the order reverse to that of [mu], which we will call [min.sub.v]. The diagonal path from Hon([max.sub.v]) to Hon([min.sub.v]) is therefore the result of a "single" deformation fixing a rank-one honeycomb containing [[lambda].sub.2].

The hexagon shape of [LAMBDA]([mu], v) is the result, however, of the fact that all tableau in SSYT(v) are [mu]- dominant, that is, SSYT (v) = LRTab([mu], v). In this case, we actually obtain the crystal associated to the partition v in the representation theory of S[L.sub.3] (see [6]). In other words, we obtain a copy of this crystal by plotting the deformation paths of honeycombs for any [mu] for which SSYT(v) = LRTab([mu], v), and embedding interpreting these objects via rotations of eigenvectors yields a new avenue to their study. However, in the case that SSYT(v) [not equal to] LRTab([mu], v), we may obtain a wide variety of shapes for [LAMBDA]([mu], v). Let us consider, for example, the example [mu] = [10, 3,2] and v = [5,3,2]. In this case the convex set [LAMBDA]([mu], v) has a very different form:

Note, in particular, the path taking Hon([max.sub.v]) does not lie on a straight line. If we proceed from Hon([max.sub.v]) in the "northeast" direction, we reach a honeycomb on the boundary of [LAMBDA]([mu], v) on the opposite side, but must then move one unit along in the "[f.sub.1]" direction to reach Hon([min.sub.v]). What has happened? In fact, if we look at the honeycomb deformations along this "bent" path from Hon([max.sub.v]) to Hon([min.sub.v]) we find:

This path becomes bent because now that some tableau in SSYT(v) are not in LRTab([mu], v), as we move far enough along in the deformation path we cross the "chamber wall", in this case the boundary [[lambda].sub.2] = [[lambda].sub.3]. Initially we move from Hon([max.sub.v]) along the deformation path and see the [[lambda].sub.1] part decreasing and the [[lambda].sub.3] part increasing, keeping the rank-one honeycomb containing the A2 part fixed. At the moment that [[lambda].sub.2] = [[lambda].sub.3], the parts pass through each other, and now the fixed rank-one honey comb contains the [[lambda].sub.3] part, while it had been the [[lambda].sub.2] just a moment before in the deformation. The part which had been [[lambda].sub.3] now becomes a [[lambda].sub.2] part, so the deformation "turns right" and proceeds as a deformation in the [f.sub.1] direction.

We see here that the honeycomb deformation structure can reveal features not evident form other approaches to characterizing the crystal structure, and using the image of the deformation paths given by rotations of associated Hermitian matrix pairs makes shows that a lot of the machinery for studying crystals (or their counterparts in MV polytopes, LS galleries, etc.) is often necessitated by forcing a given combinatorial structure to live in the dominant chamber, while the underlying path dynamics (following a single rotation) may be easier to analyze without this constraint.

These examples also demonstrate some avenues for further study. Not only do the honeycomb images of Hermitian matrices in Honey([mu], v) give us a continuous interpolation between integer-valued honeycombs determined by their discrete counterparts, but the structure also suggests a natural method to invert the process, and from a given honeycomb (Littlewood-Richardson filling, hive, etc.), one may traverse a deformation path in Honey([mu], v) and pull back the deformation as a series of rotations applied to the diagonal matrix N associated to [max.sub.v] to produce an actual Hermitian pair that gives rise to a given honeycomb. In particular, this approach will solve the problem of proving the sufficiency of the Horn inequalities, and provide a constructive solution to the problem of realizing a Hermitian pair with prescribed spectra for their sum.

References

[1] V.Danilov, G. Koshevoy. "Discrete convexity and Hermitian matrices." Trudy Matematicheskogo Instituta im. VA Steklova 241 (2003): 68-89.

[2] A. Horn, "Eigenvalues of sums of Hermitian matrices", Pacific J. Math. 12, pp. 225-241, (1962).

[3] T. Klein, "The multiplication of Schur functions and extension of p-modules" J. London Math. Soc., vol. 43, (1968), pp. 280-284.

[4] A. Knutson and T. Tao, "The honeycomb model of [GL.sub.N](C) tensor products I: Proof of the saturation conjecture", J. Amer. Math. Soc. vol. 12, (1999), pp. 1055-1090.

[5] A. Knutson, T. Tao, and C. Woodward, "The honeycomb model of [GL.sub.n] tensor products II: Facets of the Littlewood-Richardson cone", J. Amer. Math. Soc. 17 (2004), no. 1, 19-48.

[6] P. Littelmann, "The path model, the quantum Frobenius map and standard monomial theory." Algebraic groups and their representations. Springer Netherlands, (1998), 175-212.

[7] I. Pak and E. Vallejo, "Combinatorics and geometry of Littlewood-Richardson Cones", Europ. J. Combinatorics, 26, (2005), pp. 995-1008.

[8] D. Speyer, "Horn's Problem, Vinnikov Curves and Hives", Duke Journal of Mathematics 127 no. 3 (2005), p. 395-428.

Glenn Appleby * and Tamsen Whitehead ([dagger])

Santa Clara University, Santa Clara, California, USA

* Email: gappleby@scu.edu.

([dagger]) Email: tmcginley@scu.edu.