THE REPRESENTATIONS OF THE SYMMETRIC GROUP

LAUREN K. WILLIAMS

Abstract. In this paper we classify the irreducible representations of the symmetric group S_{n} and give a proof of the hook formula for the dimension of each irreducible.

1. The Irreducible Representations of S_{n}

We construct the irreducible representations of the symmetric group. The number of irreducible representations of S_{n} is the number of conjugacy classes of S_{n}, which is the number of partitions of n. Recall that a partition λ of n is λ = (λ_{1}, …, λ_{k}) where n = λ_{1} + ⋯ + λ_{k} and λ_{1} ≥ ⋯ ≥ λ_{k} ≥ 1.

To a partition λ = (λ_{1}, …, λ_{k}) we associate a Young diagram with λ_{i} boxes in the ith row, the rows of boxes left-justified. We define a tableau on a given Young diagram to be a numbering of the boxes by the integers 1, 2, …, n, and we will call it standard if the rows and columns are increasing sequences. Below are examples of a Young diagram, a standard tableau, and a non-standard tableau, for n = 8, and λ = (3, 3, 2).

1 3 4 2 5 8 6 7  3 1 8 2 5 4 6 7
Young diagram standard tableau non-standard tableau

Figure 1

Given a tableau, we define two subgroups of the symmetric group as follows.

P = P_{λ} = {g ∈ S_{n} | g preserves each row};
Q = Q_{λ} = {g ∈ S_{n} | g preserves each column}.

Then we introduce two elements in the group algebra ℂ[S_{n}] corresponding to the two subgroups:

a_{λ} = ∑_{g∈P} e_{g} and b_{λ} = ∑_{g∈Q} sign(g)e_{g}.

We let c_{λ} = a_{λ}b_{λ}—this is called the Young symmetrizer.

After making some observations about the objects we have defined, we will be able to obtain each irreducible representation V_{λ} of S_{n} from the corresponding Young symmetrizer c_{λ}.

Notice that P ∩ Q = {1}, so an element of S_{n} can be written in at most one way as a product pq for p ∈ P and q ∈ Q. So c = ∑ ±e_{g} where the sum is over all g that can be written as pq, and the coefficient of e_{g} is sign(g).

Date: December 16, 1998.

Lemma 1.1. For any p ∈ P and q ∈ Q, we have pc(sign(q)q) = c.

Proof. It’s clear that for p ∈ P, we have pa = ap = a. Similarly, for q ∈ Q, we have (sign(q)q)b = b(sign(q)q) = b. Hence pc(sign(q)q) = pab(sign(q)q) = ab = c.

Lemma 1.2. Up to scalar multiples, c is the only element in ℂ[S_{n}] with the above property.

Proof. Suppose that ∑ n_{g}e_{g} ∈ ℂ[S_{n}] satisfies the property that for any p ∈ P and q ∈ Q, p(∑ n_{g}e_{g}) sign(q)q = ∑ n_{g}e_{g}. Then when we see what happens to the term n_{g}e_{g} on the left-hand side, we get pn_{g}e_{g} sign(q)q = sign(q)n_{g}e_{pgq}, and comparing this to the corresponding term n_{pgq}e_{pgq} on the right-hand side, we see that for all g, p, q,

n_{pgq} = sign(q)n_{g}. (1)

In particular, n_{pq} = sign(q)n_{1}. So it is sufficient to show that n_{g} = 0 if g ∉ P Q.

Claim 1.3. For g ∉ P Q, there is a transposition t such that p = t ∈ P and q = g^{−1}tg ∈ Q.

If this claim holds, then we’ll get g = pgq and by (1), n_{g} = −n_{g}. This implies that n_{g} = 0. So it remains to show the claim.

Note that if T′ = gT is the tableau obtained by letting g act on each entry of T, then the column stabilizer of T′ is Q′ = gQg^{−1}. And so the claim means that there are two distinct integers in the same row of T and the same column of T′; t is their transposition.

To verify the claim, suppose that there are not two such integers. Then all of the elements in the first row of T appear in different columns in T′—we can thus choose q′_{1} ∈ Q′ = gQg^{−1} such that the first row of T and the first row of q′_{1}T′ have the same elements—further, we can choose p_{1} ∈ P such that p_{1}T and q′_{1}T′ have precisely the same first row. Repeating this process on the rest of the tableau, we get p ∈ P and q′ ∈ Q′ such that pT = q′T′. Then pT = q′T so p = q′g and g = pq where q = g^{−1}(q′)^{−1}g ∈ Q. Hence g ∈ P Q and the claim is proved.

Corollary 1.4. For any x ∈ ℂ[S_{n}], c_{λ}xc_{λ} is a scalar multiple of c_{λ}. In particular, c_{λ}c_{λ} = n_{λ}c_{λ} for some n_{λ} ∈ ℂ.

We will order partitions lexicographically, saying that λ > μ if the first nonvanishing λ_{i} − μ_{i} is positive.

Lemma 1.5. If λ > μ then for all x ∈ A we have a_{λ}xb_{μ} = 0. In particular, if λ > μ, then c_{λ}c_{μ} > 0.

Proof. It is sufficient to prove this for x = g ∈ S_{n}. Note that if T′ is the tableau used to construct b_{μ}, then gB_{μ}g^{−1} is the “b-element” constructed from gT′. Also note that our results are dependent only on the partition chosen, not the tableau. So since a_{λ}(gb_{μ}g^{−1}) = 0 implies that a_{λ}gb_{μ} = 0, it suffices to show that a_{λ}b_{μ} = 0. One can check that if λ > μ then there are two integers in the same row of T and the same column of T′. If t is the transposition of these integers, then t ∈ P_{λ} and t ∈ Q_{μ}. Hence a_{λ}t = a_{λ} and tb_{μ} = −b_{μ} so a_{λ}b_{μ} = a_{λ}ttb_{μ} = −a_{λ}b_{μ} which implies that a_{λ}b_{μ} = 0.

We can now obtain all irreducible representations of S_{n}.

Theorem 1.6. The image of c_{λ} by right multiplication on ℂ[S_{n}] is an irreducible representation V_{λ} of S_{n}, and every irreducible representation of S_{n} can be obtained in this way for a unique partition λ.

For example, when λ = (n), we get P_{λ} = S_{n}, Q_{λ} = {1}, b_{λ} = 1, and c_{λ} = a_{λ} = ∑_{g∈S_{n}} e_{g}, so V_{λ} = ℂ[S_{n}] ∑_{g∈S_{n}} e_{g} = ℂ ∑_{g∈S_{n}} e_{g} is the trivial representation.

Proof. First we show that each V_{λ} is an irreducible representation of S_{n}. Since V_{λ} = (ℂ[S_{n}])c_{λ}, it is clear that V_{λ} is a ℂ[S_{n}]-invariant subspace, i.e., a representation. Now note that by Corollary 1.4, c_{λ}V_{λ} ⊂ ℂc_{λ}. If W ⊂ V_{λ} is a subrepresentation, then either c_{λ} ∈ c_{λ}W, in which case c_{λ}W = ℂc_{λ}, or c_{λ} ∉ c_{λ}W, in which case c_{λ}W = 0. If the former is true, then since W is a subrepresentation, c_{λ}W ⊂ W, and so in particular, c_{λ} ∈ W. Then we have V_{λ} = (ℂ[S_{n}])c_{λ} ⊂ W and so W = V_{λ}. If the latter is true, then W W ⊂ (ℂ[S_{n}])c_{λ}W = 0 but this implies that W = 0. Hence V_{λ} is irreducible.

Now we will show that if λ ≠ μ, then V_{λ} and V_{μ} are not isomorphic. Without loss of generality we assume that λ > μ. Then by Corollary 1.4, c_{λ}V_{λ} = ℂc_{λ} ≠ 0, but by Lemma 1.5, c_{λ}V_{μ} = c_{λ}Ac_{μ} = 0, so they cannot be isomorphic ℂ[S_{n}]-modules.

Finally, note that these are all of the irreducible representations because we have as many irreducible representations as conjugacy classes.

2. The Dimension of V^{λ}

We sketch a proof that the dimension of V^{λ} is equal to the number of standard tableaux on λ.

First note that for λ = (λ_{1}, …, λ_{k}), a partition of n, we have a subgroup S_{λ} = S_{λ_{1}} × ⋯ × S_{λ_{k}} of S_{n}. We let U_{λ} be the representation of S_{n} obtained by inducing from the trivial representation of S_{λ}—this is equal to ℂ[S_{n}]a_{λ}. Hence V_{λ} appears in U_{λ}, as we have a surjection given by x ↦ xb_{λ}. Observe that for λ = (1, …, 1), U_{λ} is the regular representation, which contains every irreducible with multiplicity equal to its dimension. This motivates our study of U_{λ}.

The character ψ_{λ} of U_{λ} is straightforward to compute. If C_{i} is the conjugacy class in which each element consists of i_{1} 1-cycles, …, i_{n} n-cycles, then ψ_{λ}(C_{i}) is the coefficient of the monomial X^{λ} = x_{1}^{λ_{1}} ⋯ x_{k}^{λ_{k}} in the polynomial

P^{(i_{1},...,i_{n})} = (x_{1} + ⋯ + x_{k})^{i_{1}} ⋯ (x_{1}^{n} + ⋯ + x_{k}^{n})^{i_{n}}.

