# A combinatorial lemma on tableaux.

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

Then and . We will say that two numbers are collinear in if they appear in a same row in and co-columnar in if they appear in the same column of (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 , we form two subgroups of :

In other words, if has rows and columns , then and . For example, if we take to be the tableau pictured at the start of this post, then

(Recall that for a set, denotes the group of bijections of ). Note that a tabloid is nothing else than , the orbit of in the set of all tableaux under the action of the subgroup .

First, we investigate how the groups and we just defined behave with respect to the action of on tableaux:

**Lemma 1:** Let be a tableau of shape and let . Then and .

*Proof:* We have by definition of (recall that denotes the tabloid associated to ). This is equivalent to so we find , i.e., . The reverse inclusion is just the same steps reversed and the statement for is similar. QED

We now introduce a total order on the set of partitions of and thus on the set of Young diagrams with boxes. Let and be partitions of . Then if, for some index , we have for and . 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 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 and be tableaux with boxes of shape and respectively. Suppose that . If no two numbers are collinear in and co-columnar in , then and there are such that .

*Proof:* Suppose and . Since , we have and for all . In particular, the number of entries in the first row of is smaller or equal to the number of entries in the first row of , ie. . 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 (i.e. ) is smaller than the number of entries in the first row of (i.e. ). But then two entries of the first row of have to occur in the same column in , contrary to our hypothesis. Hence both diagrams have the same number of entries in their first row, i.e. . Since the entries of the first row of occur in different columns of , there is a such that these entries are the same as the entries of the first row of .

We now apply the same reasoning to the second row: and have the same number of entries in the second row and we can take , not moving the entries of the first row, such that the entries of the second row of are the entries of the second row of . By induction, we see that and that there is a such that the entries of each row of are exactly the entries of the corresponding row in . Hence there also exists a such that

This tells us that where the last equality is lemma 1. We can thus choose such that so we find and

QED

## Trackbacks & Pingbacks