How to compute all irreducible representations of a finite group ? (how GAP is doing this?)

Question

Let us "take" a finite group G. Here "take" I mean any type of group-theoretic description you prefer: e.g. as an explicit subset of GL (or other group) or Cayley table, whatever.

Question: How should we compute representation theoretic information about the group ?

By "representation theoretic information" I mean

a) number of irreps over complex numbers

b) their dimensions

c) their characters

d) matrices defining the representations

Any other kind of comments on further questions like modular or rational representations is also welcome.

What complexity should we expect from these algorithms ? And, are the current algorithms best possible or developing group theory may lead to more effective algorithms ?

---

Let me clarify my question by example.

For example - number of irreps = number of conjugacy classes. So if I would be asked question a) (i.e. compute the number of irreps) I would do the following. Just take element - compute its conjugacy class, take element, out this conjugacy class - compute its conjugacy class and so on. Finally I get the number of conjugacy classes and hence I get number of irreps.

So pay attention a) I assume that all operations like "take element", "are two elements equal", "take inverse of an element" has same complexity say "1".

b) this algorithm is based on the not so trivial fact that number of irreps = number of conjugacy classes.

Subquestion are there less complexity algorithms ?

Answer 1

You seem to be asking for a description of the the algorithms in computational representation theory. I think that is far too broad a question for this site and you need to be more specific. There is a recently published book on this topic, which you might like to look at:

Representations of Groups A Computational Approach Klaus Lux, Herbert Pahlings Cambridge University Press, 2012. Series: Cambridge Studies in Advanced Mathematics(No. 124)

As for the algorithms used by GAP, you can always look at source code! For example, for complex representations, the general approach is to compute the conjugacy classes and character table first, using the Dixon-Schneider algorithm for the latter, and a method of Dixon for getting the matrices of the representation from the character, which works if the group has a subgroup for which the restriction of the character has a linear constituent with multiplicity 1. For modular representations the Meataxe algorithm mentioned by Benjamin Steinberg is more effective.

The method you describe for finding conjugacy classes involving choosing random elements until you have covered all classes works well for groups that are not too large do not have very small conjugacy classes that are hard to find. For larger groups, there are better methods - I wrote something about this recently in

https://math.stackexchange.com/questions/198353/algorithm-to-find-conjugacy-classes-of-subgroups-elements-in-matrix-groups/198425#198425groups

BTW, I have no idea what you mean by "are there less complexity algorithms?"

Answer 2

If the group is given by its multiplication table then there are polynomial-time algorithms for all the tasks you mentioned (over $\mathbb{C}$; these don't handle modular representations).

Babai and Ronyai. Computing irreducible representations of finite groups. Math. Comp. 55 (1990), no. 192, 705–722.