# Product of Permutation Representation Characters

Consider the action of $$S_n$$ on $$x_i$$, where $$x_i$$ is a set of $$i$$-element subsets of $$X =$$ {$$1, 2, ..., n$$} (so $$|x_i| = {n \choose i}$$).

Now, let $$\pi_i$$ be the character of the permutation representation of $$S_n$$ acting on $$x_i$$ (ie, $$\pi_i(g)$$ is the trace of an $${n \choose i} \times {n \choose i}$$-dimensional permutation matrix acting on the complex vector space $$\mathbb{C} x_i$$).

A paper I am currently reading states (in Appendix C) that for $$0 \leq l \leq k \leq n/2$$, the inner product of two such characters $$\langle \pi_l, \pi_k \rangle = \langle \pi_l \pi_k, \mathbb{1}_G \rangle = l + 1$$ where $$\mathbb{1}_G$$ is the trivial representation. I am struggling to understand why this is so.

After reading some notes on representation theory, I know that the character $$\pi_i(g)$$ is the number of elements fixed by a permutation $$g$$, and that $$\langle \pi_l, \pi_k \rangle = \langle \pi_l \pi_k, \mathbb{1}_G \rangle$$ is the number of orbits of $$S_n$$ on $$x_l \times x_k$$. I'm also convinced that for $$i \neq 0, n$$ the permutation representation on $$x_i$$ is faithful (though I'm not sure if this is relevant).

I don't know how to prove this result - any help would be much appreciated!

I think I have it now:

Firstly, let's take an element $$(a, b) = (\{a_1, a_2, .., a_l \}, \{b_1, b_2, .., b_k \}) \in x_l \times x_k$$. A permutation $$\sigma$$ acts on this as $$\sigma (a, b) = (\{\sigma (a_1), .., \sigma (a_l) \}, \{\sigma (b_1), .., \sigma (b_k) \})$$.

$$a_i$$ and $$b_i$$ take values out of $$\{ 1, 2, .., n \}$$. For $$i \neq j$$, $$a_i \neq a_j$$ and $$b_i \neq b_j$$. However, $$a_i = b_j$$ is allowed. With this in mind, define the 'overlap' $$r = | a \cap b |$$, and notice that $$0 \leq r \leq l$$. Therefore, $$r$$ takes on $$l+1$$ values.

It turns out that $$r$$ indexes each orbit. To see this, note that each $$(a, b)$$ has $$l + k - r$$ unique numbers. We can find a permutation taking us from $$(a, b)$$ to $$(a', b')$$ with $$r = r'$$ by specifying $$l + k - r$$ transpositions.

If $$r \neq r'$$, then (without loss of generality) take $$r' > r$$. A map taking us from $$(a, b)$$ to $$(a', b')$$ now has a domain of cardinality $$l + k - r$$ and co-domain of cardinality $$l + k - r'$$. The domain is larger than the co-domain, so the map is non-invertible and thus cannot be a group action.

As a concrete example, we can take $$n=6, l=2, k=3$$:

• $$(a,b) = (\{1,2\}, \{1,4,3\})$$ with $$r=1$$
• $$(a’,b’) = (\{1,3\}, \{1,2,3\})$$ with $$r’=2$$

There's four possible maps (all non-invertible), two of which are:

• $$1 \rightarrow 1, 2 \rightarrow 3, 3 \rightarrow 3, 4 \rightarrow 2$$
• $$1 \rightarrow 3, 2 \rightarrow 1, 3 \rightarrow 1, 4 \rightarrow 2$$

Finally, the inner product is the number of orbits, which is the number of values r takes, which is $$l + 1$$.