Skip to content

Partitions of n, Young tableaux and tabloids.

January 15, 2013

This is a follow-up of my this post. There is a nice way to represent and visualize partitions of n. The objects we will define will admit a natural action from S_n and will permit us to think about the symmetric group in a very combinatorial way. Suppose \lambda = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k is a partition of n. Then the Young diagram of shape \lambda is an arrangement of n boxes, there is k rows and the i‘th row, starting from the top, contains \lambda_i boxes. For example, here is the associated Young diagram for n = 8 and \lambda = (3,2,2,1) :

Ydiagram2

If \lambda \vdash n, there is also the notion of a Young tableau of shape \lambda. This is simply a Young diagram of shape \lambda filled with the numbers in \{ 1, \ldots, n \} (with no repeats). A tableau of shape \lambda, or \lambda-tableau, is denoted by t^{\lambda}. For example, here are all the \lambda-tableaux for \lambda = 2,1 :Capture d’écran 2013-01-10 à 17.53.51

The entries in a tableau are designated as in a matrix, so the first tableau above has entries t_{1,1} = 1, t_{1,2} = 2, t_{2,1} = 3.

There is a natural action of S_n on a tableau t = (t_{ij}) of shape \lambda \vdash n defined as \sigma \cdot t = (\sigma(t_{i,j})) for \sigma \in S_n. i.e. \sigma just permutes the entries of the tableau. This action is clearly transitive.

The next step is to define an equivalence relation on the set of \lambda-tableaux which will be important for our construction of the irreducible representations of the symmetric group. If t_1, t_2 are two \lambda-tableaux, define them to be row equivalent if corresponding rows contain the same numbers and note this by t_1 \sim t_2. A \lambda-tabloid [t] is then defined as an equivalence class of \lambda-tableaux for this relation. For example, here is a (3,1)-tableau:

tabloid

The notation without the vertical bars is to suggest that the arrangement of numbers in different rows is irrelevant. Here is the set of all the (2,1)-tabloids:tabloid2

The action of S_n on tableaux induces an action of S_n on tabloids. This gives, for every \lambda \vdash n, a representation of S_n on the complex vector space M^{\lambda} := \mathbb{C}\{ [t_1], \ldots, [t_k] \} generated by all \lambda-tableaux [ t_1], \ldots, [ t_k ]. Let’s look at some examples for different partitions of n:

If \lambda = (n), then the associated diagram is just n horizontally aligned boxes so every \lambda-tableaux are row equivalent. In other words, there is only one \lambda-tabloid. We thus find M^{(n)} \simeq \mathbb{C} and S_n acts trivially. This is the trivial representation.

If \lambda = (1^n), the associated diagram is n vertically aligned boxes so now the situation is that no two \lambda-tableaux are row equivalent. There is thus one different tabloid for every tableau. Also, every tableau can be identified with a permutation using one line notation and since this identification preserves the action of S_n, we find that M^{(1^n)} \simeq \mathbb{C}S_n is the regular representation. In particular, the M^{\lambda}‘s are far from being irreducibles.

If \lambda = (n-1,1), then a \lambda- tabloid is uniquely determined by the number in its second row. So we can identity the tabloids with the set of numbers from 1 to n. Clearly, \sigma \in S_n will send the tabloid identified with i to the tabloid identified with j (1 \leq i,j \leq n) if and only if \sigma(i) = j. This tells us that this identification is an equivalence of representations and so we have the defining representation M^{(n-1,1)} \simeq \mathbb{C}\{e_1\ldots, e_n\}.

In subsequent posts, we will see a way to construct, for each \lambda \vdash n, an irreducible submodule of M^{\lambda} in a way that gives us all irreducible representations of S_n.

Advertisement
One Comment

Trackbacks & Pingbacks

  1. A combinatorial lemma on tableaux. « arbourj's blog

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: