AGNIHOTRI-WOODWARD-BELKALE POLYTOPE

AND THE INTERSECTION OF KLYACHKO CONES

S.Yu. Orevkov, Yu.P. Orevkov

Abstract. Agnihotri-Woodward-Belkale polytope Δ (resp. Klyachko cone K) is the set of solutions of the multiplicative (resp. additive) Horn’s problem, i.e., the set of triples of spectra of special unitary (resp. traceless Hermitian) n × n matrices satisfying AB = C (resp. A + B = C). K is the tangent cone of Δ at the origin. The group G = ℤ_{n} ⊕ ℤ_{n} acts naturally on Δ.

In this note, we report on a computer calculation which shows that Δ coincides with the intersection of gK, g ∈ G, for n ≤ 14 but does not coincide for n = 15.

Our motivation was an attempt to understand how to solve the multiplicative Horn problem in practice for given conjugacy classes in SU(n).

Introduction

For a special unitary matrix A ∈ SU(n), let us denote by λ(A) its spectrum i.e. the vector (λ_{1}, …, λ_{n}) ∈ ℝ^{n} which is uniquely defined by the conditions

λ_{1} + ⋯ + λ_{n} = 0,  λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n−1} ≥ λ_{n} ≥ λ_{1} − 1,  (1)

and exp(2πiλ_{1}), …, exp(2πiλ_{n}) are the eigenvalues of A. The mapping λ : SU(n) → ℝ^{n} identifies conjugacy classes of SU(n) with points of the (n − 1)-simplex 𝔄 given by (1). This simplex is called Weyl alcove of SU(n). It sits in the Weyl chamber 𝔱_{+} defined by (1) with the last inequality excluded.

Agnihotri-Woodward [1] and Belkale [2] obtained necessary and sufficient conditions on three vectors α, β, γ for the existence of matrices A, B, C ∈ SU(n) such that α = λ(A), β = λ(B), γ = λ(C), and AB = C. They have shown that the image of the mapping Λ : SU(n)^{2} → 𝔄^{3}, (A, B) ↦ (λ(A), λ(B), λ(AB)), is a polytope Δ ⊂ 𝔄^{3} explicitely described in terms of quantum Schubert calculus (see §1).

This result is a generalization of Klyachko’s solution [8] of Horn’s problem (see an excellent survey [7]). Namely, Klyachko have described the set K of all triples of n-vectors realizable by spectra of traceless Hermitian matrices A, B, and A+B. Of course, K is the tangent cone of Δ at the origin O of ℝ^{3n}. Its facets are described in terms of the classical Schubert calculus. We call Δ and K the Agnihotri-Woodward-Belkale polytope and the Klyachko cone respectively.

How to apply these results in practice? Suppose, we have a concrete unitary matrix C and we ask if it is realizable as a product of matrices of given conjugacy classes (see [12] for an example of applications). Though there exists a finite set of inequalities to check, the number of them grows exponentially and, for matrices, say, 30 × 30 there is no chance to generate all inequalities in a reasonable time. This concerns both additive and multiplicative problems. However, for the additive

Typeset by AMS-TEX

problem, the honeycomb description of K due to Knutson and Tao [9, 10] allows to reduce the problem to the existence of a solution of 3\binom{n}{2} simultaneous linear inequalities on \binom{n−1}{2} variables (see also [6]). The same problem for k matrices is reduced to the existence of a solution of 3(k − 2)\binom{n}{2} inequalities on (k − 2)\binom{n−1}{2} + (k − 3)(n − 1) variables. For the multiplicative problem, such a reduction seems to be unknown (see [14]). This is why we study when the multiplicative problem can be reduced to the additive problem.

Let I be the identity n × n matrix and let ω = exp(2πi/n). Easy to see that 𝔄 is the convex hull of λ(Z) where Z = {ω^{k}I} is the center of SU(n). Moreover, the action of Z on SU(n) by multiplication induces affine linear actions of Z on 𝔄 and of G = Z × Z on Δ. This yields natural lower and upper estimates for Δ:

conv(GO) ⊂ Δ ⊂ Δ_{K}  where Δ_{K} = ⋂_{g∈G} gK  (2)

(“conv” stands for the convex hull; GO = {gO | g ∈ G} = Λ(G)). Are these estimates sharp? For the lower estimate, this question was asked and answered in [2; Sect. 7]. The answer is: the equality conv(GO) = Δ holds for n ≤ 3 and it fails for n = 4. For the upper estimate, we ask and answer this question in this note. The answer is: the equality Δ = Δ_{K} holds for n ≤ 14 and it fails for n = 15.

Agnihotri and Woodward [1; Sect. 8] discuss the action of G on Δ and its relation with a hidden symmetry of Gromov-Witten invariants. In particular, they point out that the action of G allows to reduce degree d invariants to degree zero invariants for small values of n (which implies Δ = Δ_{K} for those n), but, for n = 10, they give an example where the reduction is impossible. In terms of the polyhedra Δ and Δ_{K}, this means that for n = 10, among the inequalities which are used in [1] for Δ, there is at least one which cannot be reduced by G to a homogeneous inequality. However, this inequality does not belong to a smaller system of inequalities for Δ which is given by Belkale in [2]. For the smaller system of inequalities, such examples occur only for n ≥ 15.

1. Description of Δ and K in terms of (quantum) Schubert calculus

Fix positive integers r, k such that r +k = n. Let QH^{∗}(G_{r}(ℂ^{n})) be the quantum cohomology ring of the Grassmanian of r-planes in ℂ^{n}. It is an algebra over ℤ[q] (q is an indeterminate) which is generated as a ℤ[q]-module by the elements {σ_{a}} where a runs over the set of partitions P_{r,k} = { (a_{1}, …, a_{r}) | k ≥ a_{1} ≥ ⋯ ≥ a_{r} ≥ 0 }. Let N_{ab}^{c}(r, k) = ∑_{d=0}^{∞} N_{ab}^{c,d}(r, k) q^{d} be the structure constants of this algebra, i.e.

σ_{a} · σ_{b} = ∑_{c∈P_{r,k}} ∑_{d=0}^{∞} N_{ab}^{c,d}(r, k) σ_{c}q^{d}.

The quantum multiplication is homogeneous if we set deg q = n, deg σ_{a} = |a| := a_{1} + ⋯ + a_{r}, i.e. N_{ab}^{c,d}(r, k) is nonzero only if nd = |a| + |b| − |c|. If d = 0 then N_{ab}^{c,d}(r, k) coincides with the classical Littlewood-Richardson coefficient N_{ab}^{c} (in particular, it does not depend on r and k). An algorithm of computation of N_{ab}^{c,d}(r, k) is given in [4]. It is implemented in [5].

Let Ī = { (r, k; a, b, c; d) | r + k = n, (a, b, c) ∈ P_{r,k}^{3} }. For t = (r, k; a, b, c; d) ∈ I we also denote N_{ab}^{c,d}(r, k) by N_{t}. Let I = {t ∈ Ī | N_{t} = 1} and let I_{0} be the subset of I defined by d = 0.

For t = (r, k; a, b, c; d) ∈ I, we define H_{t} = H_{ab}^{c,d}(r, k) as the half-space of ℝ^{3n} given by the inequality h_{t}(α, β, γ) ≥ 0 where

h_{t}(α, β, γ) = d + ∑_{i=1}^{r} γ_{k+i−c_{i}} − ∑_{i=1}^{r} α_{k+i−a_{i}} − ∑_{i=1}^{r} β_{k+i−b_{i}},

As usually, we regard an elements a = (a_{1}, …, a_{r}) of P_{r,k} as a Young diagram inscribed in the rectangle r × k which has r rows (numbered from the top to the bottom) and k columns (numbered from the left to the right). The Young diagram of a is the union of a_{1} leftmost squares of the first row, a_{2} leftmost squares of the second row etc. So, its area is |a|.

Let λ : SU(n) → 𝔄, Λ : SU(n)^{2} → Δ, 𝔱^{+}, and K be as in Introduction. The results of Klyachko and Agnihotri-Woodward-Belkale discussed in Introduction state that

K = 𝔱_{+}^{3} ∩ ( ⋂_{t∈I_{0}} H_{t}), Δ = 𝔄^{3} ∩ ( ⋂_{t∈I} H_{t}).

2. The action of G

Recall that G = Z × Z where Z is the center of SU(n). Let Ω : ℝ^{n} → ℝ^{n} be the affine linear mapping defined by

Ω(x_{1}, …, x_{n}) = (x_{2}, x_{3}, …, x_{n}, x_{1} − 1) + (1/n, …, 1/n).

It is easy to check that 𝔄 = ⋂_{j=0}^{n−1} Ω^{j}(𝔱_{+}) = conv{ Ω^{j}(0) | 0 ≤ j < n}. The action of G we spoke about in Introduction, is

g(α, β, γ) = (Ω^{i}(α), Ω^{j}(β), Ω^{i+j}(γ)) for g = (ω^{i}, ω^{j}).

