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

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?

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.