Today I Learned

February 18th

Today I learned an example of representation theory in the service of combinatorics, from Artin 10.6.5. The setup here is that we have $S_n$ act on $\CC^n$ by permuting coordinates, and we're interested in decomposing this representation into irreducible representations.

We do this decomposition manually. We claim the following.

Quickly, we check that these are actually $S_n$-invariant. Note that permuting the coordinates of $0$ or $\langle a,\ldots,a\rangle$ fixes the vector, so $\{0\}$ and $L$ are fixed. And if $\langle a_1,\ldots,a_n\rangle\in P,$ then for any $\sigma\in S_n,$ we have $\langle a_{\sigma1},\ldots,a_{\sigma n}\rangle$ satisfies\[a_{\sigma1}+\cdots+a_{\sigma n}=a_1+\cdots+a_n=0,\]so $\langle a_{\sigma1},\ldots,a_{\sigma n}\rangle\in P.$ Thus, $S_n$ also fixes $P.$ And of course $S_n$ fixes the entire space $\CC^n.$

We now show that these are the only subspaces; fix $V$ to be $S_n$-invariant. We begin by getting rid of trivial cases. If the only vector is $0,$ then $V=\{0\}.$ If all vectors in $V$ have all equal coordinates, and $V$ has a nonzero vector, then we can scale the nonzero vector to force $V\supseteq\{\langle a,\ldots,a\rangle\in\CC^n.$ But then these are all the vectors with equal coordinates, so $V=L.$

Otherwise, we have a vector $v\in S_n$ with not all coordinates equal; applying a suitable permutation in $S_n$ lets us assume that $v=\langle v_1,\ldots,v_n\rangle$ has $v_1\ne v_2.$ Transpositions are in $S_n,$ so we also know\[\hat v=\langle v_2,v_1,v_3,v_4,\ldots,v_n\rangle\in V.\]In particular,\[\frac{v-\hat v}{v_1-v_2}=\langle1,-1,0,0,\ldots,0\rangle\in V.\]So we have $e_1-e_2\in V,$ and applying cyclic shifts tells us $e_k-e_{k+1}\in V$ for $k\in[1,n).$ But this tells us $P\subseteq V$: taking $\langle a_1,\ldots,a_n\rangle\in P,$ we have\[\langle a_1,\ldots,a_n\rangle=\sum_{k=1}^{n-1}\left(\sum_{\ell=1}^ka_\ell\right)(e_k-e_{k+1}).\]Indeed, for $k \lt n$ we get the subtraction of two consecutive sums to give $a_ke_k,$ and at $k=n,$ we get $-(a_1+\cdots+a_{n-1})e_n,$ which is $a_n$ because $\langle a_1,\ldots,a_n\rangle\in P$ has coordinate sum $0.$ To finish, either $V\subseteq P,$ so $V=P,$ or $V$ has a vector $w$ outside of $P,$ in which case $P\cap\CC w=\{0\},$ and so\[\dim V\ge\dim(P\oplus\CC w)=\dim P+\dim\CC w=(n-1)+1=n.\]It follows $\dim V=n,$ so in fact $V=\CC^n.$ This completes the classification of $S_n$-invariant subspaces. $\blacksquare$

From here it is quick to decompose this representation into irreducible representations. Using our $S_n$-invariant subspaces, we label our representation $\rho:S_n\to\op{GL}_n(\CC)$ and let $\rho_L$ and $\rho_P$ be its restrictions to $L$ and $P$ respectively. (These are well-defined because $L$ and $P$ are $S_n$-invariant.) Further, $\CC^n=L\oplus P$ (count dimensions), so we see\[\rho=\rho_L\oplus\rho_P.\]We claim that these are irreducible. Indeed, because of our classification of $S_n$-invariant subspaces, we see that the only $S_n$-invariant subspaces of $L$ is either $\{0\}$ or $L,$ neither of which give us a useful decomposition. The same holds for $P.$ Thus, the above is our decomposition into irreducibles.

Let's use this to do some combinatorics. Because $\rho$ basically makes permutation matrices, we see that $g\in G$ makes $\op{trace}(\rho\sigma)$ equal to the number of $1$s along the diagonal, which is the number of elements fixed by $\sigma.$ That is, our character $\chi$ has\[\chi(\sigma)=|\{n:\sigma n=n\}|.\]Now, using our inner product, we see\[\langle\chi,\chi_L\rangle=1.\]But we can compute the inner product manually, for $\rho_L$ is the trivial representation: for any $\sigma,$ $\rho_L\sigma$ fixes everything in $L.$ So we write\[\langle\chi_L,\chi\rangle=\frac1{n!}\sum_{\sigma\in S_n}\chi(\sigma)\overline{\chi_L(\sigma)}=\frac1{n!}\sum_{\sigma\in S_n}\chi(\sigma).\]Using what we know about $\chi(\sigma),$ we see that this is implies\[\mathbb E[\text{number of fixed points}]=1.\]Of course, this follows quickly from linearity of expectation, but it's amusing that we got here from representation theory. Similarly, we can compute\[2=\langle\chi,\chi\rangle=\frac1{n!}\sum_{\sigma\in S_n}|\chi(\sigma)|^2.\]From this it follows\[\mathbb E\left[(\text{number of fixed points})^2\right]=2,\]which is less trivial to prove, so the ease by which representation theory got here is more impressive.

We do remark that we can actually compute $\mathbb E\left[(\text{number of fixed points})^2\right]$ using linearity of expectation. For a random permutation, we (as usual), let $X_k$ by the event that $k$ is fixed by the permutation. We want\[\mathbb E\left[\left(\sum_{k=1}^nX_k\right)^2\right]=\mathbb E\left[\sum_{k=1}^nX_k^2+2\sum_{\substack{k,\ell=1\\k\ne\ell}}^nX_kX_\ell\right].\]To be clear, the trick here is to believe that this expansion is useful. From here, we use linearity of expectation tells us we want\[\sum_{k=1}^n\mathbb E\left[X_k^2\right]+2\sum_{\substack{k,\ell=1\\k\ne\ell}}^n\mathbb E[X_kX_\ell].\]Now, $X_k$ is either $0$ or $1,$ so $X_k^2=X_k,$ so $\mathbb E[X_k^2]=1/n.$ So\[\sum_{k=1}^n\mathbb E\left[X_k^2\right]=1.\]As for $X_kX_\ell,$ this is equal to $1$ if and only if both $k$ and $\ell$ are fixed, which occurs with probability $\frac1n\cdot\frac1{n-1},$ which is our $\mathbb E[X_kX_\ell].$ Thus,\[\sum_{\substack{k,\ell=1\\k\ne\ell}}^n\mathbb E[X_kX_\ell]=n(n-1)\cdot\frac1{n(n-1)}=1.\]Combining, we see\[\mathbb E\left[(\text{number of fixed points})^2\right]=1+1=2,\]as desired.

Quickly, we say that the fact we have combinatorial proofs of those identities could actually be read backwards to prove the classification of $S_n$-invariant subspaces. Indeed, we claim $L$ and $P$ have no nontrivial $S_n$-invariant subspaces. Knowing $\langle\chi,\chi,\rangle=2$ tells us that $\rho$ is the direct sum of two irreducible representations; we can check $S_n$ is trivial on $L,$ so the trivial representation $\rho_L$ is one of the irreducibles, and\[\langle\chi,\chi_L\rangle=1\]tells us that there is only one other irreducible. Well, we also check that $P$ is $S_n$-invariant and that $\CC^n=L\oplus P,$ so we are forced to conclude\[\rho=\rho_L\oplus\rho_P\]is a decomposition into irreducibles. Thus, $L$ and $P$ cannot have any nontrivial $S_n$-invariant subspaces, which is what we wanted.