LITTLEWOOD-RICHARDSON SEMIGROUPS

ANDREI ZELEVINSKY

Abstract. This note is an extended abstract of my talk at the workshop on Representation Theory and Symmetric Functions, MSRI, April 14, 1997. We discuss the problem of finding an explicit description of the semigroup LR_{r} of triples of partitions of length ≤ r such that the corresponding Littlewood-Richardson coefficient is non-zero. After discussing the history of the problem and previously known results, we suggest a new approach based on the “polyhedral” combinatorial expressions for the Littlewood-Richardson coefficients.

This note is an extended abstract of my talk at the workshop on Representation Theory and Symmetric Functions, MSRI, April 14, 1997. I thank the organizers (Sergey Fomin, Curtis Greene, Phil Hanlon and Sheila Sundaram) for bringing together a group of outstanding combinatorialists and for giving me a chance to bring to their attention some of the problems that I find very exciting and beautiful.

For r ≥ 1, let

P_{r} = {λ = (λ_{1}, …, λ_{r}) ∈ Z^{r} : λ_{1} ≥ ⋯ ≥ λ_{r} ≥ 0}

be the semigroup of partitions of length ≤ r. Our main object of study will be the set

LR_{r} = {(λ, μ, ν) : λ, μ, ν ∈ P_{r}, c_{μν}^{λ} > 0} ,

where c_{μν}^{λ} is the Littlewood-Richardson coefficient. Recall that P_{r} is the set of highest weights of polynomial irreducible representations of GL_{r}(C); if V_{λ} is the irreducible representation of GL_{r}(C) with highest weight λ then c_{μν}^{λ} is the multiplicity of V_{λ} in V_{μ} ⊗V_{ν}. Equivalently, the c_{μν}^{λ} are the structure constants of the algebra of symmetric polynomials in r variables with respect to the basis of Schur polynomials. We call LR_{r} the Littlewood-Richardson semigroup of order r; this name is justified by the following.

Theorem 1. LR_{r} is a finitely generated subsemigroup of the additive semigroup P_{r}^{3} ⊂ Z^{3r}.

This is a special case of a much more general result well known to the experts in the invariant theory. A short proof (valid for any reductive group instead of GL_{r}(C)) can be found in [E]; A. Elashvili attributes this proof to M. Brion and F. Knop. The semigroup property also follows at once from “polyhedral” expressions for c_{μν}^{λ} that will be discussed later.

This work is supported in part by NSF grant DMS-9625511; research at MSRI is supported in part by NSF grant DMS-9022140.

Problem A. Describe LR_{r} explicitly.

I have been interested in this problem for several years (e.g., in [BZ] the set {λ : (λ, δ, δ) ∈ LR_{r}} was determined, where δ = (r − 1, …, 1, 0); this proves a special case of Kostant’s conjecture). Practically nothing is known about the list of indecomposable generators of LR_{r} for general r. We will discuss the “dual” approach, namely we would like to describe the facets of the polyhedral convex cone LR_{r}^{R} ⊂ R^{3r} generated by LR_{r}. A remarkable progress in this direction was recently made by A. Klyachko in [K]. Before discussing his results, let us note that c_{μν}^{λ} is given by the classical Littlewood-Richardson rule (see e.g., [M]), which in principle makes Problem A purely combinatorial. In particular, the Littlewood-Richardson rule (or just the definition) readily implies the following properties of LR_{r}.

Homogeneity. |λ| = |μ| + |ν| for (λ, μ, ν) ∈ LR_{r}, where |λ| = λ_{1} + ⋯ + λ_{r}.

Stability. LR_{r+1} ∩ Z^{3r} = LR_{r}, where Z^{3r} = {(λ, μ, ν) ∈ Z^{3(r+1)} : λ_{r+1} = μ_{r+1} = ν_{r+1} = 0}. Even stronger, we have LR_{r+1} ∩ Z^{3r+2} = LR_{r}, where Z^{3r+2} = {(λ, μ, ν) ∈ Z^{3(r+1)} : λ_{r+1} = 0}.

Littlewood-Richardson semigroups appear naturally in several other contexts:

1. Hall algebra, extensions of abelian p-groups: see [M].

