# Permutation representation inner product

Let $\rho : S_n \rightarrow \text{GL}(n, \mathbb{C})$ be the homomorphism mapping a permutation $g$ to its permutation matrix. Let $\chi(g) = \text{Trace}(\rho(g))$.

What is the value of $\langle \chi, \chi \rangle = \displaystyle \frac{1}{n!} \sum_{g \in S_n} \chi(g)^2$ ? Computing this expression for small $n$ yields $2$. Is this always true?

-
Hmmm... looks like a homework question! (reason: it IS one, in my course on rep's of finite groups). –  Alain Valette May 2 '11 at 17:31

You are computing the inner product of $\chi$ with itself.

Since $\chi=\mathrm{triv}+\mathrm{std}$ as a $S_n$-module, with $\mathrm{triv}$ being the trivial reprsentation, and $\mathrm{std}$ its orthogonal complement, which is an irreducible $S_n$-module, and since the inner product is, well, an inner product and distinct irreducible characters are orthogonal, your $2$ follows from $$\langle\chi,\chi\rangle=\langle\mathrm{triv}+\mathrm{std},\mathrm{triv}+\mathrm{std}\rangle=\langle\mathrm{triv},\mathrm{triv}\rangle+\langle\mathrm{std},\mathrm{std}\rangle=1+1$$.

-

A small generalization. Any doubly transitive action of a group $G$ on a set $X$ has the property that $\frac{1}{|G|} \sum_{g \in G} \text{Fix}(g)^2 = 2$. This is because, by double transitivity, the diagonal action of $G$ on $X^2$ has precisely two orbits, the orbit where the first factor equals the second and the orbit where it doesn't, so the result follows by Burnside's lemma. Similarly, any $k$-transitive action of a group $G$ on a set $X$ with $k < |X|$ has the property that $\frac{1}{|G|} \sum_{g \in G} \text{Fix}(g)^k = B_k$, since the orbits of the diagonal action of $G$ on $X^k$ can naturally be put into bijection with partitions of a $k$-element set. For $k \ge |X|$ the sum evaluates to the number of partitions of a $k$-element set into at most $|X|$ parts (of course, the action can only be $k$-transitive for $k = |X|$ if $G$ is in fact the full group of permutations on $X$!).

The representation-theoretic upshot of all this is that the permutation representation corresponding to a doubly transitive group action always breaks down into the direct sum of one copy of the trivial representation and an irreducible representation. This is an easy way to write down nice irreducible representations of groups like $PSL_2(\mathbb{F}_q)$, which has a triply transitive action on $\mathbb{P}^1(\mathbb{F}_q)$ (edit: when $q$ is even!)

-
@Qiaochu: concerning your last comment: $PSL_2(q)$ is only triply transitive when $q$ is even; if $q$ is odd, the two-point stabilizers have two orbits (corresponding to the squares and non-squares in $\mathbb{F}_q^\times$). –  Tom De Medts May 2 '11 at 10:30
@Tom: thanks for the correction. –  Qiaochu Yuan May 2 '11 at 15:17

The trace of a permutation matrix is the number of fixed points of the corresponding permutation. This is a special case of the identity proved in "An identity for fixed points of permutations" by Goldman, where the average of the $k^{th}$ powers of the number of fixed points is shown to be the $k^{th}$ Bell number $B_k$ when $k<n$. Your case follows because $B_2=2$.

-

Here's another proof.

If $G$ acts transitively on $X$, then the permutation representation of $G$ is induced from the permutation representation of the stabilizer $S$ of an arbitrary point. As a result, $\langle \chi , \chi \rangle$ counts the number of orbits of $S$ on $X$.

In your situation $G=S_n$ is acting transitively on $X=\{1,\ldots,n\}$. Let $S$ be the stabilizer of $n$; this is pretty much $S_{n-1} \subset S_n$, which has two orbits on $X$: $\{1,\ldots, n-1\}$ and $\{n\}$.

-

Alternatively, let $X=\{1,\dots,n\}$ and $A=\{(x,y,g)\in X\times X\times S_n:gx=x, gy=y\}$. The sum $\sum_g\chi(g)^2$ can be evaluated counting elements of $A$ in two different ways, as explained in W.R.Scott's Group theory, Thm. 10.1.6.

-
Isn't this just one of the standard proofs of Burnside's lemma for the action of S_n on X^2? –  Qiaochu Yuan Mar 5 '10 at 23:23
Well, the statement is Burnside's lemma for the action of S_n on X^2 :) –  Mariano Suárez-Alvarez Mar 6 '10 at 5:12

Another fact, of which this is a special case, well-known to (many) group theorists, is that if $G$ is a finite transitive permutation group, and $H$ is a point-stabilizer, then the squared-norm of the permutation character $1_{H}^{G}$ is the number of distinct $(H,H)$-double cosets in $G$, which is the same as the number of orbits of $H$ on the points in the permutation action. This is a standard application of Mackey's formula for the restriction to one subgroup of a character (or representation) induced from another subgroup (this result can be found in standard texts such as Curtis and Reiner), after first applying Frobenius reciprocity to conclude that $\langle 1_{H}^{G}, 1_{H}^{G}\rangle$ is equal to $\langle (1_{H}^{G})_{H},1 \rangle$.

-

Much as I like Burnside's Lemma, induced (permutation) representations, and other parts of group theory, I can't resist pointing out an alternative argument that uses essentially no group theory but relies on the fact that expectation (of random variables) is linear. Since $\chi(g)$ is the number of fixed-points of $g$, its square is the number of fixed ordered pairs $(x,y)$, where of course fixing a pair means fixing both its components. So the $\langle\chi,\chi\rangle$ in the question is the average number of fixed pairs of a permutation $g$, in other words the expectation (with respect to the uniform probability measure on $S_n$) of the random variable "number of fixed pairs." That random variable is the sum, over all pairs $(x,y)$, of the indicator variable $F_{x,y}$ whose value at any permutation $g$ is 1 or 0 according to whether $g$ fixes $x$ and $y$ or not. So $\langle\chi,\chi\rangle$ is the sum, over all $x,y$, of the expectations of these $F_{x,y}$, and these expectations are just the probabilities that a random permutation fixes $x$ and $y$. For each of the $n$ pairs where $x=y$, that probability is $1/n$, so all these together contribute 1 to the sum. For each of the remaining $n^2-n$ pairs, the probability is $(1/n)(1/(n-1))$ (namely, probability $1/n$ to fix $x$ and conditional probability $1/(n-1)$ to fix $y$ given that $x$ is fixed). So these pairs also contribute 1 to the sum, for a total of 2.

-
I think that if one writes down a proof of Burnside's lemma, and reads it in the correct light and angle one gets the argument you wrote without changing a word :) –  Mariano Suárez-Alvarez May 2 '11 at 16:14