Permutation representation inner product - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T16:30:38Z http://mathoverflow.net/feeds/question/17230 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17230/permutation-representation-inner-product Permutation representation inner product Marc 2010-03-05T22:14:08Z 2011-05-02T16:10:22Z <p>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))$.</p> <p>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?</p> http://mathoverflow.net/questions/17230/permutation-representation-inner-product/17235#17235 Answer by Jonas Meyer for Permutation representation inner product Jonas Meyer 2010-03-05T22:30:26Z 2010-03-05T22:30:26Z <p>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 "<a href="http://www.springerlink.com/content/m36k5q2741233625/" rel="nofollow">An identity for fixed points of permutations</a>" by Goldman, where the average of the $k^{th}$ powers of the number of fixed points is shown to be the <code>$k^{th}$</code> Bell number <code>$B_k$</code> when <code>$k&lt;n$</code>. Your case follows because <code>$B_2=2$</code>.</p> http://mathoverflow.net/questions/17230/permutation-representation-inner-product/17237#17237 Answer by Mariano Suárez-Alvarez for Permutation representation inner product Mariano Suárez-Alvarez 2010-03-05T22:35:29Z 2010-03-05T22:35:29Z <p>You are computing the inner product of $\chi$ with itself. </p> <p>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$$.</p> http://mathoverflow.net/questions/17230/permutation-representation-inner-product/17239#17239 Answer by Faisal for Permutation representation inner product Faisal 2010-03-05T22:46:13Z 2010-03-05T22:57:24Z <p>Here's another proof.</p> <p>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$.</p> <p>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\}$.</p> http://mathoverflow.net/questions/17230/permutation-representation-inner-product/17243#17243 Answer by Mariano Suárez-Alvarez for Permutation representation inner product Mariano Suárez-Alvarez 2010-03-05T23:10:52Z 2010-03-05T23:10:52Z <p>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 <em>Group theory</em>, Thm. 10.1.6.</p> http://mathoverflow.net/questions/17230/permutation-representation-inner-product/17244#17244 Answer by Qiaochu Yuan for Permutation representation inner product Qiaochu Yuan 2010-03-05T23:30:05Z 2011-05-02T15:18:11Z <p>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 &lt; |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$!).</p> <p>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!)</p> http://mathoverflow.net/questions/17230/permutation-representation-inner-product/63691#63691 Answer by Geoff Robinson for Permutation representation inner product Geoff Robinson 2011-05-02T10:21:56Z 2011-05-02T10:21:56Z <p>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$.</p> http://mathoverflow.net/questions/17230/permutation-representation-inner-product/63709#63709 Answer by Andreas Blass for Permutation representation inner product Andreas Blass 2011-05-02T16:10:22Z 2011-05-02T16:10:22Z <p>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 <code>$\langle\chi,\chi\rangle$</code> 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 <code>$S_n$</code>) of the random variable "number of fixed pairs." That random variable is the sum, over all pairs $(x,y)$, of the indicator variable <code>$F_{x,y}$</code> whose value at any permutation $g$ is 1 or 0 according to whether $g$ fixes $x$ and $y$ or not. So <code>$\langle\chi,\chi\rangle$</code> is the sum, over all $x,y$, of the expectations of these <code>$F_{x,y}$</code>, 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 <code>$n^2-n$</code> 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.</p>