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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.