A combinatorial lemma on tableaux.

January 21, 2013

Let T be a Young tableau of shape $\lambda \vdash n$ . We will denote entries of $T$ using the notation of matrices. For example if $T$ is the following tableau :

Then $T(1,3) = 3, T(2,1) = 4$ and $T(2,2) = 5$ . We will say that two numbers $i,j \in \{ 1,\ldots,n \}$ are collinear in $T$ if they appear in a same row in $T$ and co-columnar in $T$ if they appear in the same column of $T$ (these definitions come from a set of lecture notes I found on Bob Howlett’s webpage, which seems to follow the treatment in Nathan Jacobson’s Basic Algebra II). For a tableau $T$ , we form two subgroups of $S_n$ :

$R(T) := \{\sigma \in S_n : j \text{ and } \sigma j \text{ are collinear in }D \text{ for all } j\}$

$C(T) := \{\sigma \in S_n : j \text{ and } \sigma j \text{ are co-columnar for all } j\}.$

In other words, if $T$ has rows $R_1, \ldots, R_l$ and columns $C_1, \ldots, C_k$ , then $R(T) = S_{R_1} \times \cdots \times S_{R_l}$ and $C(T) = S_{C_1} \times \cdots \times S_{C_k}$ . For example, if we take $T$ to be the tableau pictured at the start of this post, then

$R(T) = S_{\{1,2,3\}} \times S_{\{4,5\}} \times S_{\{6\}}$

$C(T) = S_{\{1,4,6\}} \times S_{\{2,5\}} \times S_ {\{3\}}.$

(Recall that for $E$ a set, $S_E$ denotes the group of bijections of $E$ ). Note that a tabloid $[T]$ is nothing else than $R(T)(T)$ , the orbit of $T$ in the set of all $\lambda-$ tableaux under the action of the subgroup $R(T) < S_n$ .

First, we investigate how the groups $R(T)$ and $C(T)$ we just defined behave with respect to the action of $S_n$ on tableaux:

Lemma 1: Let $T$ be a tableau of shape $\lambda \vdash n$ and let $\sigma \in S_n$ . Then $R(\sigma T) = \sigma R(T) \sigma^{-1}$ and $C(\sigma T) = \sigma C(T) \sigma^{-1}$ .

Proof: We have $\tau \in R(\sigma T) \Leftrightarrow \tau[\sigma T] = [\sigma T]$ by definition of $R(T)$ (recall that $[T]$ denotes the tabloid associated to $T$ ). This is equivalent to $\sigma^{-1} \tau [\sigma T] = \sigma^{-1} [\sigma T]$ so we find $\sigma^{-1} \tau \sigma [T] = \sigma^{-1} \sigma [T] = [T]$ , i.e., $\sigma^{-1} \tau \sigma \in R(T)$ . The reverse inclusion is just the same steps reversed and the statement for $C(T)$ is similar. QED

We now introduce a total order on the set of partitions of $n$ and thus on the set of Young diagrams with $n$ boxes. Let $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_l)$ and $\mu = (\mu_1, \mu_2, \ldots, \mu_m)$ be partitions of $n$ . Then $\lambda < \mu$ if, for some index $i$ , we have $\lambda_j = \mu_j$ for $j < i$ and $\lambda_i < \mu_i$ . This is called the lexicographic order, it is the order you would find the partitions in if they were in a dictionnary. For example, this gives $(1^4) < (2,1^2) < (2,2) < (3,1) < (4)$ and this corresponds to the diagrams

The next combinatorial result is crucial to the treatment we follow of the representation theory of the symmetric group:

Lemma 2: Let $T$ and $T'$ be tableaux with $n$ boxes of shape $\lambda$ and $\lambda'$ respectively. Suppose that $T \leq T'$ . If no two numbers are collinear in $T'$ and co-columnar in $T$ , then $\lambda = \lambda'$ and there are $\sigma \in R(T), \tau \in C(T)$ such that $T' = \sigma \tau T$ .

Proof: Suppose $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k)$ and $\lambda' = (\lambda_1', \lambda_2', \ldots, \lambda_l')$ . Since $T \leq T'$ , we have $k \geq l$ and $\lambda_i \leq \lambda_i'$ for all $1 \leq i \leq l$ . In particular, the number of entries in the first row of $T$ is smaller or equal to the number of entries in the first row of $T'$ , ie. $\lambda_1 \leq \lambda_1'$ . Suppose this inequality was strict. Then since the number of columns in a tableau is, by construction, equal to the number of entries in its first row, this would mean that the number of columns of $T$ (i.e. $\lambda_1$ ) is smaller than the number of entries in the first row of $T'$ (i.e. $\lambda_1'$ ). But then two entries of the first row of $T'$ have to occur in the same column in $T$ , contrary to our hypothesis. Hence both diagrams have the same number of entries in their first row, i.e. $\lambda_1 = \lambda_1'$ . Since the entries of the first row of $T$ occur in different columns of $T'$ , there is a $\tau_1 \in C(T')$ such that these entries are the same as the entries of the first row of $\tau_1T'$ .

We now apply the same reasoning to the second row: $T$ and $\tau_1T'$ have the same number of entries in the second row and we can take $\tau_2 \in C(\tau_1T') = C(T')$ , not moving the entries of the first row, such that the entries of the second row of $T$ are the entries of the second row of $\tau_2 \tau_1 T$ . By induction, we see that $\lambda = \lambda'$ and that there is a $\tau' \in C(T')$ such that the entries of each row of $T$ are exactly the entries of the corresponding row in $\tau' T'$ . Hence there also exists a $\sigma \in R(T)$ such that $\sigma T = \tau' T'$

This tells us that $\tau' \in C(T') = C(\tau' T') = C(\sigma T) = \sigma C(T) \sigma^{-1}$ where the last equality is lemma 1. We can thus choose $\tau^{-1} \in C(T)$ such that $\tau' = \sigma \tau^{-1} \sigma^{-1}$ so we find $\sigma \tau^{-1} \sigma^{-1} T' = \tau' T' = \sigma T$ and

$\sigma \tau T = T'.$

QED

From → Algebra, Representation Theory

One Comment

Trackbacks & Pingbacks

Young symmetrizer, Specht modules and examples. « arbourj's blog

A combinatorial lemma on tableaux.

Trackbacks & Pingbacks

Leave a Reply Cancel reply

Search

Categories

Tags

A combinatorial lemma on tableaux.

Share this:

Like this:

Related

Trackbacks & Pingbacks

Leave a Reply Cancel reply

Search

Categories

Tags