2. Schubert calculus on Grassmannians: see [F].

3. Polynomial matrices and their invariant factors: see [T].

4. Eigenvalues of sums of Hermitian matrices.

Let us discuss the last item in more detail. For a Hermitian matrix A of order r, let λ(A) denote the sequence of eigenvalues of A arranged in a weakly decreasing order (recall that A is Hermitian if A^{∗} = A, and such a matrix always has real eigenvalues). Let HE_{r} denote the set of triples (λ, μ, ν) ∈ R^{3r} such that λ = λ(A + B), μ = λ(A), and ν = λ(B) for some Hermitian matrices A and B of order r. The following counterpart of Theorem 1 for HE_{r} is highly non-trivial.

Theorem 2. HE_{r} is a polyhedral convex cone in R^{3r}.

Problem B. Describe HE_{r} explicitly.

Problems A and B are closely related to each other. They have a long history. Problem B was probably first posed by I.M. Gelfand in the late 40’s (eigenvalues of the sum of two Hermitian matrices were studied already by H. Weyl in 1912, but I believe I.M Gelfand was the first who suggested to study the cone HE_{r} as a whole rather than concentrate on individual eigenvalues). A solution was announced by V.B. Lidskii in [L1], but the details of the proof were never published. F.A. Berezin and I.M. Gelfand in [BG] discussed the relationships between Problems A and B; in particular, they suggested the following remarkable equality:

HE_{r} ∩ P_{r}^{3} = LR_{r}.  (1)

A. Horn in [H] solved Problem B for r ≤ 4 and conjectured a general answer. To formulate his conjecture we need some terminology. Let [1, r] denote the set {1, 2, …, r}. For a subset I = {i_{1} < i_{2} < ⋯ < i_{s}} ⊂ [1, r], we denote by ρ(I) ⊂ P_{s} the partition

ρ(I) = (i_{s} − s, …, i_{2} − 2, i_{1} − 1).

A triple of subsets I, J, K ⊂ [1, r] will be called HE-consistent if they have the same cardinality s and (ρ(I), ρ(J), ρ(K)) ∈ HE_{s}. For λ ∈ R^{r} and I ⊂ [1, r], we will write |λ|_{I} = ∑_{i∈I} λ_{i}; in particular, |λ|_{[1,r]} = |λ| = λ_{1} + ⋯ + λ_{r}.

Horn’s Conjecture. Let λ, μ, and ν be vectors in R^{r} with weakly decreasing components. Then (λ, μ, ν) ∈ HE_{r} if and only if |λ| = |μ| + |ν| and |λ|_{I} ≤ |μ|_{J} + |ν|_{K} for all HE-consistent triples (I, J, K) in [1, r].

The proofs of both Horn’s Conjecture and (1) were announced by B.V. Lidskii (not to be confused with the author of [L1]) in [L2]. Unfortunately, as in the case of [L1], the detailed proofs of the results in [L2] never appeared. This justifies A. Klyachko’s claim in [K] that even Theorem 2 has not been proved before.

Let us now discuss the results in [K]. First of all, A. Klyachko proves Theorem 2; moreover, he gives the following description of the facets of HE_{r}, which is very close (but not totally equivalent) to Horn’s Conjecture. Modifying the definition of HEconsistent triples. we will call a triple of subsets I, J, K ⊂ [1, r] LR-consistent if they have the same cardinality s, and (ρ(I), ρ(J), ρ(K)) ∈ LR_{s}.

Theorem 3. Horn’s conjecture becomes true if HE-consistency in the formulation is replaced by LR-consistency. Moreover, the inequalities |λ|_{I} ≤ |μ|_{J} + |ν|_{K} for all LR-consistent triples (I, J, K) in [1, r] are independent, i.e., they correspond to facets of the polyhedral convex cone HE_{r}.

A. Klyachko also proves the following weaker version of (1). Let LR_{r}^{Q} be the set of all linear combinations of triples in LR_{r} with positive rational coefficients; equivalently, LR_{r}^{Q} = ∪_{N≥1} \frac{1}{N} LR_{r}.

Theorem 4. HE_{r} ∩ Q_{≥0}^{3r} = LR_{r}^{Q}.