Now for independent variables x_{1}, …, x_{k}, we define the power sums P_{j}(x), and the discriminant Δ(x) by

P_{j}(x) = x_{1}^{j} + ⋯ + x_{k}^{j},
Δ(x) = ∏_{i<j}(x_{i} − x_{j}).

We also define the coefficient

ω_{λ}(i) = [ΔP^{(i)}]_{l}, l = (λ_{1} + k − 1, λ_{2} + k − 2, …, λ_{k})

which we will find is equal to χ_{λ}(C_{i}), the character of V_{λ}.

To show this, we use an identity which holds for any symmetric polynomial P,

[P]_{λ} = ∑_{μ} K_{μλ}[ΔP]_{(μ_{1}+k−1,...,μ_{k})},

where the coefficients K_{μλ} are the Kostka numbers. Given partitions λ and μ of n, the Kostka number K_{μλ} is defined combinatorially as the number of ways to fill the boxes of the Young diagram for μ with λ_{1} 1’s, up to λ_{k} k’s, such that each row is a nondecreasing sequence and each column is an increasing sequence. In other words, K_{μλ} is the number of semistandard tableaux on μ of type λ. In particular, K_{μ(1,...,1)} is the number of standard tableaux on λ.

One can show that

ψ_{λ}(C_{i}) = ∑_{μ} K_{μλ}ω_{λ}(i) = ω_{μ}(i) + ∑_{μ>λ} K_{μλ}ω_{μ}(i) (2)

and that the coefficients ω_{λ}, regarded as functions on the conjugacy classes of S_{n}, satisfy the same orthogonality relations as the irreducible characters of S_{n}. Using an inductive argument, it follows from (2) that ω_{λ} = χ_{λ}.

Corollary 2.1. The integer K_{μλ} is the multiplicity of the irreducible representation V_{μ} in the induced representation U_{λ}:

U_{λ} ≅ V_{λ} ⊕ ⨁_{μ>λ} K_{μλ}V_{μ}.

When λ = (1, …, 1), it is clear that U_{λ} is the regular representation, and so K_{μ(1,...,1)}, which is the number of standard tableaux on λ, is the dimension of V_{μ}.

3. The Hook Formula

We use the previous result that the number of standard Young tableaux of a given shape λ is the degree of the corresponding representation V_{λ}. We denote the dimension of V_{λ} by f^{λ}; the hook formula is an explicit formula for this dimension, and involves objects called hooks. We give a probabilistic proof of the hook formula, due to Greene, Nijenhuis, and Wilf [2].

Definition 3.1. If v = (i, j) is a node in the diagram of λ, then it has hook

H_{v} = H_{i,j} = {(i, j′) | j′ ≥ j} ∪ {(i′, j) | i′ ≥ i}

with corresponding hooklength h_{v} = h_{i,j} = |H_{i,j}|.

For example, in the diagram, the dotted cells are the hook H_{1,2} with hooklength h_{1,2} = 4.

∗ ∗ ; ∗ ; ∗ Figure 2

Theorem 3.2 (Hook Formula). If λ is a partition of n, then

f^{λ} = \frac{n!}{∏_{(i,j)∈λ} h_{i,j}} .

To prove this theorem, we will find an algorithm that always produces a standard λ-tableau. Moreover, it produces any given standard λ-tableau P with equal probability, ^{\frac{∏ h_{i,j}}{n!}} . And hence the number of standard λ-tableau is equal to the reciprocal of that probability.

The algorithm is as follows. Note that by an inner corner we mean a node of the tableau which has hooklength 1.

• Pick a random node v ∈ λ (with probability \frac{1}{n}).

• While v is not an inner corner, repeat the following:

– Pick a random node v̄ ∈ H_{v} \ v (with probability \frac{1}{h_{v}−1}).

– Replace v with v̄.

• Give the label n to the inner corner cell v that you’ve reached.

• Go back to the first step, replacing λ with λ \ {v}, and n with n − 1, and repeat the loop until all cells are labeled.

We’ll refer to the sequence of nodes generated by one pass through the algorithm (to reach an inner corner cell) as a trial. Notice that the x-coordinates of the nodes in a trial form a monotonically increasing sequence, as do the y-coordinates.

It’s clear that our algorithm produces a standard labeling of λ. To show that all standard labelings have the same probability, we induct on n.

Consider a particular λ-tableau T. Let w be the cell containing n and let T̄ be T with w deleted. Then prob(T) = prob(w) prob(T̄) where prob(w) is the probability that a trial ends at w. For our induction step, it will clearly suffice to show that

