The connection to standard Young tableaux

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

Last update: 13 November 2012

The connection to standard Young tableaux

In this section we shall show that the combinatorics of local regions is a generalization of the combinatorics of standard Young tableaux. Let us first make some general definitions, which we will show later provide generalizations of standard objects in the Young tableaux theory. This section is a (purely combinatorial) study of the local regions in the form which appears in (4.3), and therefore corresponds to the representation theory of affine Hecke algebras when $q$ is not a root of unity.

5.1. Definition

Let $\gamma \in {𝔥}_{ℝ}^{*}$ be dominant and let

$$\begin{array}{ccc}Z\left(\gamma \right)& =& \{\alpha \in R^{+}\mid ⟨\gamma ,\alpha ⟩=0\},P\left(\gamma \right)=\{\alpha \in R^{+}\mid ⟨\gamma ,\alpha ⟩=1\},\\ {ℱ}^{(\gamma ,J)}& =& \{w\in W\mid R\left(w\right)\cap Z\left(\gamma \right)=\varnothing ,R\left(w\right)\cap P\left(\gamma \right)=J\},\end{array}$$

as in (4.3).

1. A local region is a pair $(\gamma ,J)$ such that ${ℱ}^{(\gamma ,J)}$ is nonempty.
2. A ribbon is a local region $(\gamma ,J)$ such that $\gamma$ is regular, i.e., $⟨\gamma ,\alpha ⟩\ne 0$ for all $\alpha \in R\text{.}$
3. An element $\gamma \in \bar{C}$ is calibratable if
   1. for all simple roots ${\alpha }_i,$ $1\le i\le n,$ $⟨\gamma ,{\alpha }_i⟩\ne 0,$ and
   2. for all pairs of simple roots ${\alpha }_i$ and ${\alpha }_j$ such that $\{\alpha \in R_{ij}\mid ⟨\gamma ,\alpha ⟩=0\}\ne \varnothing ,$ the set $\{\alpha \in R_{ij}\mid ⟨\gamma ,\alpha ⟩=1\}$ contains more than two elements.
   3. A skew local region is a local region $(\gamma ,J)$ such that $w\gamma$ is calibratable for all $w\in {ℱ}^{(\gamma ,J)}\text{.}$ All ribbons are skew.
   4. A column (respectively row) reading tableau is a minimal (respectively maximal) element of ${ℱ}^{(\gamma ,J)}$ in the weak Bruhat order.
   5. If $\alpha \in R$ the $\alpha \text{-axial}$ distance for $w\in {ℱ}^{(\gamma ,J)}$ is the value $d_{\alpha }\left(w\right)=⟨w\gamma ,\alpha ⟩\text{.}$

Remarks. (1) Theorem 4.6(b) shows that, up to a shift, the set ${ℱ}^{(\gamma ,J)}$ has a unique maximal and a unique minimal element and is an interval in the weak Bruhat order. This is the fundamental importance of the notions of the row reading and the column reading tableaux. Theorem 6.9 in Section 6 will show how Theorem 4.6(b) is a generalization of a Young tableaux result of Björner and Wachs [Bjo1988, Theorem 7.2].

(2) The definition of skew local regions is forced by the representation theory of the affine Hecke algebra (see Theorem 3.6, the classification of irreducible calibrated representations). In Proposition 6.4 below we shall show that the skew local regions and the ribbons are generalizations of the skew shapes and border strips which are used in the theory of symmetric functions [Mac1995, I, Section 5 and I, Section 3, Exercise 11]

(3) The axial distances control the denominators which appear in the construction of irreducible representations of the affine Hecke algebra in Theorem 3.5. In Section 6.1 we shall see how they are analogues of the axial distances used by A. Young [You1931] in his constructions of the irreducible representations of the symmetric group.

To summarize, a brief dictionary between local regions combinatorics and the Young tableaux combinatorics:

$$\begin{array}{ccc}\text{skew local regions}& \leftrightarrow & \text{skew shapes}\lambda /\mu ,\\ \text{ribbons}& \leftrightarrow & \text{border strips,}\\ \text{local regions}& \leftrightarrow & \text{general configurations of boxes,}\\ {ℱ}^{(\gamma ,J)}& \leftrightarrow & \text{the set of standard tableaux}{ℱ}^{\lambda /\mu }\text{.}\end{array}$$

The remainder of this section and the next section explain in greater detail the conversions indicated in this dictionary.

Let $\{{\epsilon }_1,\dots ,{\epsilon }_n\}$ be an orthonormal basis of ${𝔥}_{ℝ}^{*}={ℝ}^n$ so that each sequence $\gamma =({\gamma }_1,\dots ,{\gamma }_n)\in {ℝ}^n$ is identified with the vector $\gamma =\sum _i{\gamma }_i{\epsilon }_i\text{.}$ The root system of type $A_{n-1}$ is given by the sets

$$R=\{\pm ({\epsilon }_j-{\epsilon }_i)\mid 1\le i,j\le n\}\text{and}{R}^{+}=\{{\epsilon }_j-{\epsilon }_i\mid 1\le i<j\le n\}\text{.}$$

The Weyl group is $W=S_n,$ the symmetric group, acting by permutations of the ${\epsilon }_i\text{.}$

5.3. Partitions, skew shapes, and standard tableaux

A partition $\lambda$ is a collection of $n$ boxes in a corner. We shall conform to the conventions in [Mac1995] and assume that gravity goes up and to the left.

$$$$

Any partition $\lambda$ can be identified with the sequence $\lambda =({\lambda }_1\ge {\lambda }_2\ge \dots )$ where ${\lambda }_i$ is the number of boxes in row $i$ of $\lambda \text{.}$ The rows and columns are numbered in the same way as for matrices. We shall always use the word diagonal to mean a major diagonal. In the example above $\lambda =\left(553311\right)$ and the diagonals of $\lambda$ (from southwest to northeast) contain 1, 1, 1, 2, 3, 3, 2, 2, 2, and 1 box, respectively.

If $\lambda$ and $\mu$ are partitions such that ${\mu }_i\le {\lambda }_i$ for all $i$ write $\mu \subseteq \lambda \text{.}$ The skew shape $\lambda /\mu$ consists of all boxes of $\lambda$ which are not in $\mu \text{.}$ Let $\lambda /\mu$ be a skew shape with $n$ boxes. Number the boxes of each skew shape $\lambda /\mu$ along diagonals from southwest to northeast and

$${\text{write box}}_i\text{to indicate the box numbered}i\text{.}$$

See Example 5.8 below. A standard tableau of shape $\lambda /\mu$ is a filling of the boxes in the skew shape $\lambda /\mu$ with the numbers $1,\dots ,n$ such that the numbers increase from left to right in each row and from top to bottom down each column. Let ${ℱ}^{\lambda /\mu }$ be the set of standard tableaux of shape $\lambda /\mu \text{.}$ Given a standard tableau $p$ of shape $\lambda /\mu$ define the word of $p$ to be the permutation

$$\begin{array}{cc}{w}_p=\left(\begin{array}{ccc}1& \dots & n\\ p\left({\text{box}}_1\right)& \dots & p\left({\text{box}}_n\right)\end{array}\right)& \text{(5.4)}\end{array}$$

where $p\left({\text{box}}_i\right)$ is the entry in ${\text{box}}_i$ of the standard tableau.

5.5. Placed skew shapes

Let $\lambda /\mu$ be a skew shape with $n$ boxes. Imagine placing $\lambda /\mu$ on a piece of infinite graph paper where the diagonals of the graph paper are indexed consecutively (with elements of $\mathbb{Z}\text{)}$ from southwest to northeast.

$$⋮ -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 …$$

The content of a box $b$ is

$$c\left(b\right)=\text{diagonal number of box}b\text{.}$$

Identify the sequence

$$\begin{array}{cc}\gamma =(c\left({\text{box}}_1\right),c\left({\text{box}}_2\right),\dots ,c\left({\text{box}}_n\right))\text{with}\gamma =\sum _{i=1}^{n}c\left({\text{box}}_i\right){\epsilon }_i\in {ℝ}^n\text{.}& \text{(5.6)}\end{array}$$

The pair $(\gamma ,\lambda /\mu )$ is a placed skew shape. It follows from the definitions in Section 5.1 that

$$\begin{array}{ccc}Z\left(\gamma \right)& =& \{{\epsilon }_j-{\epsilon }_i\mid j>i\text{and}{\text{box}}_j\text{and}{\text{box}}_i\text{are in the same diagonal}\}\text{and}\\ P\left(\gamma \right)& =& \{{\epsilon }_j-{\epsilon }_i\mid j>i\text{and}{\text{box}}_j\text{and}{\text{box}}_i\text{are in adjacent diagonals}\}\text{.}\end{array}$$

Define

$$\begin{array}{cc}J=\{{\epsilon }_j-{\epsilon }_i\mid \begin{array}{c}j>i\\ {\text{box}}_j\text{and}{\text{box}}_i\text{are in adjacent diagonals}\\ {\text{box}}_j\text{is northwest of}{\text{box}}_i\end{array}\},& \text{(5.7)}\end{array}$$

where northwest means strictly north and weakly west.

Examples 5.8. The following diagrams illustrate standard tableaux and the numbering of boxes in a skew shape $\lambda /\mu \text{.}$

$$\begin{array}{cc} 10 12 13 14 6 8 11 5 7 9 4 2 3 1 & 3 4 9 12 1 5 10 7 13 14 2 6 8 11 \\ \lambda /\mu \text{with boxes numbered}& \text{A standard tableau}p\text{of shape}\lambda /\mu \end{array}$$

The word of the standard tableau $p$ is the permutation $w_p=(11,6,8,2,7,1,13,5,14,3,10,4,9,12)$ (in one-line notation).

The following picture shows the contents of the boxes in the placed skew shape $(\gamma ,\lambda /\mu )$ with $\gamma =(-7,-6,-5,-2,0,1,1,2,2,3,3,4,5,6)\text{.}$

$$\begin{array}{c} 3 4 5 6 1 2 3 0 1 2 -2 -6 -5 -7 \\ \text{Contents of the boxes of}(\gamma ,\lambda /\mu )\end{array}$$

In this case $J=\{{\epsilon }_2-{\epsilon }_1,{\epsilon }_6-{\epsilon }_5,{\epsilon }_8-{\epsilon }_7,{\epsilon }_{10}-{\epsilon }_8,{\epsilon }_{10}-{\epsilon }_9,{\epsilon }_{11}-{\epsilon }_9,{\epsilon }_{12}-{\epsilon }_{11}\}\text{.}$

Theorem 5.9. Let $(\gamma ,\lambda /\mu )$ be a placed skew shape and let $J$ be as defined in (5.7). Let ${ℱ}^{\lambda /\mu }$ be the set of standard tableaux of shape $\lambda /\mu$ and let ${ℱ}^{(\gamma ,J)}$ be the set defined in Section 5.1. Then the map

$$\begin{array}{ccc}{ℱ}^{\lambda /\mu }& \stackrel{1-1}{\leftrightarrow }& {ℱ}^{(\gamma ,J)},\\ p& \leftrightarrow & w_p,\end{array}$$

