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!
Best Answer
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$:
There's four possible maps (all non-invertible), two of which are:
Finally, the inner product is the number of orbits, which is the number of values r takes, which is $l + 1$.