Theorems 3 and 4 appear in [K] as a by-product of the study of stability criteria for toric vector bundles on the projective plane P^{2}. In view of these theorems, the equality (1) and Horn’s Conjecture would follow from the affirmative answer to the following

Saturation Problem. Is it true that LR_{r}^{Q} ∩ P_{r}^{3} = LR_{r}?

In other words, does the fact that c_{Nμ,Nν}^{Nλ} > 0 for some N ≥ 1 imply that c_{μν}^{λ} > 0? This is true and easy to check for r ≤ 4. On the other hand, an obvious analogue of the problem for type B has negative answer (as pointed out to me by M. Brion, counterexamples can be found in [E]).

Examples. Here are the linear inequalities corresponding to LR-consistent triples for r ≤ 3; combined with the conditions λ_{1} ≥ ⋯ ≥ λ_{r}, μ_{1} ≥ ⋯ ≥ μ_{r}, ν_{1} ≥ ⋯ ≥ ν_{r}, and |λ| = |μ| + |ν|, they provide a description of the cone HE_{r}.

• r = 1: no inequalities;

• r = 2: λ_{1} ≤ μ_{1} + ν_{1}, λ_{2} ≤ min (μ_{1} + ν_{2}, μ_{2} + ν_{1});

• r = 3: λ_{1} ≤ μ_{1}+ν_{1}, λ_{2} ≤ min (μ_{1}+ν_{2}, μ_{2}+ν_{1}), λ_{3} ≤ min (μ_{1}+ν_{3}, μ_{2}+ν_{2}, μ_{3}+ν_{1}), λ_{1} + λ_{2} ≤ μ_{1} + μ_{2} + ν_{1} + ν_{2}, λ_{1} + λ_{3} ≤ min (μ_{1} + μ_{2} + ν_{1} + ν_{3}, μ_{1} + μ_{3} + ν_{1} + ν_{2}), λ_{2} + λ_{3} ≤ min (μ_{1} + μ_{2} + ν_{2} + ν_{3}, μ_{1} + μ_{3} + ν_{1} + ν_{3}, μ_{2} + μ_{3} + ν_{1} + ν_{2}). For instance, the inequality λ_{2} + λ_{3} ≤ μ_{1} + μ_{3} + ν_{1} + ν_{3} corresponds to the triple (I, J, K) = ({2, 3}, {1, 3}, {1, 3}), which is LR-consistent because the triple of partitions (ρ(I), ρ(J), ρ(K)) = ((1, 1), (1, 0), (1, 0)) obviously belongs to LR_{2}.

Assuming the affirmative answer in the Saturation Problem, Theorem 3 provides a recursive procedure for describing the semigroup LR_{r}. Although quite elegant, this procedure is not very explicit from combinatorial point of view. Thus, we would like to formulate the following

Problem C. Find a non-recursive description of LR_{r}.

Equivalently, Problem C asks for a non-recursive description of LR-consistent triples. We would like to suggest an elementary combinatorial approach to this problem based on the “polyhedral” expressions for the coefficients c_{μν}^{λ} given in [BZ]. To present such an expression, it will be convenient to modify Littlewood-Richardson coefficients as follows. We will consider triples (λ̄, μ̄, ν̄) of dominant integral weights for the group SL_{r}. Let Vλ̄ be the irreducible SL_{r}-module with highest weight λ̄, and let cλ̄μ̄ν̄ denote the dimension of the space of SL_{r}-invariants in the triple tensor product Vλ̄ ⊗ Vμ̄ ⊗ Vν̄. The relationship between the cλ̄μ̄ν̄ and the Littlewood-Richardson coefficients is as follows. We will write each of the weights λ̄, μ̄ and ν̄ as a nonnegative integer linear combination of fundamental weights ω_{1}, ω_{2}, …, ω_{r−1} (in the standard numeration):

λ̄ = l_{1}ω_{1}+⋯+l_{r−1}ω_{r−1}, μ̄ = m_{1}ω_{1}+⋯+m_{r−1}ω_{r−1}, ν̄ = n_{1}ω_{1}+⋯+n_{r−1}ω_{r−1}. (2)

