Skip to content

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 :Y-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 diagramslex_order

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

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: