## Permutation representation inner product

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2011 at 17:31

## 7 Answers

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$$.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

3
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 2011 at 16:14

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$.

-

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!)

-

1
@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 2011 at 10:30
@Tom: thanks for the correction. – Qiaochu Yuan May 2 2011 at 15:17

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 2010 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 2010 at 5:12

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\}$.

-

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$`.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 89, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9170780777931213, "perplexity_flag": "head"}