Obviously, Δ is invariant under G. Indeed, AB = C iff (ω^{i}A)(ω^{j}B) = ω^{i+j}C.

It is shown in [1; Sect. 8] that the action of G on Δ corresponds to the action of G on I defined as follows. Quantum Pierri formula (see [3]) implies that

σ_{k}σ_{a} = \{ \begin{matrix}σ_{k,a_{1},...,a_{r−1}}, & a_{r} = 0, \\ qσ_{a_{1}−1,...,a_{r}−1}, & a_{r} ≠ 0. \end{matrix}

Hence, for any a, b, c ∈ P_{r,k} and i, j ∈ ℤ, we have

σ_{k}^{i}σ_{a} = σ_{a′}q^{d′_{a}}, σ_{k}^{j}σ_{b} = σ_{b′}q^{d′_{b}}, σ_{k}^{i+j}σ_{c} = σ_{c′}q^{d′_{c}}

for certain d′_{a}, d′_{b}, d′_{c} ≥ 0 and a′, b′, c′ ∈ P_{r,k} uniquely determined by a, b, c and i, j. Thus, for t = (r, k; a, b, c; d) and t′ = (r, k; a′, b′, c′; d′) where d′ = d + d′_{c} − d′_{a} − d′_{b}, we have N_{t} = N_{t′}. In other words, the quantum Littlewood-Richardson coefficients are symmetric under the action of G on Ī defined by gt = t′ for g = (ω^{i}, ω^{j}) (this action is well defined because σ_{k}^{n} = q^{k}). In particular, I is invariant under the action of G. It is shown in [1] that the two actions of G (on I and on Δ) are coherent, i.e., gH_{t} = H_{gt}.

3. Symmetries of Δ leaving K invariant

The the action of any non-trivial g ∈ G is such that gK ≠ K. There are also evident symmetries which are common for Δ and K.

Since AB = C ⇔ B^{−1}A^{−1} = C^{−1} and A + B = C ⇔ (−A) + (−B) = −C, both Δ and K are invariant under the involution (α, β, γ) ↦ (α^{∗}, β^{∗}, γ^{∗}) where (α_{1}, …, α_{n})^{∗} = (−α_{n}, …, −α_{1}). For t ∈ Ī, we denote the image of H_{t} under the mapping (α, β, γ) ↦ (α^{∗}, β^{∗}, γ^{∗}) by H_{t}^{∗}. This action on the facets of Δ corresponds to the following symmetry of (quantum) Littlewood-Richardson coefficients provided by the isomorphism between the Grassmanians G_{r}(ℂ^{n}) and G_{k}(ℂ^{n}).

Let t ↦ t^{∗} be the involution Ī → Ī defined by

(r, k; a, b, c; d)^{∗} = (k, r; a^{∗}, b^{∗}, c^{∗}; d)

where

(a_{1}, …, a_{r})^{∗} = (a_{1}^{∗}, …, a_{k}^{∗}), a_{i}^{∗} = max{j | a_{j} ≥ i}

(the Young diagrams of a and a^{∗} are symmetric with respect to the main diagonal). For any t ∈ Ī, we have N_{t} = N_{t^{∗}} and H_{t}^{∗} = H_{t^{∗}}.

For a = (a_{1}, …, a_{r}) ∈ ℙ_{r,k}, let ā = (k−a_{r}, …, k−a_{1}). Then Ī is invariant under the mappings t ↦ (r, k; b, a, c; d) and t ↦ (r, k; b, c̄, ā; d) (commutativity and the Poincaré duality). These symmetries correspond to the evident symmetries of Δ provided by AB ∼ BA and AB = C ⇔ BC^{−1} = A^{−1}.

Let G_{0} be the group of linear transformations of ℝ^{3n} generated by all symmetries discussed in this section and let G̃ be the group of affine transformations generated by G and G_{0}. It is clear that |G_{0}| = 12 and |G̃| = 12n^{2}.

4. Statement of the results

Proposition 1. If n ≤ 14, then I = GI_{0} = ⋃_{G} gI_{0}. In particular, Δ = Δ_{K}.

Proposition 2. If n = 15, then I = GI_{0} ∪ G̃t_{0} and t_{0} ∉ GI_{0} where

t_{0} = (6, 9; 663300, 663300, 666300; 1).

In particular, Δ = Δ_{K} ∩ ( ⋂G̃ gH_{t_{0}}).

Moreover, Δ ≠ Δ_{K}, in particular p = (α, β, γ) ∈ (Δ_{K} \ H_{t_{0}}) ⊂ (Δ_{K} \ Δ) for

α = β = \frac{1}{17} (6, 6, 6, 6, 6, 0, 0, 0, 0, 0, −6, −6, −6, −6, −6),
γ = \frac{1}{17} (8, 8, 8, 1, 1, 1, 1, 1, 1, −3, −3, −3, −3, −9, −9).

The minimum of h_{t_{0}} on Δ_{K} is attained at p.

Corollary 3. If n ≤ 15, then the set of inequalities h_{t} ≥ 0, t ∈ I, defining Δ is minimal, i.e., for any t′ ∈ I, we have

𝔄^{3} ∩ ( ⋂_{t∈I\{t′}} H_{t} ) ≠ Δ

Proof. Follows from Propositions 1 and 2 combined with Knutson-Tao-Woodward’s result [11] on the minimality of the system of inequalities {h_{t} ≥ 0}_{t∈I_{0}} defining K. □

Proposition 4. If n = 16, then I = GI_{0} ∪ G̃I′ where

I′ = { (6, 10; 553300, 663300, 663300; 1),

(7, 9; 5533000, 6633000, 6633000; 1), (7, 9; 5533300, 6633000, 6633300; 1), (7, 9; 5553000, 6443000, 6553000; 1), (7, 9; 6433300, 6633000, 6633300; 1), (8, 8; 44431000, 54441100, 54441100; 1), (8, 8; 44431000, 54442000, 54442000; 1), (8, 8; 44440000, 55441100, 55441100; 1), (8, 8; 44441000, 54441100, 55441100; 1), (8, 8; 44441100, 54431000, 54441100; 1), (8, 8; 44441100, 54441000, 55441100; 1), (8, 8; 44441100, 54441100, 55441110; 1) }.

We do not know any human readable proof of Propositions 1, 2, and 4. They are obtained on a computer. To check Proposition 1, we used the program lrcalc written by Buch [5]. Namely, using this program, for each n ≤ 14 we generated all elements t ∈ I and, for each t, we checked that its orbit Gt (see §2) contains an element with d = 0.

Doing the same computations for n = 15, we found the element t_{0} whose orbit is disjoint from I_{0}. The only orbit of G̃ disjoint from I_{0} is G̃t_{0}.

To check that the inequality h_{t_{0}} ≥ 0 is independent of the others, we minimized (using [13]) h_{t_{0}} under the constraints (1) and h_{t} ∘ g ≥ 0, t ∈ I_{0}, g ∈ G. These are 3 135 129 030 constraints on 30 variables (since a = b in t_{0}, we may set α = β). The capacity of available computers was not enough for a straight forward solution of this problem. In rest of this section we explain the trick we used to reduce the number of constraints up to 148 295.

Consider the following 15 × 15 diagonal matrices:

A = diag(1, 1, 1, 1, 1, −1, …, −1),
B_{1} = diag(1, 1, 1, −1, …, −1, 1, 1),
B_{2} = diag(1, 1, −1, …, −1, 1, 1, 1).

Then

λ(A) = λ(B_{1}) = λ(B_{2}) = \frac{1}{2}(−1, −1, −1, −1, −1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1),

λ(AB_{1}) = \frac{1}{2}(−1, −1, 0, …, 0, 1, 1), and λ(AB_{2}) = \frac{1}{2}(−1, −1, −1, 0, …, 0, 1, 1, 1).

Let p_{i} = Λ(A, B_{i}), i = 1, 2. By definition, we have p_{1}, p_{2} ∈ Δ. We have also h_{t_{0}}(p_{1}) = h_{t_{0}}(p_{2}) = 0. Let

Δ′ = ∩_{t∈I′}H_{t}, I′ = {t ∈ I | t ≠ t_{0}, h_{t}(p_{1}) = h_{t}(p_{2}) = 0}

Lemma. If min_{Δ′} h_{t_{0}} < 0, then Δ ≠ Δ_{K}.

Proof. Suppose that min_{Δ′} h_{t_{0}} < 0. Let p′ ∈ Δ′ be such that h_{t_{0}}(p′) < 0. Set p_{0} = (p_{1} + p_{2})/2. Let I′′ = I \ (I′ ∪ {t_{0}}) and Q = [p′, p_{0}] ∩ ( ⋂_{t∈I′′}{h_{t} = 0}). For any t ∈ I′′, the values of h_{t} at p_{1} and p_{2} are non-negative and at least one of them is positive, hence h_{t}(p_{0}) > 0. Therefore, p_{0} ∉ Q. Let q be the point of Q closest to p_{0}. Then h_{t}(q) ≥ 0 for any t ∈ I′′. On the other hand, h_{t}(q) ≥ 0 for any t ∈ I′ because q ⊂ Δ′. Thus, q ∈ Δ_{K} \ Δ. □

Thus, to show that Δ ≠ Δ_{K}, it is enough to find the minimum of h_{t_{0}} under the constraints only from I′ and this set is more than 30 000 times smaller than I. The minimum is attained at the point p = (α, β, γ) presented in Proposition 2 and we have h_{t_{0}}(p) = −\frac{1}{17} < 0. It follows from Lemma that Δ ≠ Δ_{K}. However, we cannot conclude that min_{Δ_{K}} h_{t_{0}} = min_{Δ} h_{t_{0}}. To prove this fact and to ensure that floating point computations in [13] did not affect the result, we checked that p ∈ Δ_{K} (using lrcalc, this takes few minutes). Namely, we checked that h_{t}(p) < 0 only for t = t_{0} and h_{t}(p) = 0 only in the following cases (up to swapping a and b):

(1) r = 3, a = b = (8, 4, 0), c = (9, 0, 0);

(2) r = 5, a = (7, 7, 3, 0, 0), b = (7, 7, 4, 4, 0), c = (8, 8, 6, 1, 1);

(3) r = 7, a = (5, 5, 2, 2, 0, 0, 0), b = (6, 6, 6, 3, 3, 0, 0), c = (5, 5, 5, 5, 3, 0, 0);

(4) r = 7, a = (5, 5, 3, 3, 3, 0, 0), b = (5, 5, 3, 3, 3, 0, 0), c = (5, 5, 5, 5, 3, 0, 0);

(5) r = 13, a^{∗} = b^{∗} = (9, 5), c^{∗} = (11, 2); in all these cases we have d = 1.

References

1. S. Agnihotri, C. Woodward, Eigenvalues of products of unitary matrices and quantum Schubert calculus, Math. Research Letters 5 (1998), 817–836.

2. P. Belkale, Local systems on ℙ^{1} − S for S a finite set, Compos. Math. 129 (2001), 67–86.

3. A. Bertram, Quantum Schubert calculus, Adv. Math., 128 (1997), 289–305.

4. A. Bertram, I. Ciocan-Fontanine, W. Fulton, Quantum multiplication of Schur polynomials, J. Algebra 219 (1999), 728–746.

5. A.S. Buch, lrcalc – Littlewood-Richardson Calculator, Software available on

http://home.imf.au.dk/abuch/lrcalc and on http://www-math.mit.edu/abuch/lrcalc.

6. V.I. Danilov, G.A. Koshevoy, Discrete convexity and Hermitian matrices, Tr. Mat. Inst. im. Steklova 241 (2003), 68–89 (Russian); English transl., Proc. Steklov Inst. Math. 241 (2003), 58–78.

7. W. Fulton, Eigenvalues, invariant factors, highest weights, and Schubert calculus, Bull. Amer. Math. Soc. (N.S.) 37 (2000), 209–249.

8. A.A. Klyachko, Stable bundles, representation theory and Hermitian operators, Selecta Math. (N.S.) 4 (1998), 419–445.

9. A. Knutson, T. Tao, The honeycomb model of GL_{n}(ℂ) tensor products I: proof of the saturation conjecture, J. Amer. Math. Soc. 12 (1999), 1055–1090.

10. A. Knutson, T. Tao, Honeycombs and sums of Hermitian matrices, Notices Amer. Math. Soc. 48 (2001), no. 2, 175–186.

11. A. Knutson, T. Tao, C. Woodward, The honeycomb model of GL_{n}(ℂ) tensor products II: puzzles determine facets of the Littlewood-Richardson cone, J. Amer. Math. Soc. 17 (2003), 19–48.

12. S.Yu. Orevkov, Quasipositivity test via unitary representations of braid groups and its application to real algebraic curves, J. Knot Theory and Ramifications 10 (2001), 1005–1023.

13. S.Yu. Orevkov, Yu.P. Orevkov, Simplex-method (linear programming), Software available on

http://picard.ups-tlse.fr/orevkov/simplex.

14. T. Tao, Open question: What is a quantum honeycomb?

http://terrytao.wordpress.com/2007/04/19.

Laboratoire Emile Picard, UFR MIG, Univ. Paul Sabatier, Toulouse, France and Steklov Math. Inst., Moscow Russia

Faculty of Economy, Moscow State Univ., Moscow, Russia