## irreducible decomposition of the permutation representation of S_n continued

Last lecture we ended by mentioning the decomposition of S_n
representation on L(X_{k,n-k}) where X_{k,n-k} = S_n/(S_k times
S_{n-k})), given by
L(X_{k,n-k}) = S^n oplus S^{n-1,1} oplus ldots oplus S^{n-k,k} assuming n-k ge k.
Of course I didn’t use the notation S^{n-k,k} before, instead the
summands are (d^*)^k ker d cap M_{k,n-k}, where M_{k,n-k} = S_n /
(S_k times S_{n-k}), the S_n homogeneous of unordered k sets.
It is not difficult to check that (d^*)^k is injective on ker d cap
M_{k,n-k} but I won’t deal with routine computation here. Instead I
want to show the following proposition:
The S^{n-k,k} are distinct irreducible representations of S_n, hence
proving that the above decomposition of L(X_{k,n-k}) is indeed a irrep
decomposition.
The main representation theoretic tool we use here to prove such
statements is Wielandt’s lemma, which is a consequence of Burnside’s
lemma, both of which we give somewhat detailed proof here.
The basic idea is to compare the decomposition of L(X_k) with that of L(X_{k-1}) and see how many irreps they have in common. Wielandt’s lemma says the following:
if H is a subgroup of G, then the number of H orbits on G/H, where H acts on G/H from the left (the right action is clearly trivial), equals the sum of squares of the multiplicities of the irreducible representations in the decomposition of L(X) viewed as a G representation space.
A slight generalization of this lemma says that if H, K are subgroups of G, let X = G/H, Y = G/K, then the number of G orbits on X times Y (where the action is the diagonal one, i.e., g(x,y) = (gx, gy)) is equal to the number of H orbits on Y which is in turn equal to the number of K orbits on X. In fact this number equals sum_{i in I cap J} m_i n_i, where I is the index set of irrep components of L(X) and J is the index set of the irrep components of L(Y) and m_i is the multiplicity of the ith irrep in L(X) and similarly n_i is the multiplicity of the ith irrep in L(Y).

Let’s see how we use these two results inductively to obtain the decomposition of the S_n module L(X_{k,n-k}). Clearly S_{n-1} times S_1 has two orbit on X_{1,n-1} = S_n/ (S_{n-1} times S_1), namely {1}, and {j}, j > 1. So the only choice of multiplicity is m_1 = 1, m_2 = 1. We know there is such a decomposition for X_{1,n-1}, namely the 1 -dimensional space spanned by sum_{i in [1,n]} delta_i, corresponding to the trivial S_n representation, and the complementary (n-1)-dimensional S_n invariant subspace consisting of vectors in CC^n whose components add up to 0, which we call S^{n-1,1}. This proves indirectly that both of these are irreducible representations (note that the trivial representation is trivally irreducible, but S^{n-1,1} is less trivial, in fact I don’t know how to prove it directly, any suggestions?).

Next we realize that the number of orbits for the action of H=S_k times S_{n-k} on X_{k,n-k} is k+1, where each orbit is characterized by the number of elements from 1 to k that are in the k sets, e.g., if k = 3, then {1,2,3} and {1,2,4} are in different orbits, but {1,2,4} and {1,3,4} are in the same orbit.
Similarly there are k orbits for the action of K=S_{k-1} times S_{n-k+1} on X_{k,n-k}. So by the generalized Wielandt’s lemma, there are k orbits for the action of H on X_{k-1,n-k+1} as well, by switching the roles of H and K. This means there are k G-orbits on X_k times X_{k-1}, which equals sum_{i in I cap J} m_i n_i. But since we know by induction that each irrep component of L(X_{k-1}) has multiplicity 1, all the n_i =1. Furthermore by Wielandt’s lemma, sum_i m_i^2 = k+1, since that’s the number of H orbits on X_k = S_n /H, If any of the m_i is > 1, then even the sum of all the m_i’s cannot be as large as k, because the size of I must be less than k+1 – 3. So certainly sum_{i in I cap J} n_i m_i < k a contradiction. So we must have m_i = 1 for all i. This means L(X_k) decomposes into k+1 distinct irreps, and share the first k of them with L(X_{k-1}). We share label these irreps by S^{j,n-j} for j up to n/2. The remaining S^{j,n-j}’s are symmetrically equal to their S^{n-j,j} counterparts. In fact as Silberstein, Scarabotti and Tolli later points out in chapter 10, the index {j,n-j} is a special case of the young’s tableau partition notation. Indeed all the irreps of S_n are indexed by the different young tableaux.
Using the same comparison method as described in the previous paragraph, one can actually decompose the representation of S_n on S_n / S_{k_1} times S_{k_2} times ldots times S_{n- k_1 – ldots} into the S^{some young_tableau} ‘s.

We shall devote the remaining space to proving Wielandt’s lemma. We do the general case as it was left as an exercise in [SST].
To show that the H orbits on Y=G/K are equal in number of G orbits on X times Y, we construct an explicit bijection. Let x_0 = H viewed as a coset element in G/H, then (x_0,y) and (x_0,y’) are in the same orbit if there is some g in G with gy = y’ and g in H. But {gK: g in H} is precisely the orbit of K in Y under the action of H. And it’s clear that if y_1, y_2, ldots, y_k is a set of representatives of the H orbits on Y, then (x_0, y_i) belong to different orbits of G on X times Y, because in order for g(x_0,y_i) = (x_0,y_j), g must be in H. But (x_0,y_j) indeed for a spanning set of representatives of the orbits of G on X times Y since for any (x,y), we can find g such that gx = x_0, hence bring it down to the level set with first coordinate x_0.
By symmetry the number of K orbits on X is also the same.
The part that requires Burnside’s lemma is to show the number of orbits = sum_{i in I cap J} m_i n_i. Indeed
sum_{i in I cap J} m_i n_i = 1/G sum_{g in G} chi_X (g) chi_Y (g)
where chi_X is the character associated with the G-representation L(X). The reason is that characters of a representation decomposes into the sum of the characters of the irreducible components, and characters of distinct irreps are orthogonal, thanks to the fact that matrix elements are different irreps are orthogonal, a fact that’s central to all the orthogonality results in representation theory, which is a simple consequence of Schur’s lemma. The 1/G is the right normalization factor by considering the trivial character.
Now chi_X(g) chi_Y(g) is also chi_{X times Y}(g), the character associated with the diagonal action of G on X times Y, because chi_{X times Y} (g) = sum_{x ,y} delta_{(x,y), g(x,y)}= sum_x delta{x, gx} sum_y delta{y, gy} = chi_X(g) chi_Y(g). Now Burnside’s lemma says the following
if G acts on X transitively, then sum_{g in G} chi_X(g) = sum_{x in X} |Stab_G(x)|, where Stab_G(x) is the stabilizer of x under G. And the latter equals |G| times the number of G orits in X, which is clear because if x_1, ldots, x_k all belong to the same orbit, then their stabilizers all have the same size (they are conjugates of each other), which equals |G| / k, hence summing |Stab_G(x_i)| would equal to  |G|. So each orbit has a contribition of |G| in the final sum.
Applying this result, we get 1/G sum_{g in G} chi_X(g) chi_Y(g) = the number of G orbits on X times Y.

The only thing remaining to be proved is the first statement of Burnside’s lemma. But since delta_x form a linear basis of L(X), sum_g chi_X(g) = sum_{g,x} delta_{gx = x} = sum_x sum_g delta_{gx = x} = sum_x |Stab_G(x)|, as desired.