where $w_p$ is as defined in (5.4), is a bijection.

		Proof.
	If $w=\left(w\left(1\right)\dots w\left(n\right)\right)$ is a permutation in $S_n$ then $$R\left(w\right)=\{{\epsilon }_j-{\epsilon }_i\mid j>i\text{such that}w\left(j\right)<w\left(i\right)\}\text{.}$$ The theorem is a consequence of the following chain of equivalences: The filling $p$ is a standard tableau if and only if, for all $1\le i<j\le n,$ $p\left({\text{box}}_i\right)<p\left({\text{box}}_j\right)$ if ${\text{box}}_i$ and ${\text{box}}_j$ are on the same diagonal, $p\left({\text{box}}_i\right)<p\left({\text{box}}_j\right)$ if ${\text{box}}_j$ is immediately to the right of ${\text{box}}_i,$ and $p\left({\text{box}}_i\right)>p\left({\text{box}}_j\right)$ if ${\text{box}}_j$ is immediately above ${\text{box}}_i\text{.}$ These conditions hold if and only if ${\epsilon }_j-{\epsilon }_i\notin R\left(w_p\right)$ if ${\epsilon }_j-{\epsilon }_i\in Z\left(\gamma \right),$ ${\epsilon }_j-{\epsilon }_i\notin R\left(e_p\right)$ if ${\epsilon }_j-{\epsilon }_i\in P\left(\gamma \right)\backslash J,$ ${\epsilon }_j-{\epsilon }_i\in R\left(w_p\right)$ if ${\epsilon }_j-{\epsilon }_i\in J,$ which hold if and only if $\alpha \notin R\left(w_p\right)$ if $\alpha \in Z\left(\gamma \right),$ $\alpha \notin R\left(w_p\right)$ if $\alpha \in P\left(\gamma \right)\backslash J,$ and $\alpha \in R\left(w_p\right)$ if $\alpha \in J\text{.}$ Finally, these are equivalent to the conditions $R\left(w_p\right)\cap Z\left(\gamma \right)=\varnothing$ and $R\left(w_p\right)\cap P\left(\gamma \right)=J\text{.}$ $\square$

5.10. Places configurations

We have described how one can identify placed skew shapes $(\gamma ,\lambda /\mu )$ with certain pairs $(\gamma ,J)\text{.}$ One can extend this conversion to associate placed configurations of boxes to more general pairs $(\gamma ,J\text{.})$ The resulting configurations are not always skew shapes.

Let $(\gamma ,J)$ be a pair such that $\gamma =({\gamma }_1,\dots ,{\gamma }_n)$ is a dominant integral weight and $J\subseteq P\left(\gamma \right)\text{.}$ (The sequence $\gamma$ is a dominant integral weight if ${\gamma }_1\le \dots \le {\gamma }_n$ and ${\gamma }_i\in \mathbb{Z}$ for all $i\text{.)}$ If $J$ satisfies the condition

$$\text{if}\beta \in J,\alpha \in Z\left(\gamma \right),\text{and}\beta -\alpha \in R^{+}\text{then}\beta -\alpha \in J$$

then $(\gamma ,J)$ will determine a placed configuration of boxes (see Theorem 4.6). As in the placed skew shape case, think of the boxes as being placed on graph paper where the boxes on a given diagonal all have the same content. (The boxes on each diagonal are allowed to slide along the diagonal as long as they do not pass through the corner of a box on an adjacent diagonal.) The sequence $\gamma$ describes how many boxes are on each diagonal and the set $J$ determines how the boxes on adjacent diagonals are placed relative to each other. We want

$$\gamma =\sum _{i=1}^{n}c\left({\text{box}}_i\right){\epsilon }_i$$

and

1. if ${\epsilon }_j-{\epsilon }_i\in J$ then ${\text{box}}_j$ is northwest of ${\text{box}}_i,$ and
2. if ${\epsilon }_j-{\epsilon }_i\in P\left(\gamma \right)\backslash J$ then ${\text{box}}_j$ is southeast of ${\text{box}}_i,$

where the boxes are numbered along diagonals in the same way as for skew shapes, southeast means weakly south and strictly east, and northwest means strictly north and weakly west.

If we view the pair $(\gamma ,J)$ as a placed configuration of boxes then the standard tableaux are fillings $p$ of the $n$ boxes in the configuration with $1,2,\dots ,n$ such that, for all $i<j,$

1. $p\left({\text{box}}_i\right)<p\left({\text{box}}_j\right)$ if ${\text{box}}_i$ and ${\text{box}}_j$ are on the same diagonal,
2. $p\left({\text{box}}_i\right)<p\left({\text{box}}_j\right)$ if ${\text{box}}_i$ and ${\text{box}}_j$ are on adjacent diagonals and ${\text{box}}_j$ is southeast of ${\text{box}}_i,$ and
3. $p\left({\text{box}}_i\right)<p\left({\text{box}}_j\right)$ if ${\text{box}}_i$ and ${\text{box}}_j$ are on adjacent diagonals and ${\text{box}}_j$ is northwest of ${\text{box}}_i\text{.}$

As in (5.6) the permutation in ${ℱ}^{(\gamma ,J)}$ which corresponds to the standard tableau $p$ is $w_p=(p\left({\text{box}}_1\right),\dots ,p\left({\text{box}}_n\right))\text{.}$ The following example illustrates the conversion.

Example. Suppose $\gamma =(-1,-1,-1,0,0,0,1,1,1,2,2,2)$ and

$$\begin{array}{ccc}J& =& \{{\epsilon }_4-{\epsilon }_1,{\epsilon }_4-{\epsilon }_2,{\epsilon }_4-{\epsilon }_3,{\epsilon }_5-{\epsilon }_2,{\epsilon }_5-{\epsilon }_3,{\epsilon }_7-{\epsilon }_5,{\epsilon }_7-{\epsilon }_6,{\epsilon }_8-{\epsilon }_6,{\epsilon }_{10}-{\epsilon }_9,\\ & & {\epsilon }_{10}-{\epsilon }_8,{\epsilon }_{10}-{\epsilon }_7,{\epsilon }_{11}-{\epsilon }_9,{\epsilon }_{11}-{\epsilon }_8,{\epsilon }_{11}-{\epsilon }_7,{\epsilon }_{12}-{\epsilon }_9\}\text{.}\end{array}$$

The placed configuration of boxes corresponding to $(\gamma ,J)$ is as given below.

$$\begin{array}{ccc} 2 2 0 1 -1 0 -1 1 2 -1 0 1 & 10 11 4 7 1 5 2 8 12 3 6 9 & 3 4 1 5 2 6 9 7 8 10 11 12 \\ \text{contents of boxes}& \text{numbering of boxes}& \text{a standard tableau}\end{array}$$

5.11. Books of placed configurations

The general case, when $\gamma =({\gamma }_1,\dots ,{\gamma }_n)$ is an arbitrary element of ${ℝ}^n$ and $J\subseteq P\left(\gamma \right),$ is handled as follows. First group the entries of $\gamma$ according to their $\mathbb{Z}\text{-coset}$ in $ℝ\text{.}$ Each group of entries in $\gamma$ can be arranged to form a sequence

$$\begin{array}{c}\beta +C_{\beta }=\beta +(z_1,\dots ,z_k)=(\beta +z_1,\dots ,\beta +z_k),\\ \text{where}0\le \beta <1,z_i\in \mathbb{Z},\text{and}{z}_1\le \dots \le z_k\text{.}\end{array}$$

Fix some ordering of these groups and let

$$\overrightarrow{\gamma }=({\beta }_1+C_{{\beta }_1},\dots ,{\beta }_r+C_{{\beta }_r})$$

be the rearrangement of the sequence $\gamma$ with the groups listed in order. Since $\overrightarrow{\gamma }$ and $\gamma$ are in the same orbit it is sufficient to analyze $\overrightarrow{\gamma }$ $\text{(}\gamma$ corresponds to the central character of the corresponding affine Hecke algebra representations and thus any convenient element of the orbit is appropriate, see Section 2.3).

The decomposition of $\overrightarrow{\gamma }$ into groups induces decompositions

$$Z\left(\overrightarrow{\gamma }\right)=\bigcup _{{\beta }_i}{Z}_{{\beta }_i},P\left(\overrightarrow{\gamma }\right)=\bigcup _{{\beta }_i}{P}_{{\beta }_i},\text{and,}\text{if}J\subseteq P\left(\overrightarrow{\gamma }\right),\text{then}J=\bigcup _{{\beta }_i}{J}_{{\beta }_i},$$

where $J_{{\beta }_i}=J\cap P_{{\beta }_i}\text{.}$ Each pair $(C_{\beta },J_{\beta })$ is a placed shape of the type considered in the previous subsection and we may identify $(\overrightarrow{\gamma },J)$ with the book of placed shapes $((C_{{\beta }_1},J_{{\beta }_1}),\dots ,(C_{{\beta }_r},J_{{\beta }_r}))\text{.}$ We think of this as a book with pages numbered by the values ${\beta }_1,\dots ,{\beta }_r$ and with the placed configuration determined by $(C_{{\beta }_i},J_{{\beta }_i})$ on page ${\beta }_i\text{.}$ In this form the standard tableaux of shape $\overrightarrow{\gamma },J$ are fillings of the $n$ boxes in the book with the numbers $1,\dots ,n$ such that the filling on each page satisfies the conditions for a standard tableau in Section 5.10.

Example. If $\gamma =(1/2,1/2,1,1,1,3/2,-2,-2,-1/2,-1,-1,-1,-1/2,1/2,0,0,0)$ then one possibility for $\overrightarrow{\gamma }$ is

$$\overrightarrow{\gamma }=(-2,-2,-1,-1,-1,0,0,0,1,1,1,-1/2,-1/2,1/2,1/2,1/2,3/2)\text{.}$$

In this case ${\beta }_1=0,$ ${\beta }_2=1/2,$

$$\begin{array}{ccc}{\beta }_1+C_{{\beta }_1}& =& (-2,-2,-1,-1,-1,0,0,0,1,1,1),\text{and}\\ {\beta }_2+C_{{\beta }_2}& =& (-1/2,-1/2,1/2,1/2,1/2,3/2)\text{.}\end{array}$$

If $J=J_{{\beta }_1}\cup J_{{\beta }_2}$ where $J_{{\beta }_2}=\{{\epsilon }_{14}-{\epsilon }_{13},{\epsilon }_{17}-{\epsilon }_{16}\}$ and

$$J_{{\beta }_1}=\{{\epsilon }_3-{\epsilon }_2,{\epsilon }_4-{\epsilon }_2,{\epsilon }_5-{\epsilon }_2,{\epsilon }_6-{\epsilon }_3,{\epsilon }_6-{\epsilon }_4,{\epsilon }_6-{\epsilon }_5,{\epsilon }_9-{\epsilon }_7,{\epsilon }_9-{\epsilon }_8,{\epsilon }_{10}-{\epsilon }_7,{\epsilon }_{10}-{\epsilon }_8\}$$

then the book of shapes is

$$0 1 -2 -1 -1 0 -1 1 -1 0 1 -1 0 0 -2 0 1 Page0 Page12$$

where the numbers in the boxes are the contents of the boxes. The filling

$$1 8 2 4 3 6 5 11 7 10 14 9 13 16 12 15 17 Page0 Page12$$

is a standard tableau of shape $(\overrightarrow{\gamma },J)\text{.}$ This filling corresponds to the permutation

$$w=(2,12,4,5,9,1,13,14,8,11,17,3,7,6,10,16,14)\text{in}{ℱ}^{(\overrightarrow{\gamma },J)}\subseteq S_{16}\text{.}$$

Notes and References

This is an excerpt of the paper entitled Affine Hecke algebras and generalized standard Young tableaux written by Arun Ram in 2002, published in the Academic Press Journal of Algebra 260 (2003) 367-415. The paper was dedicated to Robert Steinberg.

Research supported in part by the National Science Foundation (DMS-0097977) and the National Security Agency (MDA904-01-1-0032).

page history