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

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 ?

-
Look at mathoverflow.net/questions/32836/… and google meataxe. –  Benjamin Steinberg Nov 3 '12 at 15:07
–  Alexander Chervov Nov 3 '12 at 20:17
Just found that similar question has been asked: mathoverflow.net/questions/45560/… –  Alexander Chervov Nov 4 '12 at 10:59

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

http://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?"

-
Thank you very much ! May I kindly ask you to look also at mathoverflow.net/questions/111404/… –  Alexander Chervov Nov 3 '12 at 20:21
PS concerning your last remark - actually what you write at MSE seems to answer me that question. PSPS Complexity - is complexity - just count of operations. Of course it depends on input group, so we may speak about "worst case" "average" (for some class of groups). I was interested about any information known about this, and your MSE reply provides such an information. Thank you again ! –  Alexander Chervov Nov 3 '12 at 20:31

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.

-