The definitions readily imply that if λ, μ, ν ∈ P_{r} are such that |λ| = |μ| + |ν| then c_{μν}^{λ} = cλ̄μ̄ν̄, where the coordinates l_{s}, m_{s} and n_{s} in (2) are given by

l_{s} = λ_{r−s} − λ_{r−s+1}, m_{s} = μ_{s} − μ_{s+1}, n_{s} = ν_{s} − ν_{s+1}.  (3)

Thus, the knowledge of LR_{r} is equivalent to the knowledge of the semigroup

\overline{LR}_{r} = \{(λ̄, μ̄, ν̄) ∈ Z_{≥0}^{3(r−1)} : cλ̄μ̄ν̄ > 0\}.

Passing from LR_{r} to \overline{LR}_{r} has two important advantages. First, the coefficients cλ̄μ̄ν̄ are more symmetric than the original Littlewood-Richardson coefficients: they are invariant under the 12-element group generated by all permutations of three weights λ̄, μ̄ and ν̄, together with the transformation replacing each of these weights with its dual (i.e., sending (l_{s}, m_{s}, n_{s}) to (l_{r−s}, m_{r−s}, n_{r−s})). Second, the dimension of the ambient space reduces by 2, from 3r − 1 to 3(r − 1). On the other hand, \overline{LR}_{r} has at least one potential disadvantage: the condition |λ| = |μ| + |ν| is replaced by a more complicated condition that ∑_{s} s(l_{s}+m_{s}+n_{s}) is divisible by r (in more invariant terms, this means that λ̄ + μ̄ + ν̄ must be a radical weight, i.e., belongs to the root lattice). To illustrate both phenomena, one can compare the description of LR_{2} given above with the following description of \overline{LR}_{2} which is equivalent to the classical Clebsch-Gordan rule: \overline{LR}_{2} consists of triples of nonnegative integers (l_{1}, m_{1}, n_{1}) satisfying the triangle inequality and such that l_{1} + m_{1} + n_{1} is even.

Let us now give a combinatorial expression for cλ̄μ̄ν̄ (this is one of several such expressions found in [BZ]). Consider a triangle in R^{2}, and subdivide it into small triangles by dividing each side into r equal parts and joining the points of the subdivison by the line segments parallel to the sides of our triangle. Let Y_{r} denote the set of all vertices of the small triangles, with the exception of the three vertices of the original triangle. Introducing barycentric coordinates, we identify Y_{r} with the set of integer triples (i, j, k) such that 0 ≤ i, j, k < r and i + j + k = r. Let Z^{Y_{r}} be the set of integer families (y_{ijk}) indexed by Y_{r}; we think of y ∈ Z^{Y_{r}} as an integer “matrix” with Y_{r} as the set of “matrix positions.” To every y ∈ Z^{Y_{r}} we associate the partial line sums

l_{ts}(y) = ∑_{j=t}^{s} y_{r−s,j,s−j}, m_{ts}(y) = ∑_{k=t}^{s} y_{s−k,r−s,k}, n_{ts}(y) = ∑_{i=t}^{s} y_{i,s−i,r−s},  (4)

where 0 ≤ t ≤ s ≤ r. We call these linear forms on R^{Y_{r}} tails, and we say that y ∈ R^{Y_{r}} is tail-positive if all tails of y are ≥ 0. We also say that a linear form on R^{Y_{r}} is tail-positive if it is a nonnegative linear combination of tails.

Theorem 5. For any triple (λ̄, μ̄, ν̄) as in (2), the coefficient cλ̄μ̄ν̄ is equal to the number of tail-positive y ∈ Z^{Y_{r}} with prescribed values of line sums

l_{0s}(y) = l_{s}, m_{0s}(y) = m_{s}, n_{0s}(y) = n_{s} (1 ≤ s ≤ r − 1).  (5)

In other words, let T_{r} ⊂ Z^{Y_{r}} denote the semigroup of tail-positive elements, and let σ : Z^{Y_{r}} → Z^{3(r−1)} be the projection given by (5). Then Theorem 5 says that

σ(T_{r}) = \overline{LR}_{r}.  (6)

