Is there an easy way to calculate $\sum_{s \in t^G} \rho(s)$ for a representation $\rho$ of $G$?

Question

I am looking at ways to quickly decompose finite group representations into irreducibles. I am following Serre's book "Linear Representations of Finite Groups". He gives a formula for computing the canonical decomposition (that is, if we have $\rho : G \to GL(V)$, the decomposition of $V$ into $\oplus_i V_i$ where each $V_i$ is a direct sum of isomorphic representations). This is given as a formula for a projection $p_i : V \to V_i$:

$$p_i = \frac{n_i}{|G|} \sum_{t \in G} \chi_i(t)^* \rho(t)$$

($n_i$ is the degree of the irrep we are considering, $\chi_i$ the character)

If the group is very large, this is very tedious to do. I think there must be a way to speed this up by taking advantage of the fact that $\chi_i$ is the same on conjugacy classes.

For example, you can split up the sum by conjugacy class, for each $t$ a representative of a conjugacy class, you have $\sum_{s \in t^G}\chi_i(s)^* \rho(s)$. Now I can pull out the character since it's a class function to get $\chi_i(t)^* \sum_{s \in t^G} \rho(s)$.

But this doesn't really help, since the big part of the calculation is still to be done: adding up hundreds of matrices $\rho(s)$.

Is there some trick I can do to avoid summing over the group?

Answer 1

This answer doesn't avoid summing over the group, but it's much faster than just naively enumerating elements and summing.

Say $G$ is a permutation group (if not, just find an isomorphism to a permutation group, $G$ is finite).

You can find a base $\{1,\ldots,n\}$ and stabiliser chain for $G$:

$$G = G_0 \geq \ldots \geq G_n = \{1\}$$

where $G_i$ stabilises the first $i$ points in the base.

Then use that $\sum_{g \in G_i} \rho(g) = \sum_{r_j} (\sum_{g \in G_{i+1}} \rho(g)) r_j$ where the $r_j$ are right coset representatives of $G_{i+1}$ in $G_i$. Starting at $G_n$ and using this to progressively move up and get to the sum over $G_0$ is fast.

I haven't thought too hard about the complexity, runtime etc, but experimentally, using the GAP algebra system (which implements the Schreier-Sims algorithm for finding such chains (StabChain et al)), summing over $S_{10}$ went from 4 minutes to 30 milliseconds, this is good enough for me.