## Column strict tableaux

Last update: 30 January 2012

## Column strict tableaux

A letter is an element of $B\left({\epsilon }_{1}\right)= {{\epsilon }_{1},...,{\epsilon }_{n}}$ and a word of length $k$ is an element of $B ε1 ⊗k = εi1 ⊗⋯⊗ εik 1≤i1,...,ik≤n .$ For $1\le i\le n-1$ define $fi˜: B ε1 ⊗k → B ε1 ⊗k ∪{0} and ei˜: B ε1 ⊗k → B ε1 ⊗k ∪{0}$ as follows. For $b\in B{\left({\epsilon }_{1}\right)}^{\otimes k},$
 place $+1$ under each ${\epsilon }_{i}$ in $b$, (5.39) place $-1$ under each ${\epsilon }_{i+1}$ in $b$, and place $0$ under each ${\epsilon }_{j}$, $j\ne i$, $i+1$.
Ignoring 0s, successively pair adjacent $\left(+1,-1\right)$ pairs to obtain a sequence of unpaired -1s and +1s (after pairing and ignoring 0s). Then A partition is a collection $\lambda$ 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 $\lambda$ are indexed from the top to bottom and left to right, respectively.
 The parts of $\lambda$ are ${\lambda }_{i}=$(the number of boxes in row $i$ of $\lambda$), (5.41) the length of $\lambda$ is $l\left(\lambda \right)=$ (the number of rows of $\lambda$), the size of $\lambda$ is $|\lambda |={\lambda }_{1}+\cdots +{\lambda }_{l\left(\lambda \right)}=$ (the number of boxes of $\lambda$).
Then $\lambda$ is determined by (and identified with) the sequence $\lambda =\left({\lambda }_{1},...,{\lambda }_{l}\right)$ of positive integers such that ${\lambda }_{1}\ge {\lambda }_{2}\ge \cdots \ge {\lambda }_{l}>0,$ where $l=l\left(\lambda \right).$ For example,

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

1. the rows are weakly increasing from left to right,
2. the columns are strictly increasing from top to bottom.
If $p$ is a column strict tableaux write $\mathrm{shp}\left(p\right)$ and $\mathrm{wt}\left(p\right)$ for the shape and the weight of $p$ so that For example,

For a partition $\lambda$ and a sequence $\mu =\left({\mu }_{1},...,{\mu }_{n}\right)\in {ℤ}_{\ge 0}^{n}$ of nonnegative integers write Let $\lambda$ be a partition with $k$ boxes and let The set $B\left(\lambda \right)$ is a subset of $B{\left({\epsilon }_{1}\right)}^{\otimes k}$ via the injection

where the arabic reading of $p$ is ${\epsilon }_{{i}_{1}}\otimes {\epsilon }_{{i}_{2}}\otimes \cdots \otimes {\epsilon }_{{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 $\lambda =\left({\lambda }_{1},...,{\lambda }_{n}\right)$ be a partition with $k$ boxes. Then $B\left(\lambda \right)$ is the subset of $B{\left({\epsilon }_{1}\right)}^{\otimes k}$ generated by under the action of the operators

Proof.
If $P=P\left(b\right)$ is a filling of the shape $\lambda$ then ${b}_{{i}_{1}}\otimes \cdots \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 $\lambda$ with 1s in the first row, 2s in the second row, and so on. Define operators $\stackrel{˜}{{e}_{i}}$ and $\stackrel{˜}{{f}_{i}}$ on a filling of $\lambda$ by To prove the proposition we shall show that if $P$ is a column strict tableaux of shape $\lambda$ then
1. $\stackrel{˜}{{e}_{i}}P$ and $\stackrel{˜}{{f}_{i}}P$ are column strict tableaux,
2. $P$ can be obtained by applying a sequence of $\stackrel{˜}{{f}_{i}}$ to ${P}_{\lambda }.$
Let ${P}^{\left(j\right)}$ be the column strict tableau formed by the entries of $P$ which are $\le j$ and let ${\lambda }^{\left(j\right)}=\mathrm{shp}\left({P}^{\left(j\right)}\right).$ This conversion identifies $P$ with the sequence
1. Let us analyze the action of $\stackrel{˜}{{e}_{i}}$ and $\stackrel{˜}{{f}_{i}}$ on $P$. The sequence of +1, -1, 0 constructed via (5.39) is given by
 placing $+1$ in each box of ${\lambda }^{\left(i\right)}/{\lambda }^{\left(i-1\right)}$, placing $-1$ in each box of ${\lambda }^{\left(i+1\right)}/{\lambda }^{\left(i\right)}$, placing $0$ in each box of ${\lambda }^{\left(j\right)}/{\lambda }^{\left(j-1\right)}$, for $j\ne i,i+1$,
and reading the resulting filling in Arabic reading order. The process of removing $\left(+1,-1\right)$ pairs can be executed on the horizontal strips ${\lambda }^{\left(i+1\right)}/{\lambda }^{\left(i\right)}$ and ${\lambda }^{\left(i\right)}/{\lambda }^{\left(i-1\right)},$
with the effect that the entries in any configuration of boxes of the form $+1 +1 ⋯ +1 -1 -1 ⋯ -1$ will be removed. Additional +1, -1 pairs will also be removed and the final sequence $(5.44) -1 -1 ⋯ -1 ⏟ di- p +1 +1 ⋯ +1 ⏟ di+ p$ will correspond to a configuration of the form
The rightmost -1 in the sequence (5.40) corresponds to a box in ${\lambda }^{\left(i+1\right)}/{\lambda }^{\left(i\right)}$ which is leftmost in its row and which does not cover a box of ${\lambda }^{\left(i\right)}/{\lambda }^{\left(i-1\right)}.$ Similarly the leftmost +1 in the sequence correponds to a box in ${\lambda }^{\left(i\right)}/{\lambda }^{\left(i-1\right)}$ which is rightmost in its row and which does not have a box of ${\lambda }^{\left(i+1\right)}/{\lambda }^{\left(i\right)}$ covering it. These conditions guarantee that $\stackrel{˜}{{e}_{i}}P$ and $\stackrel{˜}{{f}_{i}}P$ are column strict tableaux.
2. The tableau $P$ is obtained from ${P}_{\lambda }$ by applying a sequence of $\stackrel{˜}{{f}_{i}}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 can be used to produce a column strict tableau ${P}_{n}$ 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 $\le n-1$ is ${P}_{{\lambda }^{\left(n-1\right)}}.$
Iterating the process and applying a sequence of operators to the tableau ${P}_{n}$ can be used to produce a tableau ${P}_{n-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 $\le n-2$ is ${P}_{{\lambda }^{\left(n-2\right)}}.$
The tableau $P$ is obtained after a total of $n$ iterations of this process.

$\square$

## 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.