Column strict tableaux

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 30 January 2012

Column strict tableaux

A letter is an element of

B (ε_{1}) =  {ε_{1} ... ε_{n}}

and a word of length $k$ is an element of

B {(ε_{1})}^{\otimes k} =  {ε_{i_{1}} \otimes \dots \otimes ε_{i_{k}}| 1 \leq i_{1}, ..., i_{k} \leq n}  .

For

1 \leq i \leq n - 1

define

\tilde{f_{i}} : B {(ε_{1})}^{\otimes k} \to B {(ε_{1})}^{\otimes k} \cup {0} and \tilde{e_{i}} : B {(ε_{1})}^{\otimes k} \to B {(ε_{1})}^{\otimes k} \cup {0}

as follows. For

b \in B {(ε_{1})}^{\otimes k},

		place $+ 1$ under each $ε_{i}$ in $b$ ,
(5.39)		place $- 1$ under each $ε_{i + 1}$ in $b$ , and
		place $0$ under each $ε_{j}$ , $j \neq i$ , $i + 1$ .

Ignoring 0s, successively pair adjacent

(+ 1, - 1)

pairs to obtain a sequence of unpaired -1s and +1s

\begin{array}{lcl} (5.40) & - 1 - 1 - 1 - 1 - 1 - 1 - 1 + 1 + 1 + 1 + 1 \end{array}

(after pairing and ignoring 0s). Then

\begin{array}{rcl} \tilde{f_{i}} b & = & same as b except the letter corresponding to the leftmost unpaired + 1 is changed to ε_{i + 1}, \\ \tilde{e_{i}} b & = & same as b except the letter corresponding to the rightmost unpaired - 1 is changed to ε_{i} . \end{array}

\begin{array}{rcl} If there is no unpaired + 1 after pairing then & \tilde{f_{i}} b = 0 . \\ If there is no unpaired - 1 after pairing then & \tilde{e_{i}} b = 0 . \end{array}

A partition is a collection

λ

of boxes in a corner where the convention is that gravity goes up and to the left. As for matrices, the rows and columns of

λ

are indexed from the top to bottom and left to right, respectively.

	The parts of $λ$ are	$λ_{i} =$ (the number of boxes in row $i$ of $λ$ ),
(5.41)	the length of $λ$ is	$l (λ) =$ (the number of rows of $λ$ ),
	the size of $λ$ is	$\| λ \| = λ_{1} + \dots + λ_{l (λ)} =$ (the number of boxes of $λ$ ).

Then

λ

is determined by (and identified with) the sequence

λ = (λ_{1} ... λ_{l})

of positive integers such that

λ_{1} \geq λ_{2} \geq \dots \geq λ_{l} > 0,

where

l = l (λ) .

For example,

Let $λ$ be a partition and let $μ = (μ_{1} ... μ_{n}) \in ℤ_{\geq 0}^{n}$ be a sequence of nonnegative integers. A column strict tableaux of shape $λ$ and weight $μ$ is a filling of the boxes of $λ$ with $μ_{1}$ 1s, $μ_{2}$ 2s, ..., $μ_{n}$ $n$ s, such that

the rows are weakly increasing from left to right,
the columns are strictly increasing from top to bottom.

p

is a column strict tableaux write

shp (p)

and

wt (p)

for the shape and the weight of

p

so that

\begin{array}{rcl} shp (p) = (λ_{1} ... λ_{n}), & where & λ_{i} = number of boxes in row i of p, and \\ wt (p) = (μ_{1} ... μ_{n}), & where & μ_{i} = number of i s in p . \end{array}

For example,

For a partition

λ

and a sequence

μ = (μ_{1} ... μ_{n}) \in ℤ_{\geq 0}^{n}

of nonnegative integers write

(5.42) \begin{array}{rcl} B (λ) & = &  {column strict tableaux p| shp (p) = λ} , \\ B {(λ)}_{μ} & = &  {column strict tableaux p| shp (p) = λ and wt (p) = μ}  . \end{array}

