The Littlewood-Richardson rule and Gelfand-Tsetlin patterns
We give a survey on the Littlewood-Richardson rule. Using Gelfand-Tsetlin patterns as the main machinery of our analysis, we study the interrelationship of various combinatorial descriptions of the Littlewood-Richardson rule.
Gespeichert in:
| Datum: | 2016 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2016
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/155744 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | The Littlewood-Richardson rule and Gelfand-Tsetlin patterns / P. Doolan, S. Kim // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 1. — С. 21-47. — Бібліогр.: 29 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-155744 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1557442019-06-18T01:25:22Z The Littlewood-Richardson rule and Gelfand-Tsetlin patterns Doolan, P. Kim, S. We give a survey on the Littlewood-Richardson rule. Using Gelfand-Tsetlin patterns as the main machinery of our analysis, we study the interrelationship of various combinatorial descriptions of the Littlewood-Richardson rule. 2016 Article The Littlewood-Richardson rule and Gelfand-Tsetlin patterns / P. Doolan, S. Kim // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 1. — С. 21-47. — Бібліогр.: 29 назв. — англ. 1726-3255 2010 MSC:05E10, 20G05, 52B20. http://dspace.nbuv.gov.ua/handle/123456789/155744 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We give a survey on the Littlewood-Richardson rule. Using Gelfand-Tsetlin patterns as the main machinery of our analysis, we study the interrelationship of various combinatorial descriptions of the Littlewood-Richardson rule. |
| format |
Article |
| author |
Doolan, P. Kim, S. |
| spellingShingle |
Doolan, P. Kim, S. The Littlewood-Richardson rule and Gelfand-Tsetlin patterns Algebra and Discrete Mathematics |
| author_facet |
Doolan, P. Kim, S. |
| author_sort |
Doolan, P. |
| title |
The Littlewood-Richardson rule and Gelfand-Tsetlin patterns |
| title_short |
The Littlewood-Richardson rule and Gelfand-Tsetlin patterns |
| title_full |
The Littlewood-Richardson rule and Gelfand-Tsetlin patterns |
| title_fullStr |
The Littlewood-Richardson rule and Gelfand-Tsetlin patterns |
| title_full_unstemmed |
The Littlewood-Richardson rule and Gelfand-Tsetlin patterns |
| title_sort |
littlewood-richardson rule and gelfand-tsetlin patterns |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2016 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/155744 |
| citation_txt |
The Littlewood-Richardson rule and Gelfand-Tsetlin patterns / P. Doolan, S. Kim // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 1. — С. 21-47. — Бібліогр.: 29 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT doolanp thelittlewoodrichardsonruleandgelfandtsetlinpatterns AT kims thelittlewoodrichardsonruleandgelfandtsetlinpatterns AT doolanp littlewoodrichardsonruleandgelfandtsetlinpatterns AT kims littlewoodrichardsonruleandgelfandtsetlinpatterns |
| first_indexed |
2025-07-14T07:59:09Z |
| last_indexed |
2025-07-14T07:59:09Z |
| _version_ |
1837608416317538304 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 22 (2016). Number 1, pp. 21–47
© Journal “Algebra and Discrete Mathematics”
The Littlewood-Richardson rule
and Gelfand-Tsetlin patterns
Patrick Doolan and Sangjib Kim
Communicated by V. A. Artamonov
Abstract. We give a survey on the Littlewood-Richardson
rule. Using Gelfand-Tsetlin patterns as the main machinery of our
analysis, we study the interrelationship of various combinatorial
descriptions of the Littlewood-Richardson rule.
1. Introduction
1.1. Let us consider Schur polynomials sµ, sν and sλ in n variables
labelled by partitions µ, ν and λ, respectively. The Littlewood-Richardson
(LR) coefficient is the multiplicity cλ
µ,ν of sν in the product of sµ and sν :
sµsν =
∑
λ
cλ
µ,νsλ
and its description is called the LR rule.
The same number appears in the tensor product decomposition prob-
lem in the representation theory of the complex general linear group GLn
and Schubert calculus in the cohomology of the Grassmannians, and is
also related to the eigenvalues of the sum of Hermitian matrices. For more
details, we refer readers to [8, 15,27,29].
2010 MSC: 05E10, 20G05, 52B20.
Key words and phrases: Littlewood-Richardson rule, Gelfand-Tsetlin patterns.
22 The Littlewood-Richardson rule
1.2. The LR rule is usually stated in terms of combinatorial objects
called LR tableaux. Recall that a Young tableau is a filling of the boxes
of a Young diagram with positive integers. We shall use the English
convention of drawing Young diagrams and tableaux as in [7, 26] and
assume a basic knowledge of these objects.
Definition 1. A tableau T on a skew Young diagram is called a LR
tableau if it satisfies the following conditions:
1) it is semistandard, that is, the entries in each row of T weakly
increase from left to right, and the entries in each column strictly
increase from top to bottom; and
2) its reverse reading word is a Yamanouchi word (or lattice permuta-
tion). That is, in the word x1x2x3 . . . xr obtained by reading all the
entries of T from left to right in each row starting from the bottom
one, the sequence xrxr−1xr−2 . . . xs contains at least as many a’s
as it does (a+ 1)’s for all a > 1.
For example, the following is a LR tableau on a skew Young diagram
(11, 7, 5, 3)/(5, 3, 1)
1 1 1 1 1 1
1 2 2 2
2 3 3 3
2 4 4
and its reverse reading word is 24423331222111111.
Remark 1. (1) In this paper we assume each tableau’s entries weakly
increase from left to right in every row. (2) From the second condition in
the above definition, which we will call the Yamanouchi condition, the
bth row of a LR tableau does not contain any entries strictly bigger than
b for all b > 1.
The number of LR tableaux on the skew shape λ/µ with content ν
is equal to the LR number cλ
µ,ν . Here, the content ν = (ν1, . . . , νn) of a
tableau means that the entry k appears νk times in the tableau for k > 1.
See, for example, [24, §I.9] and [15].
1.3. In this paper, we survey variations of the semistandard and Ya-
manouchi conditions with an emphasis on dualities in combinatorial
descriptions of the LR rule. Although many of the results in this paper
can be found in the literature, we will give complete and elementary
proofs of our statements.
P. Doolan, S. Kim 23
(1) In Theorem 1 and Theorem 2, we analyse hives, introduced by
Knutson and Tao along with their honeycomb model [21], in terms of
Gelfand-Tsetlin(GT) patterns [10]. We then show how the interlacing
conditions in GT patterns are intertwined to form the defining conditions
of hives. For the relevant results, see for example [1–4].
(2) In Theorem 3, we show that the semistandard and Yamanouchi
conditions in LR tableaux are equivalent to, respectively, the interlacing
and exponent conditions in GZ schemes introduced by Gelfand and
Zelevinsky [11]. As a corollary we obtain a correspondence between
LR tableaux and hives equivalent to [18, (3.3)]. We then observe how
conditions on LR tableaux, GZ schemes and hives are translated between
objects by this bijection. For the relevant results, see, for example, [1, 5,
18,19].
(3) In Theorem 4, we show that the semistandard and Yamanouchi
conditions in LR tableaux are equivalent to, respectively, the exponent
and semistandard conditions in their companion tableaux introduced by
van Leeuwen [29]. Here the correspondence between conditions is obtained
by taking the transpose of matrices.
As a consequence, we obtain bijections between the families of combi-
natorial objects counting the LR number.
1.4. In [16,17], Howe and his collaborators constructed a polynomial
model for the tensor product of representations in terms of two copies
of the multi-homogeneous coordinate ring of the flag variety, and then
studied its toric degeneration with the SAGBI-Gröbner method. Through
the characterization of the leading monomials of highest weight vectors,
their toric variety is encoded by the LR cone [25]. On the other hand,
via toric degenerations, the flag variety may be described in terms of the
lattice cone of GT patterns [13,20,23]. These results led us to study the
LR rule in terms of two sets of interlacing or semistandard conditions and
to investigate the interrelationship of various combinatorial descriptions
of the LR rule with GT patterns.
2. Hives and GT patterns I
In this section, we define GT patterns, hives, and objects related to
them. We also describe hives in terms of pairs of GT patterns.
2.1. We set, once and for all, three polynomial dominant weights of the
complex general linear group GLn, that is, the sequences of nonnegative
24 The Littlewood-Richardson rule
integers:
λ = (λ1, . . . , λn), µ = (µ1, . . . , µn), ν = (ν1, . . . , νn)
such that λi > λi+1, µi > µi+1, and νi > νi+1 for all i. We define the dual
λ∗ of λ to be
λ∗ = (−λn,−λn−1, . . . ,−λ1),
and define µ∗ and ν∗ similarly.
2.2. Let us consider an array of integers, which we will call a t-array
T =
(
t
(1)
1 , . . . , t
(i)
j , . . . , t(n)
n
)
∈ Z
n(n+1)/2
where 1 6 j 6 i 6 n. We are particularly interested in the case when the
entries of T are either all non-negative or all non-positive integers.
Definition 2. A t-array T = (t
(i)
j ) ∈ Z
n(n+1)/2 is called a GT pattern for
GLn if it satisfies the interlacing conditions:
IC(1): t
(i+1)
j > t
(i)
j
IC(2): t
(i)
j > t
(i+1)
j+1
for all i and j.
We shall draw a t-array in the reversed pyramid form. For example, a
generic GT pattern for GL5 is
t
(5)
1 t
(5)
2 t
(5)
3 t
(5)
4 t
(5)
5
t
(4)
1 t
(4)
2 t
(4)
3 t
(4)
4
t
(3)
1 t
(3)
2 t
(3)
3
t
(2)
1 t
(2)
2
t
(1)
1
where the entries are weakly decreasing along the diagonals from left to
right.
Then, the dual array T ∗ = (s
(i)
j ) of T is the t-array obtained by
reflecting T over a vertical line and then multiplying −1, i.e.,
s
(i)
j = −t
(i)
i+1−j
for all 1 6 j 6 i 6 n.
P. Doolan, S. Kim 25
Definition 3. For a t-array T = (t
(i)
j ) ∈ Z
n(n+1)/2,
1) the kth row of T is t(k) = (t
(k)
1 , t
(k)
2 , . . . , t
(k)
k ) ∈ Z
k for 1 6 k 6 n.
The type of T is its nth row;
2) the weight of T is (w1, w2, . . . , wn) ∈ Z
n where w1 = t
(1)
1 and
wi =
i
∑
k=1
t
(i)
k −
i−1
∑
k=1
t
(i−1)
k for 2 6 i 6 n.
Note that if T is of type λ and weight w ∈ Z
n, then T ∗ is of type λ∗
and weight −w.
GT patterns were introduced by Gelfand and Tsetlin in [10] to label
the weight basis elements of an irreducible representation of the general
linear group. The weight of T is exactly the weight of the basis element
labelled by T in the irreducible representation V µ
n whose highest weight
is µ = t(n). It follows that the dual array T ∗ of T corresponds to a weight
vector in the contragradiant representation of V µ
n .
2.3. Let us consider an array of nonnegative integers, which we will call
a h-array,
(h0,0, . . . , ha,b, . . . , hn,n) ∈ Z
(n+1)(n+2)/2
where 0 6 a 6 b 6 n and h0,0 = 0.
Definition 4. A hive for GLn is a h-array H = (ha,b) ∈ Z
(n+1)(n+2)/2
satisfying the rhombus conditions:
RC(1): (ha,b + ha−1,b−1) > (ha−1,b + ha,b−1) for 1 6 a < b 6 n,
RC(2): (ha−1,b + ha,b) > (ha,b+1 + ha−1,b−1) for 1 6 a 6 b < n,
RC(3): (ha,b + ha,b+1) > (ha+1,b+1 + ha−1,b) for 1 6 a 6 b < n.
We shall draw a h-array in the pyramid form. For example, a generic
hive for GL3 is shown below.
h0,0
h0,1 h1,1
h0,2 h1,2 h2,2
h0,3 h1,3 h2,3 h3,3
26 The Littlewood-Richardson rule
The rhombus conditions RC(1), RC(2), and RC(3) then say that, for each
fundamental rhombus of one of the following forms,
A
O′ A′ O O′ A′ O
A O , A′ , O′ A
the sum of entries at the obtuse corners is bigger than or equal to the
sum of entries at the acute corners, i.e., O +O′ > A+A′.
For polynomial dominant weights µ, ν, and λ of GLn, we let H(µ, ν, λ)
denote the set of all h-arrays such that
µ = (h0,1 − h0,0, h0,2 − h0,1, . . . , h0,n − h0,n−1),
ν = (h1,n − h0,n, h2,n − h1,n, . . . , hn,n − hn−1,n), (1)
λ = (h1,1 − h0,0, h2,2 − h1,1, . . . , hn,n − hn−1,n−1).
That is, the three boundary sides of H ∈ H(µ, ν, λ) are fixed:
h0,i = µ1 + µ2 + · · · + µi
hi,n =
n
∑
j=1
µj + ν1 + ν2 + · · · + νi
hi,i = λ1 + λ2 + · · · + λi
for 1 6 i 6 n. Recall that we always set h0,0 = 0. Let H◦(µ, ν, λ) be the
subset of H(µ, ν, λ) satisfying the rhombus conditions. This is the set of
hives whose boundaries are described by (1).
Hives were introduced by Knutson and Tao in [21] along with their
honeycomb model to prove the saturation conjecture. In particular, the
number of hives in H◦(µ, ν, λ) is equal to the LR number cλ
µ,ν . See also
[5, 22,25].
2.4. For each h-arrayH = (ha,b) ∈ Z
(n+1)(n+2)/2, let us define its derived
t-arrays
T1 = (x
(i)
j ), T2 = (y
(i)
j ), T3 = (z
(i)
j )
whose entries are obtained from the differences of adjacent entries of H.
More specifically, for each fundamental triangle in H,
ha,b
ha,b+1 ha+1,b+1
P. Doolan, S. Kim 27
h0,0
χ
(3)
1 z
(3)
1
h0,1 y
(1)
1 h1,1
χ
(3)
2 z
(2)
1 χ
(2)
1 z
(3)
2
h0,2 y
(2)
1 h1,2 y
(2)
2 h2,2
χ
(3)
3 z
(1)
1 χ
(2)
2 z
(2)
2 χ
(1)
1 z
(3)
3
h0,3 y
(3)
1 h1,3 y
(3)
2 h2,3 y
(3)
3 h3,3
Figure 1. A h-array and its three derived t-arrays.
the entries of the derived t-arrays (x
(i)
j ), (y
(i)
j ), and (z
(i)
j ) are
x
(n−a)
b+1−a = ha,b+1 − ha,b (SW–NE direction)
y
(b+1)
a+1 = ha+1,b+1 − ha,b+1 (E–W direction) (2)
z
(n+a−b)
a+1 = ha+1,b+1 − ha,b (SE–NW direction)
for 0 6 a 6 b 6 n− 1.
This rather involved indexing is to make the entries of the derived
arrays compatible with those of GT patterns. We may visualize the derived
t-arrays by placing their entries between the entries of the h-array used
to compute them. For example, if n = 3, then a h-array and its three
derived t-arrays may be drawn as Figure 1.
2.5. The rhombus conditions for h-arrays are closely related to the
interlacing conditions for their derived t-arrays.
Proposition 1. Let Tk = Tk(H) be a derived t-array of a h-array H for
k = 1, 2, 3.
1) H satisfies RC(1) if and only if T1 satisfies IC(2) and T2 satisfies
IC(1).
2) H satisfies RC(2) if and only if T1 and T3 satisfy IC(1).
3) H satisfies RC(3) if and only if T2 and T3 satisfy IC(2).
4) T3 satisfies IC(1) if and only if T1 satisfies IC(1).
5) T3 satisfies IC(2) if and only if T2 satisfies IC(2).
28 The Littlewood-Richardson rule
Proof. Let us consider five adjacent entries of H of the forms
Z1 Z3
Y1 W1 Y2 W2 Y3 W3
X1 V1 , X2 V2 U2, V3 U3.
Then, in the first and the third ones, RC(2) says that Yi +Wi > Zi +Vi for
i = 1 and 3. This is equivalent to Y1−Z1 > V1−W1 andW3−Z3 > V3−Y3,
which are IC(1) for T1 and T3, respectively. This proves the statement (2).
The statements (1) and (3) can be shown similarly.
Next, let us consider fundamental rhombi of the following forms in H
K
L N P S
M , Q R.
Note that N − K > M − L if and only if L − K > M − N , which
proves (4). Similarly, P −Q > S−R if and only if P −S > Q−R, which
proves (5).
Suppose a h-array H satisfies RC(1), RC(2), and RC(3). Then, by the
statements (1) and (2) of Proposition 1, T1(H) satisfies IC(1) and IC(2).
Similarly, by the statements (1) and (3), T2(H) satisfies IC(1) and IC(2).
This shows that T1(H) and T2(H) are GT patterns. Conversely, if T1(H)
and T2(H) are GT patterns, then, by the statements (4) and (5), T3(H)
is also a GT pattern. This means all three derived t-arrays satisfy both
IC(1) and IC(2), and therefore, from the statements (1), (2), and (3), H
is a hive.
Theorem 1. For a h-array H ∈ Z
(n+1)(n+2)/2 and its derived t-arrays
T1(H) and T2(H), H is a hive if and only if T1(H) and T2(H) are GT
patterns for GLn.
We remark that, in the above result, T1(H) and T2(H) are not in-
dependent. Let T1 = (x
(i)
j ) and T2 = (y
(i)
j ) be the derived t-arrays of a
h-array H. Then, for each rhombus of the form
B A
C D
P. Doolan, S. Kim 29
we have (D − C) + (C −B) = (D −A) + (A−B), or
(C −B) − (D −A) = (A−B) − (D − C)
which is, using (2),
x
(n−a−1)
b−a − x
(n−a)
b+1−a = y
(b+1)
a+1 − y
(b)
a+1 (3)
for 0 6 a < b < n. Note that hives (respectively, GT patterns) for
GLn with non-negative entries form a subsemigroup of Z
(n+1)(n+2)/2
>0
(respectively, Z
n(n+1)/2
>0 ). Theorem 1 and (3) imply that the semigroup
⋃
(µ,ν,λ)
H◦(µ, ν, λ)
of hives is a fiber product of, over Z
n(n−1)/2
>0 , two affine semigroups S1
GT
and S2
GT of GT patterns with respect to
φk : Sk
GT −→ Z
n(n−1)/2
>0
such that, for 0 6 a < b < n,
φ1(T1) =
(
. . . , x
(n−a−1)
b−a − x
(n−a)
b+1−a, . . .
)
,
φ2(T2) =
(
. . . , y
(b+1)
a+1 − y
(b)
a+1, . . .
)
where T1 = (x
(i)
j ) ∈ S1
GT and T2 = (y
(i)
j ) ∈ S2
GT .
We also remark that by exchanging the roles of T1(H), T2(H) and
T3(H), one can read the symmetry of the LR rule. See, for example, [28].
3. Hives and GT patterns II
In this section, we study the set H◦(µ, ν, λ) of hives with a given
boundary condition in terms of a single GT pattern.
3.1. Gelfand and Zelevinsky counted the LR number cλ
µ,ν with GT
patterns of type µ and weight λ− ν satisfying the following additional
condition.
Lemma 1 ([11]). For a t-array T = (t
(i)
j ) ∈ Z
n(n+1)/2, we define its
exponents as
ε
(i)
j (T ) =
∑
16h<j
(t
(i+1)
h − 2t
(i)
h + t
(i−1)
h ) + (t
(i+1)
j − t
(i)
j ).
30 The Littlewood-Richardson rule
Then the cardinality of the set GZ(µ, λ − ν, ν) of all GT patterns T of
type µ with weight λ− ν such that, for all i and j,
ε
(i)
j (T ) 6 νi − νi+1
is equal to the LR number cλ
µ,ν .
The elements of GZ(µ, λ− ν, ν) will be called GZ schemes.
3.2. Note that, for a h-array H, since the derived t-arrays are defined
from the differences of the entries in H, if the boundaries of H are fixed,
then any one of the derived t-array of H uniquely determines H. Moreover,
we can characterize the derived t-arrays as follows.
Theorem 2. For a h-array H in H(µ, ν, λ), consider its derived t-arrays
T1(H) and T2(H).
1) H is a hive if and only if T ∗
1 (H) = (T1(H))∗ is a GZ scheme in
GZ(µ∗, λ∗ − ν∗, ν∗);
2) H is a hive if and only if T2(H) is a GZ scheme in GZ(ν, λ−µ, µ).
Note that this theorem, in particular, gives bijections between hives
and GZ schemes:
H◦(µ, ν, λ) −→ GZ(µ∗, λ∗ − ν∗, ν∗)
H 7−→ T ∗
1 (H)
and
H◦(µ, ν, λ) −→ GZ(ν, λ− µ, µ)
H 7−→ T2(H) .
For the rest of this section, we will prove Theorem 2 by showing the
following.
(a) T ∗
1 (H) satisfies IC(2) if and only if ε
(i)
j (T2(H)) 6 µi − µi+1;
(b) T ∗
1 (H) satisfies IC(1) if and only if T2(H) satisfies IC(1);
(c) T ∗
1 (H) satisfies ε
(i)
j (T ∗
1 (H)) 6 ν∗
i −ν∗
i+1 if and only if T2(H) satisfies
IC(2).
The weights of the derived t arrays will also be computed.
3.3. Let us first compute the weights of T1(H) and T2(H) for H ∈
H(µ, ν, λ).
Lemma 2. For a h-array H = (ha,b) ∈ H(µ, ν, λ),
P. Doolan, S. Kim 31
1) the weight of T1(H) is ν∗ − λ∗, i.e.,
(λn − νn, λn−1 − νn−1, . . . , λ1 − ν1)
therefore, the weight of T ∗
1 (H) is λ∗ − ν∗;
2) the weight of T2(H) is λ− µ, i.e.,
(λ1 − µ1, λ2 − µ2, . . . , λn − µn).
Proof. We will prove the second statement. The proof of the first case is
similar. From Definition 3, (2) and the expressions for λ and µ in terms
of the h-array elements it follows
w1 = y
(1)
1 = h1,1 − h0,1 = (h1,1 − h0,0) + (h0,0 − h0,1) = λ1 − µ1.
Using the same approach for wi, i > 2, we see
wi =
i
∑
k=1
y
(i)
k −
i−1
∑
k=1
y
(i−1)
k
=
i
∑
k=1
(hk,i − hk−1,i) −
i−1
∑
k=1
(hk,i−1 − hk−1,i−1)
= (hi,i − h0,i) − (hi−1,i−1 − h0,i−1)
= λi − µi.
Therefore wi = λi − µi for all i, and the weight of T2(H) is λ− µ.
3.4. Next, we study the relations between the interlacing conditions and
the exponents conditions for derived arrays. Note that, from the definition
of dual arrays, a t-array T satisfies IC(1) if and only if T ∗ satisfies IC(2),
and T satisfies IC(2) if and only if T ∗ satisfies IC(1).
Proposition 2. For a h-array H = (ha,b) ∈ H(µ, ν, λ) and its derived
t-arrays T1(H) = (x
(i)
j ) and T2(H) = (y
(i)
j ), T1(H) satisfies IC(1) if and
only if ε
(i)
j (T2(H)) 6 µi − µi+1.
Proof. Let us assume j > 1. Then the exponent of T2(H),
ε
(i)
j (T2(H)) =
∑
16h<j
(
(y
(i+1)
h − y
(i)
h ) − (y
(i)
h − y
(i−1)
h )
)
+
(
y
(i+1)
j − y
(i)
j
)
32 The Littlewood-Richardson rule
can be rewritten in terms of the entries of T1(H). By using (3),
ε
(i)
j (T2(H)) =
∑
16h<j
(
(x
(n−h)
i−h+1 − x
(n−h+1)
i−h+2 ) − (x
(n−h)
i−h − x
(n−h+1)
i−h+1 )
)
+
(
x
(n−j)
i−j+1 − x
(n−j+1)
i−j+2 + y
(i)
j
)
−
(
x
(n−j)
i−j − x
(n−j+1)
i−j+1 + y
(i−1)
j
)
and we see that parts of the consecutive terms cancel to give
ε
(i)
j (T2(H)) =
(
x
(n)
i − x
(n)
i+1
)
+
(
x
(n−j)
i−j+1 − x
(n−j)
i−j + y
(i)
j − y
(i−1)
j
)
. (4)
Now note that the interlacing condition IC(1) for T1(H) implies
x
(n−j+1)
i−j+1 > x
(n−j)
i−j+1 or equivalently, by using (3),
x
(n−j)
i−j >
(
x
(n−j)
i−j+1 + y
(i)
j − y
(i−1)
j
)
therefore
0 >
(
x
(n−j)
i−j+1 − x
(n−j)
i−j + y
(i)
j − y
(i−1)
j
)
.
Hence, from (4), the interlacing condition IC(1) for T1(H) is equivalent
to
ε
(i)
j (T2(H)) 6
(
x
(n)
i − x
(n)
i+1
)
= µi − µi+1.
The case j = 1 can be shown similarly for all i.
Proposition 3. For a h-array H = (ha,b) ∈ H(µ, ν, λ) and its derived
t-arrays T1(H) = (x
(i)
j ) and T2(H) = (y
(i)
j ), T1(H) satisfies IC(2) if and
only if T2(H) satisfies IC(1).
Proof. Using the equality (3),
(
x
(i)
j > x
(i+1)
j+1
)
if and only if
(
y
(n−i+j)
n−i > y
(n−i+j−1)
n−i
)
and therefore, by setting i′ = n− i+ j − 1 and j′ = n− i, we have
(
x
(i)
j > x
(i+1)
j+1
)
if and only if
(
y
(i′+1)
j′ > y
(i′)
j′
)
for 1 6 j 6 i 6 n − 1 and 1 6 j′ 6 i′ 6 n − 1. This shows that IC(2)
holds for T1(H) if and only if IC(1) holds for T2(H).
Proposition 4. For a h-array H = (ha,b) ∈ H(µ, ν, λ) and its derived t-
arrays T1(H) = (x
(i)
j ) and T2(H) = (y
(i)
j ), T ∗
1 (H) satisfies ε
(i)
j (T ∗
1 (H)) 6
ν∗
i − ν∗
i+1 if and only if T2(H) satisfies IC(2).
P. Doolan, S. Kim 33
Proof. Let us assume j > 1. Write the exponents of T ∗
1 (H) = (s
(i)
j ) using
s
(i)
j = −x
(i)
i+1−j .
ε
(i)
j (T ∗
1 (H)) =
∑
16h<j
(
−x
(i+1)
i−h+2 + 2x
(i)
i−h+1 − x
(i−1)
i−h
)
+
(
−x
(i+1)
i−j+2 + x
(i)
i−j+1
)
=
∑
16h<j
(
(x
(i)
i−h+1 − x
(i+1)
i−h+2) − (x
(i−1)
i−h − x
(i)
i−h+1)
)
+
(
x
(i)
i−j+1 − x
(i+1)
i−j+2
)
Then, using the identity (3), we can rewrite the exponents in terms of
the entries of T2(H) as
ε
(i)
j (T ∗
1 (H)) =
∑
16h<j
(
(y
(n−h+1)
n−i − y
(n−h)
n−i ) − (y
(n−h+1)
n−i+1 − y
(n−h)
n−i+1)
)
+
(
y
(n−j+1)
n−i − y
(n−j)
n−i
)
6
∑
16h<j
(
(y
(n−h+1)
n−i − y
(n−h)
n−i ) − (y
(n−h+1)
n−i+1 − y
(n−h)
n−i+1)
)
+
(
y
(n−j+1)
n−i − y
(n−j+1)
n−i+1
)
where the inequality is by IC(2): y
(n−j)
n−i > y
(n−j+1)
n−i+1 in T2(H). Parts of the
consecutive terms in the right hand side cancel to give
ε
(i)
j (T ∗
1 (H)) 6
(
(y
(n)
n−i − y
(n−j+1)
n−i ) − (y
(n)
n−i+1 − y
(n−j+1)
n−i+1 )
)
+
(
y
(n−j+1)
n−i − y
(n−j+1)
n−i+1
)
=
(
y
(n)
n−i − y
(n)
n−i+1
)
= νn−i − νn−i+1 = ν∗
i − ν∗
i+1.
So the interlacing condition IC(2) for T2(H) is equivalent to
ε
(i)
j (T ∗
1 (H)) 6 ν∗
i − ν∗
i+1
as required. The case j = 1 can be shown similarly for all i.
3.5. Suppose we have a hive H. From Lemma 2, the weights of T ∗
1 (H)
and T2(H) are λ∗ −ν∗ and λ−µ, respectively. Theorem 1 states that H is
a hive if and only if T1(H) and T2(H), and hence T ∗
1 (H) and T2(H), satisfy
both IC(1) and IC(2). Therefore since H is a hive, Proposition 2 and
34 The Littlewood-Richardson rule
Proposition 4 imply T ∗
1 (H) and T2(H) satisfy the exponent conditions, and
consequently they are GZ schemes in GZ(µ∗, λ∗ − ν∗, ν∗) and GZ(ν, λ−
µ, µ), respectively.
Conversely, if T ∗
1 (H) is a GZ scheme from GZ(µ∗, λ∗−ν∗, ν∗) it satisfies
IC(1), IC(2), and the exponent condition, thus from Propositions 2 – 4,
T2(H) is a GZ scheme. In particular, T1(H) and T2(H) are GT patterns,
meaning H is a hive by Theorem 1. Similarly, if T2(H) ∈ GZ(ν, λ− µ, µ),
then H is a hive. This proves Theorem 2.
4. LR tableaux and GT patterns I
In this section we introduce a bijection between LR tableaux and GZ
schemes (Theorem 3). In proving this we will see that the semistandard
and Yamanouchi conditions for tableaux are equivalent to, respectively,
the interlacing and exponent conditions for t-arrays.
As an interesting consequence we then combine Theorem 3 with
Theorem 2 (1) to arrive at a correspondence between LR tableaux and
hives (Corollary 1). It turns out that Corollary 1 is equivalent to [18, (3.3)],
so we compare the two constructions. The main difference is that our
method has an intermediate GZ scheme, which is an artefact of composing
Theorem 3 and Theorem 2. To conclude the section we summarise how the
conditions on LR tableaux (semistandard and Yamanouchi conditions), GZ
schemes (semistandard and exponent conditions) and hives (the rhombus
conditions) are translated by the bijections.
The reader may find relevant results and further developments in, for
example, [1–4,6, 18,19,25].
4.1. A well-known bijection between semistandard tableaux
and GT patterns. Our bijection between LR tableaux and GZ schemes
is an extension of a well-known bijection between semistandard tableaux
and GT patterns, seen in, for example, [11]. We now review this bijection
and state it in the form most useful for our purposes. For this we require
some relevant notation.
A non-skew semistandard tableau Y is uniquely determined by its
associated matrix (ai,j(Y )) where
ai,j(Y ) = the number of i’s in the jth row (5)
for all 1 6 i, j 6 n. Note that ai,j(Y ) = 0 for i < j. We also note
that
∑n
k=1 ak,j(Y ) for 1 6 j 6 n give the shape of the tableau Y , and
∑n
k=1 ai,k(Y ) for 1 6 i 6 n give the content of Y . The reader is warned
P. Doolan, S. Kim 35
that these are not the same aij as those in [18, (3.4)]. Those label hive
entries, not content of a tableau.
We remark that if Y is a semistandard tableau on the skew shape λ/µ,
then the ai,j(Y )’s are well defined, and the ai,j(Y )’s with λ or µ uniquely
define Y . It is possible to develop the theory of tableaux exclusively in
terms of their associated matrices. See [6] for this direction.
Now consider a semistandard Young tableau. Removing all instances
of the largest entry simultaneously yields a tableau with a new shape.
Repeating this process, we would achieve a list of successively shrinking
shapes, which written downwards would form the rows of a GT pattern.
This process is a bijection. See Example 1.
It is easy to symbolically describe the inverse of the bijection. Given
a GT pattern T = (t
(i)
j ) of type λ with non-negative entries, it creates a
semistandard Young tableau YT of shape λ whose entries are elements of
{1, 2, . . . , n} and defined by
ai,j(YT ) = t
(i)
j − t
(i−1)
j (6)
for 1 6 i, j 6 n with the conventions
t
(i)
j = 0 for j > i > 0.
Manipulating (6), it follows that the bijection takes a semistandard tableau
Y and creates a GT pattern TY = (t
(i)
j ) according to the rule
t
(i)
j =
i
∑
k=1
ak,j(Y ) (7)
for 1 6 j 6 i 6 n. Since ak,j(Y ) = 0 for k < j in every non-skew
semistandard tableau Y , we can in fact write this as
t
(i)
j =
i
∑
k=j
ak,j(Y ). (8)
See also, for example, [14, §8.1.2] or [20] for further background on this
bijection.
Example 1. As an example we apply the bijection to the tableau
1 1 2
2 3
3
36 The Littlewood-Richardson rule
and list the successive shapes λ(i) as they are created.
1 1 2
2 3
3
= (0) = 3, 2, 1
1 1 2
2
(0) = 3, 2, 1
(1) = 3, 1
1 1
(0) = 3, 2, 1
(1) = 3, 1
(2) = 2
Clearly, the shapes form a GT pattern. It is straightforward to check
that the expressions (8) and (6) both hold.
Under this bijection, the content of the tableau is equal to the weight of
the t-array. We also note that in this bijection, the semistandard condition
on the tableau is implied by the interlacing conditions on the t-array and
vice versa (cf. Remark 2).
4.2. A well-known bijection between semistandard skew
tableaux and truncated GT patterns. The bijection of §4.1 can
be extended to act on skew tableaux. Again, this is a well known result
included in [11], [12] and [3], among others.
Lemma 3. There is a bijection between the set of skew semistandard
Young tableaux of shape λ/µ with entries from {1, 2, . . . , n} and the set
of GT patterns for GL2n whose type is λ′ = (λ1, . . . , λn, 0, · · · , 0) ∈ Z
2n
and whose kth row is (µ1, µ2, . . . , µk) for 1 6 k 6 n.
Proof. For a given semistandard Young tableau Y of shape λ/µ, replace
the i entries with (n+i)’s for 1 6 i 6 n, then fill in the empty boxes in the
ℓth row of Y with ℓ’s for 1 6 ℓ 6 n. Then this process uniquely determines
a non-skew semistandard Young tableau of shape λ with entries from
{1, 2, . . . , 2n}, and under the bijection given by (6), its corresponding GT
pattern for GL2n is the one described in the statement.
The first half of Example 2 shows Lemma 3 applied to a skew tableau.
We remark that the GT pattern for GLn whose kth row is (µ1, µ2, . . . , µk)
for 1 6 k 6 n corresponds to the highest weight vector of the repre-
sentation V µ
n labelled by a Young diagram µ. In fact, the GT patterns
described in Lemma 3 encode the weight vectors of V λ′
2n , which are the
highest weight vector for V µ
n under the branching of GL2n down to GLn.
The bottom n− 1 rows of a GT pattern described by Lemma 3 hold
redundant information because they are determined by µ. It is therefore
convention to omit them and achieve what is called a truncated GT
pattern. It is also common to omit the upper-right portion of this pattern,
P. Doolan, S. Kim 37
since the interlacing conditions force those entries to be zero. For example,
the first half of the bijection described by [18, (3.3)] uses Lemma 3 with
these conventions.
There is an excellent example of Lemma 3 and further explanation in
[1, §2].
4.3. Symbolic forms of the semistandard and Yamanouchi con-
ditions. We are almost ready to use Lemma 3 to establish the bijection
between LR tableaux and GZ schemes. However, we first need symbolic
forms of both the semistandard and Yamanouchi conditions.
Let us express the semistandard condition for a tableau Y in terms
of the ai,j(Y ) defined in (5). By rearranging the entries in each row if
necessary, we can always make the entries of Y weakly increasing along
each row from left to right. The strictly increasing condition on the
columns of Y can then be rephrased as follows: the number of entries up
to ℓ in the (m+ 1)th row is not bigger than the number of entries up to
(ℓ− 1) in the mth row, i.e.,
ℓ−1
∑
k=1
ak,m(Y ) >
ℓ
∑
k=1
ak,m+1(Y ) (9)
for 1 6 ℓ 6 n and 1 6 m < n. Here, if ℓ = 1, then the left hand side is
0 as an empty sum and the inequality implies that a1,m+1(Y ) = 0 for
m > 1. Inductively, we can obtain ai,m+1(Y ) = 0 for m > i from the
inequality with ℓ = i. This shows that for a semistandard Young tableau
Y, ai,j(Y ) = 0 for j > i, as we noted after (5).
Remark 2. By using the conversion formula (7), one can directly compute
that IC(2) on a GT pattern T is equivalent to the semistandard condition
(9) in YT corresponding to T . On the other hand, IC(1) in T is equivalent
to a rather trivial condition ai,j(YT ) > 0 for all i, j.
If Y is a skew tableau of shape λ/µ, then, using the same argument
as for (9), it is straightforward to see that we can make Y semistandard
by rearranging elements along each row if and only if
µm+1 +
ℓ
∑
k=1
ak,m+1(Y ) 6 µm +
ℓ−1
∑
k=1
ak,m(Y ) (10)
for 1 6 ℓ 6 n and 1 6 m < n. The Yamanouchi condition in a LR tableau
Y can be expressed as
j
∑
k=1
ai+1,k(Y ) 6
j−1
∑
k=1
ai,k(Y ) (11)
38 The Littlewood-Richardson rule
for 1 6 j 6 n and 1 6 i < n. Here, if j = 1, then the right hand side is 0
as an empty sum and the inequality implies that ai+1,1(Y ) = 0 for i > 1.
Inductively, we can obtain ai+1,ℓ(Y ) = 0 for i > ℓ from the inequality
with j = ℓ. This shows that for an LR tableau Y, ai,j(Y ) = 0 for i > j,
as we noted in Remark 1 (2).
4.4. Bijection between LR tableaux and GZ schemes. We now
establish a bijection between LR tableaux and GZ schemes using Lemma
3. After applying the lemma to an LR tableau, a center section of the
resulting GT pattern is removed. Taking the dual of the removed array we
get the desired GZ scheme. In doing this we observe how the conditions
on the tableau become those of the scheme.
For a specific example of this bijection, see the first half of Example 2.
Theorem 3. There is a bijection φ between LR(λ/µ, ν) and GZ(µ∗, λ∗ −
ν∗, ν∗). In particular, the semistandard and Yamanouchi conditions in L ∈
LR(λ/µ, ν) are equivalent to, respectively, the interlacing and exponent
conditions in φ(L) ∈ GZ(µ∗, λ∗ − ν∗, ν∗).
Proof. Let L ∈ LR(λ/µ, ν) be given. By applying Lemma 3 we find its
corresponding GT pattern T = (t
(i)
j ) for GL2n and remove the bottom
n− 1 rows to achieve a truncated GT pattern of n+ 1 rows. Furthermore,
the truncated pattern for L can be divided into three subtriangular arrays
TX , TY and TZ , as in Figure 2. Note that these are the same size.
TZ
TYTX
Figure 2. Dividing a truncated GT pattern into 3 subpatterns.
The upper left subarray TX is completely determined by λ because of
the Yamanouchi condition (see Remark 1 (2)). The upper right subarray
TY contains only zeroes. Therefore, given fixed λ, µ, and ν, the LR tableau
L ∈ LR(λ/µ, ν) is uniquely determined by TZ . We want to show that the
dual array T ∗
Z of TZ is an element of GZ(µ∗, λ∗ − ν∗, ν∗), and from that
P. Doolan, S. Kim 39
establish a bijection
LR(λ/µ, ν) −→ GZ(µ∗, λ∗ − ν∗, ν∗)
L 7−→ T ∗
Z
.
Let us rewrite the middle subarray TZ as follows by reflecting it over
a horizontal line.
TZ =
t
(n)
1 t
(n)
2 · · · t
(n)
n−1 t
(n)
n
t
(n+1)
2 t
(n+1)
3 · · · t
(n+1)
n
t
(n+2)
3 t
(n+2)
n
. . . . .
.
t
(2n−1)
n
Then µi = t
(n)
i for 1 6 i 6 n and TZ satisfies the interlacing conditions
induced from the truncated GT pattern T , which are assured by the
semistandardness of L. Therefore TZ is a GT pattern of type µ. From the
fact that the weights of TX , TY , and T are (λ1, . . . , λn), (0, . . . , 0), and
(µ1, . . . , µn, ν1, . . . , νn) respectively, it is easy to show that the weight of
TZ is ν∗ − λ∗. Hence its dual T ∗
Z is a GT pattern (see §3.4) of type µ∗
and weight λ∗ − ν∗. Next, we want to show that T ∗
Z satisfies the exponent
conditions.
Let ai,j = ai,j(L), i.e., be the number of i’s in the jth row of L for all
i and j. Then
ai,j = t
(n+i)
j − t
(n+i−1)
j and ak,k = λk − t
(n+k−1)
k (12)
for 1 6 i < j 6 n and 1 6 k 6 n. Since the content of L is ν with
νq =
∑n
k=1 aq,k for 1 6 q 6 n, we can write
(−νi+1) − (−νi) =
n
∑
k=1
(ai,k − ai+1,k) (13)
for 1 6 i < n.
On the other hand, from the Yamanouchi condition (11) in L, we have
j
∑
k=1
ai+1,k 6
j−1
∑
k=1
ai,k or equivalently, ai+1,j 6
j−1
∑
k=1
(ai,k − ai+1,k).
Then, using this inequality, (13) becomes
(−νi+1) − (−νi) >
n
∑
k=j+1
(ai,k − ai+1,k) + ai,j
40 The Littlewood-Richardson rule
and the right hand side is, via (12), the exponents of T ∗
Z . Therefore,
T ∗
Z ∈ GZ(µ∗, λ∗ − ν∗, ν∗).
4.5. A bijection between LR tableaux and hives. Composing
Theorem 3 and Theorem 2 (1) gives a bijection between the set of LR
tableaux and the set of hives.
GZ(µ∗, λ∗ − ν∗, ν∗)
ւր ցտ
LR(λ/µ, ν) H◦(µ, ν, λ)
Corollary 1. [18, (3.3)] There is a bijection between LR(λ/µ, ν) and
H◦(µ, ν, λ).
Proof. For L ∈ LR(λ/µ, ν), we compute the corresponding truncated
GT pattern and its middle subarray TZ . Then, by Theorem 3, its dual
T ∗
Z belongs to GZ(µ∗, λ∗ − ν∗, ν∗). Similarly, for H ∈ H◦(µ, ν, λ), its
first derived subarray T1(H) satisfies T ∗
1 (H) ∈ GZ(µ∗, λ∗ − ν∗, ν∗) by
Theorem 2. We can therefore identify a H such that T1(H) = TZ and
this gives us a bijection from LR(λ/µ, ν) to H◦(µ, ν, λ).
We give an example of Corollary 1 below.
Example 2. We start by using Theorem 3 to map the LR tableau below
to a GT pattern (whose dual array is a GZ scheme).
Let λ = (11, 7, 5, 3), µ = (5, 3, 1, 0) and ν = (7, 5, 3, 2). The LR tableau
from LR(λ/µ, ν)
1 1 1 1 1 1
1 2 2 2
2 3 3 3
2 4 4
considered as an object for GL4, corresponds to the following truncated
GT pattern.
11 7 5 3 0 0 0 0
11 7 5 1 0 0 0
11 7 2 1 0 0
11 4 1 0 0
5 3 1 0
P. Doolan, S. Kim 41
Taking out the middle section, we find TZ is
5 3 1 0
4 1 0
2 1
1
with a dual array T ∗
Z belonging to GZ(µ∗, λ∗ − ν∗, ν∗).
For the second half of the process, we apply the bijection between
hives and GZ schemes (Theorem 2 (1)) to T ∗
Z . We know the corresponding
hive H will have boundaries given by µ = (5, 3, 1, 0), ν = (7, 5, 3, 2) and
λ = (11, 7, 5, 3) so that it appears as follows
0
5 11
8 p 18
9 q r 23
9 16 21 24 26
with some inner entries p, q and r. Adding (T ∗
Z)∗ = TZ along the NE-SW
diagonals as if it were T1(H) we find p = 15, q = 16 and r = 20.
Of course, there are many known bijections between LR tableaux and
hives. For example, in the appendix of [5] Fulton gave a bijection between
LR tableaux and hives using contratableaux. It is interesting to note that
his first step is to construct partitions from the hive that are equivalent to
the derived t-array T1. However, that approach diverges from ours once
he uses the partitions to form a contratableau.
Our Corollary 1 is simpler than most other bijections between LR
tableaux and hives, such as the one by Fulton, but is in fact equivalent
to [18, (3.3)]. There, the authors also take an LR tableau and compute
the truncated GT pattern via Lemma 3. They then take row sums in
the pattern and separate out a bottom section, which becomes the hive.
This is simply our process in reverse, since we separate a section of the
truncated GT pattern in Theorem 3 by removing TZ , and then successively
add those entries to the boundary of the hive in Theorem 2 (1).
The key difference, however, is that here we establish GZ schemes as
an intermediate object in the bijection, which is absent from the simple
and elegant treatment in [18]. This provides background as to why their
simple bijection works, and also allows us to track the conditions as they
move between objects (see tables 1 and 2). We also note that Corollary
42 The Littlewood-Richardson rule
1 is not the main focus of our discussion. Rather, it is an interesting
consequence that appears when piecing together two sets of combinatorial
theory – the derived t-arrays of hives on one hand, and the classical
bijection between tableaux and t-arrays on the other.
To complete the section we combine the two approaches for some
insights. Though not clear from our presentation, the elegant formula
[18, (3.4)] states that the elements of the hive H = (hl,m) are given by
hl,m =
the number of empty boxes and entries 6 l
in the first m rows of the LR tableau.
Finally, in proving [18, Proposition 3.2], King et al. show that, under
their bijection, conditions1 on hives correspond to conditions on LR
tableaux. Table 1 summarises these equivalences.
Hive LR tableau
RC(1) trivial
RC(2) Semistandard condition
RC(3) Yamanouchi
Table 1. Equivalent LR tableau and hive conditions in [18, (3.3)]
Using our results from Proposition 1, Theorem 2, Remark 2 and
Theorem 3 we are able to add a middle column showing the equivalent
conditions in the intermediate GZ scheme object. See Table 2.
Hive GZ scheme LR tableau
RC(1) IC(1) trivial
RC(2) IC(2) Semistandard condition
RC(3) Exponents Yamanouchi
Table 2. Equivalent LR tableau, GZ scheme and hive conditions in Corollary 1
5. LR Tableaux and GT Patterns II
In this section, we show that the semistandard and Yamanouchi
conditions for tableaux are equivalent to, respectively, the exponent and
semistandard conditions for their companion tableaux. This correspondence
1The conditions RC(1), RC(2) and RC(3) are referred to as R2, R3 and R1 respec-
tively by [18].
P. Doolan, S. Kim 43
is obtained by taking the transpose of matrices describing tableaux. As
a result, we show that the companion tableaux of LR tableaux are GZ
schemes under the tableau-pattern bijection.
5.1. For a (skew) semistandard tableau Y , as in (5), we let ai,j(Y )
denote the number of i’s in the jth row.
Definition 5. For a (skew) semistandard tableau Y , its companion tableau
Y c is defined as a non-skew tableau whose entries are weakly increasing
along each row and whose number of i’s in the jth row is equal to aj,i(Y );
that is, for 1 6 i, j 6 n,
ai,j(Y c) = aj,i(Y ). (14)
Example 3. For the LR tableau Y from Example 2, the associated
matrix is
ai,j(Y ) =
6 1 0 0
0 3 1 1
0 0 3 0
0 0 0 2
.
Then, from its transpose, we have the following companion tableau Y c.
1 1 1 1 1 1 2
2 2 2 3 4
3 3 3
4 4
Note that Y is of shape (11, 7, 5, 3)/(5, 3, 1, 0) and content (7, 5, 3, 2) while
its companion tableau Y c is of shape (7, 5, 3, 2) and content (6, 4, 4, 3),
which is (11, 7, 5, 3) − (5, 3, 1, 0). The GT pattern TY c corresponding to
Y c is
7 5 3 2
7 4 3
7 3
6
.
We want to show that this correspondence Y 7→ TY c gives another bijection
from the set of LR tableaux to the set of GZ schemes.
In [29], van Leeuwen replaced the Yamanouchi condition in LR
tableaux with the semistandard condition in their companion tableaux.
Here, we show that the semistandard condition in LR tableaux has a
counterpart in the companion tableaux as well, and then we identify the
companion tableaux as an independent object equivalent to GZ schemes.
44 The Littlewood-Richardson rule
Theorem 4. For a LR tableau Y , we let Y c denote its companion tableau
and let TY c denote the GT pattern corresponding to Y c. The map ψ(Y ) =
TY c gives a bijection from LR(λ/µ, ν) to GZ(ν, λ− µ, µ). In particular,
the Yamanouchi and semistandard conditions in Y are equivalent to,
respectively, the interlacing condition IC(2) and the exponent condition
in TY c.
Proof. From (14), Y is a tableau of shape λ/µ if and only if the content
of Y c is equal to λ−µ. The content of Y is equal to the shape of Y c. The
type and weight of TY c are therefore ν and λ− µ, respectively.
Recall the Yamanouchi condition in Y (11): for 0 6 i < n and
1 6 j < n,
i
∑
k=1
aj,k(Y ) >
i+1
∑
k=1
aj+1,k(Y ). (15)
Since ai,j(Y ) = aj,i(Y
c) for all i and j, this inequality, in terms of the
entries in Y c, is saying that the number of entries less than or equal to
i+ 1 in the (j+ 1)th row is not more than the number of entries less than
or equal to i in the jth row. It is the semistandard condition for Y c and
therefore the interlacing condition for TY c .
To show this, consider expressing the elements of the GT pattern
TY c = (t
(i)
j ) in terms of ai,j(Y
c). From the standard bijection between
semistandard tableaux and GT patterns, (7), we have
t
(i)
j =
i
∑
k=1
ak,j(Y c)
where ai,j(Y c) is the number of i entries in the jth row of Y c.
Consider the interlacing condition IC(2): t
(i)
j > t
(i+1)
j+1 where 0 6 i < n
and 1 6 j < n. Writing this with the above relation gives
i
∑
k=1
ak,j(Y c) >
i+1
∑
k=1
ak,j+1(Y c) ⇔
i
∑
k=1
aj,k(Y ) >
i+1
∑
k=1
aj+1,k(Y )
which is exactly the expression for the Yamanouchi condition (15). It can
be similarly shown that, as mentioned in Remark 2, IC(1) is equivalent
to ai,j(Y ) > 0.
Using (10), the semistandard condition for Y says we have, for all
1 6 ℓ 6 n and 1 6 m < n,
(
ℓ
∑
k=1
ak,m+1(Y ) −
ℓ−1
∑
k=1
ak,m(Y )
)
6 (µm − µm+1) (16)
P. Doolan, S. Kim 45
or
ℓ−1
∑
k=1
(am+1,k(Y c) − am,k(Y c)) + am+1,ℓ(Y
c) 6 (µm − µm+1) .
To finish our proof, it is enough to show that the left hand side of the
above inequality is the exponent ε
(m)
ℓ (TY c). This can be easily seen, by
using (8), as
ε
(m)
ℓ (TY c) =
∑
16h<ℓ
(
t
(m+1)
h − 2t
(m)
h + t
(m−1)
h
)
+
(
t
(m+1)
ℓ − t
(m)
ℓ
)
=
∑
16h<ℓ
(
m+1
∑
k=h
ak,h(Y c) − 2
m
∑
k=h
ak,h(Y c) +
m−1
∑
k=h
ak,h(Y c)
)
+
(
m+1
∑
k=ℓ
ak,ℓ(Y
c) −
m
∑
k=ℓ
ak,ℓ(Y
c)
)
=
∑
16k<ℓ
(am+1,k(Y c) − am,k(Y c)) + am+1,ℓ(Y
c).
We now have an alternative proof of Corollary 1.
Corollary 2. There is a bijection between LR(λ/µ, ν) and H◦(µ, ν, λ).
Proof. We can map any Y ∈ LR(λ/µ, ν) to TY c ∈ GZ(ν, λ − µ, µ) via
the bijection in Theorem 4. From Theorem 2 there is a bijection between
H◦(µ, ν, λ) and GZ(ν, λ− µ, µ) through the derived t-array T2 of a hive.
The composition of the first bijection with the inverse of the second then
gives a bijection which assigns Y ∈ LR(λ/µ, ν) to H ∈ H◦(µ, ν, λ) if and
only if T2(H) = TY c .
Acknowledgement
We thank Roger Howe and Victor Protsak for helpful conversations
regarding several aspects of this work.
References
[1] A. D. Berenstein and A. N. Kirillov, Groups generated by involutions, Gelfand-
Tsetlin patterns, and combinatorics of Young tableaux. Algebra i Analiz 7 (1995),
no. 1, 92–152; translation in St. Petersburg Math. J. 7 (1996), no. 1, 77–127.
[2] A. D. Berenstein and A. V. Zelevinsky, Tensor product multiplicities and convex
polytopes in partition space. J. Geom. Phys. 5 (1988), no. 3, 453–472.
46 The Littlewood-Richardson rule
[3] A. D. Berenstein and A. V. Zelevinsky, Involutions on Gelfand-Tsetlin schemes
and multiplicities in skew GLn-modules. (Russian) Dokl. Akad. Nauk SSSR 300
(1988), no. 6, 1291–1294; translation in Soviet Math. Dokl. 37 (1988), no. 3,
799–802.
[4] A. D. Berenstein and A. V. Zelevinsky, Triple multiplicities for sl(r + 1) and
the spectrum of the exterior algebra of the adjoint representation. J. Algebraic
Combin. 1 (1992), no. 1, 7–22.
[5] A. S. Buch, The saturation conjecture (after A. Knutson and T. Tao). With an
appendix by William Fulton, Enseign. Math. (2) 46 (2000), no. 1-2, 43–60.
[6] V. I. Danilov and G. A. Koshevoi, Arrays and the combinatorics of Young
tableaux, Russian Mathematical Surveys, Volume 60(2005), no. 2, 269–334.
[7] W. Fulton, Young tableaux. With applications to representation theory and
geometry. London Mathematical Society Student Texts, 35. Cambridge University
Press, Cambridge, 1997.
[8] W. Fulton, Eigenvalues, invariant factors, highest weights, and Schubert calculus.
Bull. Amer. Math. Soc. (N.S.) 37 (2000), no. 3, 209–249.
[9] W. Fulton and J. Harris, Representation theory. A first course. Graduate Texts in
Mathematics, 129. Readings in Mathematics. Springer-Verlag, New York, 1991.
[10] I. M. Gelfand and M. L. Tsetlin, Finite-dimensional representations of the group
of unimodular matrices. Doklady Akad. Nauk SSSR (N.S.) 71, (1950), 825–828.
[11] I.M. Gelfand and A. V. Zelevinskĭı, Polyhedra in a space of diagrams and the
canonical basis in irreducible representations of gl
n
. Functional Anal. Appl. 19
(1985), no. 2, 141–144.
[12] I.M. Gelfand and A.V. Zelevinskĭı, Multiplicities and regular bases for gl
n
. Group-
theoretic methods in physics, Vol. 2 (Russian) (Yurmala, 1985), 22–31, Nauka,
Moscow, 1986.
[13] N. Gonciulea and V. Lakshmibai, Degenerations of flag and Schubert varieties to
toric varieties. Transform. Groups 1 (1996), no. 3, 215–248.
[14] R. Goodman and N. R. Wallach, Symmetry, representations, and invariants.
Graduate Texts in Mathematics, 255. Springer, Dordrecht, 2009.
[15] R. Howe and S.T. Lee, Why should the Littlewood-Richardson rules be true?,
Bull. Amer. Math. Soc. 49 (2012), 187–236.
[16] R. Howe, E.-C. Tan, and J. F. Willenbring, A basis for the GLn tensor product
algebra. Adv. Math. 196 (2005), no. 2, 531–564.
[17] R. Howe, S. Jackson, S. T. Lee, E.-C. Tan, J. Willenbring, Toric degeneration of
branching algebras. Adv. Math. 220 (2009), no. 6, 1809–1841.
[18] R. C. King, C. Tollu, and F. Toumazet, The hive model and the polynomial
nature of stretched Littlewood-Richardson coefficients. Sem. Lothar. Combin.
54A (2005/07), Art. B54Ad, 19 pp.
[19] R. C. King, C. Tollu, and F. Toumazet, The hive model and the factorisation of
Kostka coefficients. Sem. Lothar. Combin. 54A (2005/07), Art. B54Ah, 22 pp.
[20] S. Kim, Standard monomial theory for flag algebras of GL(n) and Sp(2n). J.
Algebra 320 (2008), no. 2, 534–568.
P. Doolan, S. Kim 47
[21] A. Knutson and T. Tao, The honeycomb model of GLn(C) tensor products.
I. Proof of the saturation conjecture. J. Amer. Math. Soc. 12 (1999), no. 4,
1055–1090.
[22] A. Knutson, T. Tao, and C. Woodward, The honeycomb model of GLn(C) tensor
products. II. Puzzles determine facets of the Littlewood-Richardson cone. J.
Amer. Math. Soc. 17 (2004), no. 1, 19–48.
[23] M. Kogan and E. Miller, Toric degeneration of Schubert varieties and Gelfand-
Tsetlin polytopes. Adv. Math. 193 (2005), no. 1, 1–17.
[24] I. G. Macdonald, Symmetric functions and Hall polynomials. Second edition.
Oxford Mathematical Monographs. Oxford Science Publications. The Clarendon
Press, Oxford University Press, New York, 1995.
[25] I. Pak and E. Vallejo, Combinatorics and geometry of Littlewood-Richardson
cones. European J. Combin. 26 (2005), no. 6, 995–1008.
[26] R. P. Stanley, Enumerative combinatorics. Vol. 2. Cambridge Studies in Advanced
Mathematics, 62. Cambridge University Press, Cambridge, 1999.
[27] H. Tamvakis, The connection between representation theory and Schubert calculus.
Enseign. Math. (2) 50 (2004), no. 3-4, 267–286.
[28] H. Thomas and A. Yong, An S3-symmetric Littlewood-Richardson rule. Math.
Res. Lett. 15 (2008), no. 5, 1027–1037.
[29] M.A.A. van Leeuwen, The Littlewood-Richardson rule, and related combinatorics.
Interaction of combinatorics and representation theory, 95–145, MSJ Mem., 11,
Math. Soc. Japan, Tokyo, 2001.
Contact information
Patrick Doolan School of Mathematics and Physics
The University of Queensland
St Lucia, QLD 4072, Australia
E-Mail(s): patrick.doolan@uqconnect.edu.au
Sangjib Kim Department of Mathematics
Korea University
145 Anam-ro, Seongbuk-gu,
Seoul, 02841, South Korea
E-Mail(s): sk23@korea.ac.kr
Received by the editors: 22.09.2015
and in final form 04.10.2015.
|