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 k = εi1 εik 1i1,...,ikn . For 1in-1 define fi˜: B ε1 k B ε1 k {0} and ei˜: B ε1 k B ε1 k {0} as follows. For b B ε1 k ,
  place +1 under each εi in b,
(5.39)   place -1 under each εi+1 in b, and
  place 0 under each εj, ji, i+1.
Ignoring 0s, successively pair adjacent +1-1 pairs to obtain a sequence of unpaired -1s and +1s (5.40)   -1 -1 -1 -1 -1 -1 -1 +1 +1 +1 +1  (after pairing and ignoring 0s). Then fi˜b = same as  b  except the letter corresponding to the leftmost unpaired  +1  is changed to εi+1, ei˜b = same as  b  except the letter corresponding to the rightmost unpaired  -1  is changed to εi. If there is no unpaired +1 after pairing then   fi˜b=0. If there is no unpaired -1 after pairing then   ei˜b=0. 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++λlλ= (the number of boxes of λ).
Then λ is determined by (and identified with) the sequence λ = λ1...λl of positive integers such that λ1λ2λl>0, where l=lλ. For example,

Layer 1 553311 =

Let λ be a partition and let μ= μ1...μn 0n 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 ns, 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 shpp and wtp for the shape and the weight of p so that shpp = λ1...λn , where λi=  number of boxes in row i of p, and wtp = μ1...μn , where μi=  number of is in p. For example,

Layer 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 6 6 7 7 p= has shpp = 9774210 and wtp = 7655322.

For a partition λ and a sequence μ= μ1...μn 0n of nonnegative integers write (5.42) Bλ = column strict tableaux   p shpp =λ , Bλμ = column strict tableaux   p shpp =λ   and   wtp =μ . Let λ be a partition with k boxes and let Bλ = {column strict tableaux of shape   λ}. The set Bλ is a subset of B ε1 k via the injection B(λ) B ε1 k p (the arabic reading of   p) Layer 1 (5.43) iλ1 i λ1 +λ2 ik i λ1 +1 i2 i1 εi1 εi2 εik

where the arabic reading of p is εi1 εi2 εik if the entries of p are i1 i2 ... ik 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 k generated by pλ= ε1 ε1 ε1 λ1   factors ε2 ε2 ε2 λ2   factors εn εn εn λn   factors under the action of the operators ei˜,   fi˜,   1in.

Proof.
If P=P(b) is a filling of the shape λ then bi1 bik =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 Layer 1 Pλ= P(pλ) = 1 1 1 1 1 2 2 2 n n
is the column strict tableaux of shape λ with 1s in the first row, 2s in the second row, and so on. Define operators ei˜ and fi˜ on a filling of λ by ei˜P = P(ei˜b) fi˜P = P(fi˜b), if   P=P(b). To prove the proposition we shall show that if P is a column strict tableaux of shape λ then
  1. ei˜P and fi˜P are column strict tableaux,
  2. P can be obtained by applying a sequence of fi˜ to Pλ.
Let Pj be the column strict tableau formed by the entries of P which are j and let λj = shpPj. This conversion identifies P with the sequence P=( =λ0 λ1 λn=λ), where λi/λi-1   is a horizontal strip for each 1in.
  1. Let us analyze the action of ei˜ and fi˜ on 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 ji,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, Layer 1 + + + + - - - - - - - - + + - - - + + + + - - - - + + + + + + + λ i-1 λ i+1 =
    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 Layer 1 - - - - - + + + + + + + λ i-1 λ i+1 =
    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 ei˜P and fi˜P are column strict tableaux.
  2. 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 Pn containing the entries 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 Pn-1 containing the entries 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