Permutation representation inner product - MathOverflow

Permutation representation inner product

2010-03-05T22:14:08Z

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?

Answer by Jonas Meyer for Permutation representation inner product

2010-03-05T22:30:26Z

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

Answer by Mariano Suárez-Alvarez for Permutation representation inner product

2010-03-05T22:35:29Z

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

Answer by Faisal for Permutation representation inner product

2010-03-05T22:46:13Z

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

Answer by Mariano Suárez-Alvarez for Permutation representation inner product

2010-03-05T23:10:52Z

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.

Answer by Qiaochu Yuan for Permutation representation inner product

2010-03-05T23:30:05Z

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

Answer by Geoff Robinson for Permutation representation inner product

2011-05-02T10:21:56Z

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

Answer by Andreas Blass for Permutation representation inner product

2011-05-02T16:10:22Z

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.