# Representation theory of the symmetric group: basics

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

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.

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

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:

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.

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:

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$:

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$.