Let

λ

be a partition with

k

boxes and let

B (λ) = {column strict tableaux of shape λ} .

The set

B (λ)

is a subset of

B {(ε_{1})}^{\otimes k}

via the injection

\begin{array}{rcl} B (λ) & ↪ & B {(ε_{1})}^{\otimes k} \\ p & \mapsto & (the arabic reading of p) \end{array}

where the arabic reading of $p$ is $ε_{i_{1}} \otimes ε_{i_{2}} \otimes \dots \otimes ε_{i_{k}}$ if the entries of $p$ are $i_{1} i_{2} ... i_{k}$ read right to left by rows with the rows read in sequence beginning with the first row.

Let $λ = (λ_{1} ... λ_{n})$ be a partition with $k$ boxes. Then $B (λ)$ is the subset of $B {(ε_{1})}^{\otimes k}$ generated by $p_{λ} = \underset{λ_{1} factors}{\underset{⏟}{ε_{1} \otimes ε_{1} \otimes \dots \otimes ε_{1}}} \otimes \underset{λ_{2} factors}{\underset{⏟}{ε_{2} \otimes ε_{2} \otimes \dots \otimes ε_{2}}} \otimes \dots \otimes \underset{λ_{n} factors}{\underset{⏟}{ε_{n} \otimes ε_{n} \otimes \dots \otimes ε_{n}}}$ under the action of the operators $\tilde{e_{i}}, \tilde{f_{i}}, 1 \leq i \leq n .$

Proof.

P = P (b)

is a filling of the shape

λ

then

b_{i_{1}} \otimes \dots \otimes b_{i_{k}} = b

is obtained from

P

by reading the entries of

P

in arabic reading order (right to left across rows and from top to bottom down the page). The tableaux
is the column strict tableaux of shape

λ

with 1s in the first row, 2s in the second row, and so on. Define operators

\tilde{e_{i}}

and

\tilde{f_{i}}

on a filling of

λ

\tilde{e_{i}} P = P (\tilde{e_{i}} b) \tilde{f_{i}} P = P (\tilde{f_{i}} b), if P = P (b) .

To prove the proposition we shall show that if

P

is a column strict tableaux of shape

λ

then

$\tilde{e_{i}} P$ and $\tilde{f_{i}} P$ are column strict tableaux,
$P$ can be obtained by applying a sequence of $\tilde{f_{i}}$ to $P_{λ} .$

Let

P^{(j)}

be the column strict tableau formed by the entries of

P

which are

\leq j

and let

λ^{(j)} = shp (P^{(j)}) .

This conversion identifies

P

with the sequence

\begin{array}{l} P = (\emptyset = λ^{(0)} \subseteq λ^{(1)} \subseteq \dots \subseteq λ^{(n)} = λ), where \\ λ^{(i)} / λ^{(i - 1)} is a horizontal strip for each 1 \leq i \leq n . \end{array}

Let us analyze the action of

\tilde{e_{i}}

and

\tilde{f_{i}}

P

. The sequence of +1, -1, 0 constructed via (5.39) is given by

		placing $+ 1$ in each box of $λ^{(i)} / λ^{(i - 1)}$ ,
		placing $- 1$ in each box of $λ^{(i + 1)} / λ^{(i)}$ ,
		placing $0$ in each box of $λ^{(j)} / λ^{(j - 1)}$ , for $j \neq i, i + 1$ ,

and reading the resulting filling in Arabic reading order. The process of removing

(+ 1, - 1)

pairs can be executed on the horizontal strips

λ^{(i + 1)} / λ^{(i)}

and

λ^{(i)} / λ^{(i - 1)},

with the effect that the entries in any configuration of boxes of the form

\begin{array}{cccc} + 1 & + 1 & \dots & + 1 \\ - 1 & - 1 & \dots & - 1 \end{array}

