Polynomials and Representations XIX

Representations of the Symmetric Group

Let [d] be the set {1,…,d}, and S_dbe the group of bijections $g: [d] \to [d].$ From here on, we shall look at the representations of $S_d.$ Note that this requires a good understanding of representation theory (character theory) of finite groups.

To start, let us first find some representations.

Definition. Given a partition $\lambda \vdash d$ , let $X_\lambda$ be the set of partitions of $[d]$ into disjoint subsets $A_1 \coprod \ldots \coprod A_l$ such that $|A_i| =\lambda_i$ for each $i.$ The group $G = S_d$ then acts on $X_\lambda$ via:

$(A_1, A_2, \ldots, A_l) \overset {g \in S_d} \mapsto (g(A_1), g(A_2), \ldots, g(A_l)).$

Note

If $\lambda_i = \lambda_{i+1}$ , the partitioning is considered different when we swap $A_i$ and $A_{i+1}.$ For example if d = 4 and $\lambda = (2, 2)$ , then $X_\lambda$ has 6 elements:

$\begin{aligned}( \{1,2\}, \{3,4\}), \quad (\{1,3\}, \{2,4\}), \quad (\{1,4\}, \{2,3\}), \\ (\{2,3\}, \{1,4\}), \quad (\{2,4\}, \{1,3\}), \quad (\{3,4\}, \{1,2\}).\end{aligned}$

In general,

$\displaystyle |X_\lambda| = \frac {d!} {\lambda_1 ! \lambda_2 ! \ldots \lambda_l !}.$

As $X_\lambda$ is a G-set, we see that $U_\lambda := K[X_\lambda]$ is a $K[G]$ -module for any field K. Two special cases are of interest.

$\lambda = (d)$ : X has a single element so $U_\lambda$ is the trivial representation;
$\lambda = (1,1,\ldots)$ : X is just the set of permutations of [d] so $U_\lambda$ is the regular representation.

Exercise

Show that for $\lambda = (d-1, 1)$ , $U_\lambda$ is the standard representation of $S_d$ on $[d].$

Let us study such representations in a more general setting.

blue-lin

Representations From G-Sets

Let G be a group and X a G-set; then K[X] is naturally a K[G]-module. We then have the following isomorphisms of K[G]-modules:

Lemma.

$K[X]^\vee \cong K[X]$ (i.e. $K[X]$ is isomorphic to its dual);

$K[X] \otimes_K K[Y] \cong K[X\times Y]$ ;

$\text{Hom}_K(K[X], K[Y]) \cong K[X\times Y]$ ;

$K[X]^G = \{v\in K[X] : \forall g\in G, gv = v\}$ has dimension $|G\backslash X|$ , the number of orbits of X.

Note

In general, a representation is not isomorphic to its dual.

Proof

Take the bilinear map $K[X] \times K[X] \to K$ induced linearly from the map:

$X \times X\to K, \quad (x, y) \mapsto \delta_{xy} = \begin{cases} 1, \quad &\text{if } x=y,\\ 0,\quad &\text{if } x\ne y.\end{cases}$

This induces an isomorphism $K[X] \to K[X]^\vee$ of vector spaces. It is also G-equivariant since the bilinear map is G-equivariant, which proves the first statement.

For the second, linear algebra gives $K[X]\otimes_K K[Y] \cong K[X \times Y]$ as vector spaces, taking $x\otimes y \mapsto (x, y).$ One easily checks that it is G-equivariant.

The third statement follows from the first two since generically, we have $\text{Hom}(V, W) \cong V^\vee \otimes_K W$ for any K[G]-modules V and W. Thus:

$\text{Hom}_K(K[X], K[Y]) \cong K[X]^\vee \otimes_K K[Y] \cong K[X] \otimes_K K[Y] \cong K[X\times Y].$

Finally, if $\sum_{x\in X} c_x x\in K[X]$ is invariant under every $g\in G$ , then $c_x = c_{g x}$ for all $g\in G$ and $x\in X.$ Thus $c_x$ is constant when $x\in X$ runs through an orbit. ♦

blue-lin

Now assume that char(K) = 0.

Question. Given $\lambda, \mu \vdash d,$ what is the following value:

$\displaystyle \left<U_\mu, U_\lambda\right>_G = \dim_L\text{Hom}_{L[G]}(L[X_\mu], L[X_\lambda])$

where $L$ is the algebraic closure of $K$ ?

Note

The reader may assume $K =\mathbb{C}$ to simplify matters, in which case L = K and when we mention “absolutely irreducible”, just replace it with “irreducible”.

Answer

By the above lemma, we have:

$\text{Hom}_{K[G]} (K[X_\mu], K[X_\lambda]) =\text{Hom}_K (K[X_\mu], K[X_\lambda])^G \cong K[X_\lambda \times X_\mu]^G$

which has dimension $|G \backslash (X_\lambda \times X_\mu)|$ . Writing $\lambda = (\lambda_1, \ldots, \lambda_l)$ and $\mu = (\mu_1, \ldots, \mu_{m}),$ let us pick $(A_1, \ldots, A_l) \in X_\lambda$ and $(B_1, \ldots, B_m)\in X_\mu.$ Then the orbit of the pair $(g(X_\lambda), g(X_\mu))$ satisfies:

$|g(A_i) \cap g(B_j)|_{i, j} = |g(A_i \cap B_j)|_{i, j} \quad \text{ for } 1\le i \le l, 1 \le j \le m,$

so the collection of these numbers is invariant over all $g\in G$ .

Conversely, suppose $(A_i), (B_j)$ and $(A_i'), (B_j')$ are partitions of [d] satisfying:

$|A_i| = |A_i'| = \lambda_i, \quad |B_j| = |B_j'| = \mu_j,\quad |A_i \cap B_j| = |A_i' \cap B_j'|$

for all $i, j$ . Then we can find $g\in S_d$ mapping the pairwise intersection sets $A_i \cap B_j$ to $A_i' \cap B_j'$ so the pairs $(A_i), (B_j)$ and $(A_i'), (B_j')$ are in the same orbit. Hence the number of orbits is the number of solutions to