In particular, this implies at once that \overline{LR}_{r} (and hence LR_{r}) is a semigroup. Furthermore, Theorem 5 implies the following description of the convex cone \overline{LR}_{r}^{R} generated by \overline{LR}_{r}.

Corollary 6. A linear form f on R^{3(r−1)} takes nonnegative values on \overline{LR}_{r}^{R} if and only if the form f ∘ σ on R^{Y_{r}} is tail-positive.

Returning to the Littlewood-Richardson semigroup LR_{r}, we have the projection ∂ : LR_{r} → \overline{LR}_{r} given by (3). This projection extends by linearity to a projection ∂ : R^{3r−1} → R^{3(r−1)}, where R^{3r−1} is the subspace of triples (λ, μ, ν) ∈ R^{3r} satisfying |λ| = |μ|+|ν|. It is clear that the cone LR_{r}^{R} ⊂ R^{3r−1} is given by the linear inequalities f ∘ ∂ ≥ 0 for all linear forms f as in Corollary 6. This suggests the following strategy for determining the set of LR-consistent triples. Take a triple of subsets (I, J, K) in [1, r] of the same cardinality s, consider the corresponding linear form |μ|_{J} + |ν|_{K} − |λ|_{I} on R^{3r−1}, write this form as f ∘ ∂, and compute the form f ∘ σ on R^{Y_{r}}. A straightforward calculation gives

(f ∘ σ)(y) = ∑_{(i,j,k)∈Y_{r}}(#(I_{>i}) − #(J_{>r−j}) − #(K_{>r−k})) y_{ijk},  (7)

where #(I_{>i}) stands for the number of elements of I which are > i. Taking into account Theorem 3, we obtain the following criterion for LR-consistency.

Theorem 7. A triple of subsets (I, J, K) of the same cardinality s in [1, r] is LRconsistent if and only if |ρ(I)| = |ρ(J)| + |ρ(K)| and the form in (7) is tail-positive.

In particular, since every tail-positive linear form is obviously a nonnegative linear combination of the y_{ijk}, we obtain the following necessary condition for LRconsistency.

Corollary 8. If a triple of subsets (I, J, K) in [1, r] is LR-consistent then

#(I_{>i}) ≥ #(J_{>r−j}) + #(K_{>r−k})  (8)

for all (i, j, k) ∈ Y_{r}.

It would be interesting to deduce this corollary directly from the Littlewood-Richardson rule. One can show that (8) is not sufficient for LR-consistency. In fact, Theorem 7 can be used to produce other necessary conditions for LR-consistency. One can hope to solve Problem C by generating a system of necessary and sufficient conditions for LR-consistency using this method.

References

[BG] F.A. Berezin, I.M. Gelfand, Some remarks on spherical functions on symmetric Riemannian manifolds, Tr. Mosk. Mat. Obsch., 5 (1956), 311-351.

[BZ] A. Berenstein, A. Zelevinsky, Triple multiplicities for sl(r+1) and the spectrum of the exterior algebra of the adjoint representation, J. Alg. Comb., 1 (1992), 7 - 22.

[E] A.G. Elashvili, Invariant algebras, Advances in Soviet Math., 8 (1992), 57-64.

[F] W. Fulton, Young tableaux, Cambridge University Press, 1997.

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

[K] A.A. Klyachko, Stable vector bundles and Hermitian operators, IGM, University of Marnela-Vallee preprint (1994).

[L1] V.B. Lidskii, On the characteristic numbers of the sum and product of symmetric matrices, Dokl. Akad. Nauk USSR, 75 (1950), 769-772.

[L2] B.V. Lidskii, Spectral polyhedron of the sum of two Hermitian matrices, Funct. Anal. Appl., 16 (1982), 139-140.

[M] I.G. Macdonald, Symmetric functions and Hall polynomials, Second Edition, Clarendon Press, Oxford, 1995.

[T] R.C. Thompson, Divisibility relations satisfied by the invariant factors of a matrix product, Operator Theory, Advances and Applications, 40, Birkhauser, 1989.

Andrei Zelevinsky, Department of Mathematics, Northeastern University, Boston, MA 02115

  E-mail address: andrei@neu.edu