In this post we lay out some introductory material on the representation theory of $S_n$ over $\mathbb{C}$.

1. Conventions and first impressions

We identify $S_n$ with the permutations of the set $\{1,\ldots,n\}=[n]$, and a permutation with a bijection $\pi:[n]\to[n]$, so that composition of permutations is defined as composition of functions.

We will also write permutations in cycle notation when it's more convenient, so that \begin{align*} \pi=(a_{11},\ldots,a_{1k_1})(a_{21},\ldots,a_{2k_2})\ldots(a_{m1},\ldots,a_{mk_m}) \end{align*} means the permutation consisting of the $m$ disjoint cycles $a_{i1}\to\ldots\to a_{ik_i}\to a_{i1}$. Sometimes when working over $[n]$ with $n<10$, we will omit the commas in the cycles.

1.1. Some special representations

What are the representations of $S_n$ like? First, it's easy to see that there are only two 1-dimensional ones:

Proposition 1.

$S_n$ has precisely two 1-dimensional representations: the trivial representation $\mathop{\rm triv}\nolimits$ sending everything to $1$, and the alternating/sign representation $\mathop{\rm sgn}\nolimits$ sending even permutations to 1 and odd permutations to $-1$.

Proof 1.

Suppose $\rho:S_n\to\mathbb{C}$ is a representation of $S_n$. Then a transposition must go to $\pm1$, because it is of order 2. Since all transpositions are conjugate to one another, and since $\mathbb{C}$ is commutative, we have for two any transpositions $\tau,\sigma$ that \begin{align*} \rho(\tau) = \rho(\pi\sigma\pi^{-1})=\rho(\pi)\rho(\sigma)\overline{\rho(\pi)}=\rho(\sigma) \end{align*} so all transpositions go to either $1$ or $-1$. If they go to $1$, all of $S_n$ goes to $1$ because the transpositions generate; and if they go to $-1$, we get the alternating representation.

Next, what we did above when setting up our implementation of the symmetric group already defines a natural representation, the permutation representation of $S_n$, given by the action of $S_n$ on an $n$-dimensional vector space by permuting the elements of some basis $e_1,\ldots,e_n$. It contains an invariant subspace, the span of the vector $(1,\ldots,1)$, which is a copy of the trivial representation. The remaining component is irreducible as well:

Proposition 2.

The standard representation of $S_n$, acting by permuting the coordinates in the subspace $\mathop{\rm triv}\nolimits^\perp = \left\{ x_1e_1+\ldots+x_ne_n \ \big| \ x_1+\ldots+x_n=0\right\}$ of the permutation representation, is irreducible.

Proof 2.

Let $w\in \mathop{\rm triv}\nolimits^\perp$; we will show that the span of the guys $\left\{ \pi w \ \big| \ \pi\in S_n\right\}$ is the whole $\mathop{\rm triv}\nolimits^\perp$. To get something simpler to work with, we will subtract from $w$ something that's almost the same. Indeed, there must be some $i,j$ such that $w_i\neq w_j$, and then $w-(i,j)w=\alpha(e_i-e_j)$ for some $\alpha\neq 0$, consequently $e_i-e_j$ is in the span. But then $e_{i'}-e_{j'}$ is in the span for any $i',j'$ by applying a suitable permutation to that. Since $e_1-e_2,\ldots,e_1-e_n$ is a basis for $\mathop{\rm triv}\nolimits^\perp$, we get what we claimed.

1.2. The conjugacy classes

We know that in general the number of irreducible representations of a finite group equals the number of conjugacy classes. What are the conjugacy classes of $S_n$ like?

As we know, conjugation is just a fancy term for `renaming' the ground set $[n]$, just like matrix conjugation is a change of basis. To be more specific, we have the following simple lemma:

Lemma 3.

If $\pi= (a_1,\ldots,a_k)\ldots(z_1,\ldots,z_m)$ in cycle form, then conjugation by $\sigma$ is obtained by simply applying $\sigma$ to each entry: \begin{align*} \sigma\pi\sigma^{-1} = (\sigma(a_1),\ldots,\sigma(a_k))\ldots(\sigma(z_1),\ldots,\sigma(z_m)) \end{align*}

Proof 3.

Let $\pi= \gamma_1\ldots\gamma_k$ as a cycle decomposition; then \begin{align*} \sigma \pi\sigma^{-1} = (\sigma \gamma_1\sigma^{-1})\ldots (\sigma\gamma_k\sigma^{-1}) \end{align*} Now focus on a single cycle $\gamma$ and look at $\sigma\gamma\sigma^{-1}$. If $i\notin\gamma$, we have \begin{align*} \sigma\pi\sigma^{-1}(\sigma(i)) = \sigma\pi(i)=\sigma(i) \end{align*} and if $i\in\gamma$, \begin{align*} \sigma\pi\sigma^{-1}(\sigma(i)) = \sigma\pi(i) \end{align*} So if $\gamma=(a_1,\ldots,a_k)$ then $\sigma\pi\sigma^{-1}(\sigma(a_i)) = \sigma\pi(a_i)=\sigma(a_{i+1})$ indices modulo $k$, and moreover $\sigma\pi\sigma^{-1}$ is non-trivial precisely on $a_1,\ldots,a_k$. The assertion follows by multiplying all the conjugates of the $\gamma_i$ obtained in this way.

So the question is, given a permutation $\pi$, what are all permutations that can be obtained from $\pi$ by renaming the ground set $[n]$? Given the above renaming lemma, it's clear that these are precisely the permutations that have the same cycle type as $\pi$:

Corollary 1.

The conjugacy class of $\pi\in S_n$ consists of all permutations having the cycle type of $\pi$.

So the number of conjugacy classes of $S_n$ equals the partition number $p(n)$: the number of ways to partition $n$ into parts of sizes $\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_k\geq 1$ (so that the order of parts doesn't matter, only their sizes). There is no known closed-form expression for $p(n)$, though it obeys the following generating function \begin{align*} \sum_{n\in\mathbb{N}}^{} p(n)x^n = \prod_{i=1}^{\infty} \frac{1}{1-x^i} = (1+x+x^2+\ldots)(1+x^2+x^4+\ldots)\ldots \end{align*} for all $|x|<1$.