will be removed. Additional +1, -1 pairs will also be removed and the final sequence

\begin{matrix} (5.44) & \underset{d_{i}^{-} (p)}{\underset{⏟}{ - 1 - 1 \dots - 1 }} \underset{d_{i}^{+} (p)}{\underset{⏟}{ + 1 + 1 \dots + 1 }} \end{matrix}

will correspond to a configuration of the form
The rightmost -1 in the sequence (5.40) corresponds to a box in

λ^{(i + 1)} / λ^{(i)}

which is leftmost in its row and which does not cover a box of

λ^{(i)} / λ^{(i - 1)} .

Similarly the leftmost +1 in the sequence correponds to a box in

λ^{(i)} / λ^{(i - 1)}

which is rightmost in its row and which does not have a box of

λ^{(i + 1)} / λ^{(i)}

covering it. These conditions guarantee that

\tilde{e_{i}} P

and

\tilde{f_{i}} P

are column strict tableaux.

The tableau P is obtained from Pλ by applying a sequence of fi˜P in the following way. Applying the operator fn,i˜ = fn-1˜ ⋯ fi+1˜ fi˜ to Pλ will change the rightmost i in row i to n. A sequence of applications of fn,i˜, as i decreases (weakly) from n-1 to 1, can be used to produce a column strict tableau Pn in which
1. the entries equal to $n$ match the entries equal to $n$ in $P$ , and
2. the subtableau of $P_{n}$ containing the entries $\leq n - 1$ is $P_{λ^{(n - 1)}} .$
Iterating the process and applying a sequence of operators fn-1,i˜, as i decreases (weakly) from n-2 to 1, to the tableau Pn can be used to produce a tableau Pn-1 in which
1. the entries equal to $n$ and $n - 1$ match the entries equal to $n$ and $n - 1$ in $P$ , and
2. the subtableau of $P_{n - 1}$ containing the entries $\leq n - 2$ is $P_{λ^{(n - 2)}} .$
The tableau P is obtained after a total of n iterations of this process.

$□$

Notes and References

The above notes are taken from section 5.7 of the paper

[Ram] A. Ram, Alcove Walks, Hecke Algebras, Spherical Functions, Crystals and Column Strict Tableaux, Pure and Applied Mathematics Quarterly 2 no. 4 (2006), 963-1013.

References

[BD] Y. Billig and M. Dyer, Decompositions of Bruhat type for the Kac-Moody groups, Nova J. Algebra Geom. 3 no. 1 (1994), 11-31.

[Br] M. Brion, Positivity in the Grothendieck group of complex flag varieties, J. Algebra 258 no. 1 (2002), 137-159.

[GL] S. Gaussent and P. Littelmann, LS galleries, the path model, and MV cycles, Duke Math. J. 127 no. 1 (2005), 35-88.

[GR] S. Griffeth and A. Ram, Affine Hecke algebras and the Schubert calculus, European J. Combin. 25 no. 8 (2004), 1263-1283.

[Ha] T. Haines, Structure constants for Hecke and representation rings, Int. Math. Res. Not. 39 (2003), 2103-2119.

[IM] N. Iwahori and H. Hatsumoto, On some Bruhat decomposition and the structure of the Hecke rings of $𝔭 -$ adic Chevalley groups, Inst. Hautes Études Sci. Publ. Math. 25 (1965), 5-48.

[Ki] K. Killpatrick, A Combinatorial Proof of a Recursion for the q-Kostka Polynomials, J. Comb. Th. Ser. A 92 (2000), 29-53.

[KM] M. Kapovich and J.J. Millson, A path model for geodesics in Euclidean buildings and its applications to representation theory, arXiv: math.RT/0411182.

[LS] A. Lascoux and M.P. Schützenberger, Le monoïde plaxique, Quad. Ricerce Sci. 109 (1981), 129-156.

page history