Math 202B: Lecture 24

In Lecture 23 we worked out the irreducible representations of the symmetric group $S_3$ and computed their characters. Proceeding by bare hands becomes difficult quickly since the cardinality of $S_n$ grows very rapidly (indeed, superexponentially) with $n$ .

We can at least answer one natural question, which encouragingly was asked by Yunseong Jung in Lecture 23: is the standard representation of $S_n$ irreducible for all $n$ ? If so, we will have three irreducible unitary representations of $S_n$ , namely the trivial and alternating ones, which are one-dimensional, and the standard representation, which is $n-1$ dimensional. This isn’t much – the number of irreducible representations of $S_n$ is the number of partitions of $n,$ which according to the Hardy-Ramanujan formula is asymptotically

$\frac{1}{4\sqrt{3}n}\exp \pi\sqrt{\frac{2}{3}n}$

for large $n$ – but it’s better than nothing.

Start with the permutation representation $(V,\varphi)$ of $S_n$ , so $V$ is a Hilbert space with orthonormal basis $\{e_x \colon x \in X\}$ , $X=\{1,\dots,n\},$ and $\varphi \colon S_n \to U(\mathcal{L}(V))$ is the group homomorphism defined by

$\varphi(g)e_x = e_{g(x)}, \quad g \in S_n,\ x\in X.$

The character of the permutation representation of $S_n$ is

$\chi^V(g) = \mathrm{Tr} \varphi(g) = \sum\limits_{x\in X} \langle e_x, \varphi(g)e_x \rangle = \sum\limits_{x \in X} \langle e_x,e_{g(x)}\rangle,$

so $\chi^V(g)$ is the number of fixed points (i.e. one-cycles) of the permutation $g.$ Therefore,

$\langle \chi^V,\chi^V\rangle = \sum\limits_{g \in S_n} |\mathrm{Fix}(g)|^2,$

where $\mathrm{Fix}(g) \subseteq X$ is the set of fixed points of $g \in S_n$ . To understand this sum, let us begin with the simpler version without the squares. By Burnside’s Lemma, which is a consequence of the orbit-stabilizer theorem, we have

$\frac{1}{|S_n|} \sum\limits_{g \in S_n} |\mathrm{Fix}(g)| = \left|X/S_n\right|,$

where $X/S_n$ is the number of orbits of $S_n$ acting on $X.$ Obviously, the number of orbits of $S_n$ acting on $X=\{1,\dots,n\}$ is one, i.e. $S_n$ acts transitively on $X,$ so

$\frac{1}{|S_n|} \sum\limits_{g \in S_n} |\mathrm{Fix}(g)| = \left|X/S_n\right|,$

which can be interpreted probabilistically as saying that the expected number of fixed points in a uniformly random sample from $S_n$ is one.

We can use a version of the same argument to evaluate $\langle \chi^V,\chi^V\rangle.$ To get the exponent of $2$ into the equation, let $S_n$ act on $X\times X$ by $g\cdot (x,y)=(g(x),g(y)).$ Then, we have

$(g(x),g(y))=(x,y) \iff g(x) =x \text{ and }g(y)=y,$

so that points of $X\times X$ which are fixed by a given $g \in S_n$ are in bijection with pairs of points in $X$ which are fixed by $g$ . Applying Burnside’s Lemma we thus have

$\langle \chi^V,\chi^V\rangle = \sum\limits_{g \in S_n} |\mathrm{Fix}(g)|^2=\left|(X \times X)/S_n\right|.$

It is not too difficult to determine the number of orbits of $S_n$ acting on $X \times X.$ Indeed, consider any point $(x,y) \in X \times X.$ Either $x=y$ or $x \neq y$ . In the first case, the orbit of $(x,y)$ under $S_n$ consists of all pairs of points with equal coordinates, in the second case it is all pairs of points with distinct coordinates; these two mutually exclusive cases are the only possibilities. We thus have

$\frac{1}{|S_n|}\sum\limits_{g \in S_n} |\mathrm{Fix}(g)|^2=2,$

which says that the second moment of the random variable $Z$ which gives the number of fixed points in a uniformly random permutation is equal to two. Since $\mathbb{E}[Z]=1$ and $\mathbb{E}[Z^2]=2$ you might be tempted to assume that the $k$ th moment of $Z$ is $\mathbb{E}[Z^k]=k,$ but this is wrong and the correct answer is quite a bit more interesting.

For our purposes, all we need is

$\langle \chi^V,\chi^V\rangle =2|S_n|.$

Let $A \in \mathcal{C}(S_n)$ be the random variable defined by

$A(g) = |\mathrm{Fix}(g)|^2.$

We conclude from the above that the character $\chi^V$ of the permutation representation of $S_n$ satisfies

$\langle \chi,\chi \rangle = 2|S_n|.$

Now let $W$ be the one-dimensional subspace of $V$ spanned by $e_1+\dots+e_n,$ which is an irreducible representation of $S_n$ , and let $W^\perp$ be its orthogonal complement, which is the standard representation of $S_n$ . Since $V=W \oplus W^\perp,$ we have $\chi^V=\chi^W+\chi^{W^\perp},$ and therefore

$\langle \chi^V,\chi^V\rangle = \langle \chi^W+\chi^{W^\perp},\chi^W+\chi^{W^\perp}\rangle = \langle \chi^W,\chi^W\rangle + \langle \chi^{W^\perp},\chi^{W^\perp}\rangle,$

where we have used character orthogonality to claim

$\langle \chi^W\chi^{W^\perp}\rangle = 0$

on the grounds that $W$ and $W^\perp$ are non-isomorphic representations of $S_n$ for $n>1.$ Indeed, $W$ is the trivial representation of $S_n$ , in which every permutation acts as the identity on this one-dimensional space. The standard representation $W^\perp$ is the alternating representation of $S_n$ if $n=2,$ and for $n>2$ its dimension is strictly larger than one.

To finish the argument, write

$\langle \chi^W,\chi^W\rangle = \langle \chi^V,\chi^V\rangle - \langle \chi^{W^\perp},\chi^{W^\perp}\rangle=2|S_n|-|S_n| = |S_n|,$

where the fact that $\langle \chi^{W^\perp},\chi^{W^\perp}\rangle=|S_n|$ follows from its irreducibility. Likewise, since $\langle \chi^W,\chi^W\rangle =|S_n|,$ the standard representation of the symmetric group is irreducible.

Thankfully, the basic idea in the representation theory of the symmetric groups is very simple: $S_{n-1}$ is a subgroup of $S_n$ (more precisely, $S_{n-1}$ is isomorphic to the subgroup of $S_n$ consisting of all permutations of $1,2, \dots ,n$ that have $n$ as a fixed point). Thus we have an infinite sequence of nested groups

$S_1 \subset S_2 \subset S_3 \subset \dots,$

or equivalently an infinite sequence of nested algebras

$\mathcal{C}(S_1) \subset \mathcal{C}(S_2) \subset \mathcal{C}(S_3) \subset \dots.$

The strategy is therefore to analyze representations of $S_n$ inductively, by understanding how the unitary representations of $S_n$ is related to those of $S_{n-1}.$

Let $\Lambda_n$ be a set indexing isomorphism classes of irreducible unitary representations of $S_n,$ or equivalently irreducible linear representations of its convolution algebra $\mathcal{C}(S_n).$ For each $\lambda \in \Lambda_n,$ let $(V^\lambda,\Phi^\lambda)$ be a representative of the corresponding isomorphism class. We know $\Lambda_n$ concretely: it is the set of integer partitions of the number $n$ , which also index conjugacy classes in $S_n.$

Since $(V^\lambda,\Phi^\lambda)$ is irreducible, the image of $\mathcal{C}(S_n)$ in $\mathcal{L}(V^\lambda)$ under $\Phi^\lambda$ is all of $\mathcal{L}(V^\lambda),$ by Burnside’s theorem. On the other hand, viewing $S_{n-1}$ as a subgroup of $S_n$ and hence $\mathcal{C}(S_{n-1})$ as a subalgebra of $\mathcal{C}(S_n),$ the image of $\mathcal{C}(S_{n-1})$ in $\mathcal{L}(V^\lambda)$ is not necessarily all of $\mathcal{L}(V^\lambda),$ meaning that $V^\lambda$ is a unitary representation of $S_{n-1},$ but not necessarily an irreducible one. So viewed as a representation of $S_{n-1},$ there is an isotypic decomposition

$V^\lambda = \bigoplus\limits_{\mu \in \Lambda_{n-1}} \langle V^\mu,V^\lambda\rangle V^\mu,$

where the direct sum is over the set $\Lambda_{n-1}$ of partitions of $n-1,$ and $\langle V^\mu,V^\lambda$ is the multiplicity of $V^\mu$ in $V^\lambda$ viewed as a representation of $S_{n-1}.$ The main theorem in the representation theory of the symmetric groups is a strikingly simple description of this isotypic decomposition, which we discuss in Lecture 25.

Math 202B: Lecture 24

Like this:

Published by Jonathan Novak

Leave a ReplyCancel reply

Share this:

Like this:

Published by Jonathan Novak

Leave a ReplyCancel reply

Discover more from Jonathan Novak