prob(w) = \begin{matrix}\frac{1}{n!} & ∏ & v∈λ & h_{v} \\ \frac{1}{(n−1)!} & ∏ & v̄∈λ̄ & hv̄ \end{matrix} .

And everything in the above expression cancels except for terms corresponding to the following subset of λ:

S = {v ≠ w | w ∈ H_{v}}.

Each hooklength in S is decreased by 1 so we can rewrite the previous expression as

prob(w) = \frac{1}{n} ∏_{v∈S} \frac{h_{v}}{h_{v} − 1} = \frac{1}{n} ∏_{v∈S} [1 + \frac{1}{h_{v} − 1}] .

Now let w have coordinates (α, β) and notice that v ∈ S means that v is in the same row or column as w. So if we let a_{i} = h_{i,β} − 1, and b_{j} = h_{α,j} − 1, then we can rewrite the preceding expression as

prob(w) = \frac{1}{n} ∏_{i=1}^{α−1} (1 + \frac{1}{a_{i}} ) ∏_{j=1}^{β−1} (1 + \frac{1}{b_{j}} ) = \frac{1}{n} ∑_{I,J} ∏_{i∈I} \frac{1}{a_{i}} ∏_{j∈J} \frac{1}{b_{j}}

where I ranges over the subsets of [α − 1] and J ranges over the subsets of [β − 1]. (Note that we use [n] to denote the set {1, …, n}.)

We can now interpret each term above in the following way.

Definition 3.3. Given a trial ending at (α, β), we let the horizontal projection of the trial be

I = {i ≠ α | v = (i, j) for some v on the trial}.

The vertical projection is defined analogously. Let prob_{I,J}(α, β) denote the sum of the probabilities of all trials ending at (α, β) with horizontal projection I and vertical projection J. So prob(α, β) = ∑_{I,J} prob_{I,J}(α, β) where I ranges over the subsets of [α − 1] and J ranges over the subsets of [β − 1]. Now, to prove the theorem, it is sufficient to prove the following lemma:

Lemma 3.4. Given (α, β), I a subset of [α − 1], and J a subset of [β − 1],

prob_{I,J}(α, β) = \frac{1}{n} ∏_{i∈I} \frac{1}{a_{i}} ∏_{j∈J} \frac{1}{b_{j}} .

Proof. We use induction on |I ∪ J|. First, assume that I or J is empty. WLOG J = ∅. Then if we order the terms of I in an increasing sequence (i_{1}, i_{2}, …), the only possible trial is the sequence {(i_{1}, β), (i_{2}, β), … }. The probability of randomly choosing (i_{1}, β) according to the algorithm is \frac{1}{n}. Similarly, the probability of choosing (i_{2}, β) is \frac{1}{a_{i_{1}}} , and so on. So

prob_{I,J}(α, β) = \frac{1}{na_{i_{1}}a_{i_{2}} ⋯}

as desired.

Now assume that neither I nor J is empty. Then we must have v_{1} = (i_{1}, j_{1}) and there are exactly two choices for v_{2}—(i_{2}, j_{1}) or (i_{1}, j_{2})—each of which is chosen with probability \frac{1}{h_{i_{1},j_{1}}} . Let Ī = I \ \{i_{1}\} and J̄ = J \ \{j_{1}\}. Then

prob_{I,J}(α, β) = \frac{1}{h_{i_{1},j_{1}} − 1}[prob_{Ī,J}(α, β) + prob_{I,J̄}(α, β)]

= \frac{1}{h_{i_{1},j_{1}} − 1} [\frac{1}{nâ_{i_{1}}a_{i_{2}} ⋯ b_{j_{1}}b_{j_{2}} ⋯} + \frac{1}{na_{i_{1}}a_{i_{2}} ⋯ b̂_{j_{1}}b_{j_{2}} ⋯}]

= \frac{a_{i_{1}} + b_{j_{1}}}{h_{i_{1},j_{1}} − 1} [\frac{1}{na_{i_{1}}a_{i_{2}} ⋯ b_{j_{1}}b_{j_{2}} ⋯}]

where ˆ · means that the factor is deleted. But h_{i_{1},j_{1}−1} = (h_{i_{1},β} −1)+(h_{α,j_{1}} −1) = a_{i_{1}} + b_{j_{1}}, so we are done.

References

ics, no. 129, Springer-Verlag, New York, US, 1991.

York, US, 1991.

   E-mail address: lkwill@fas.harvard.edu

1. W. Fulton and J. Harris, Representation theory: A first course, Graduate Texts in Mathemat-2. Bruce Sagan, The symmetric group, Cole Mathematics Series, Wadsworth & Brooks, New

Department of Mathematics, Harvard University, Cambridge, MA 02138

Current address: 1624 Cataluna Place, Palos Verdes Estates, CA 90274