Question

Question 1 Given a representation of a finite group, what algorithm can be used to check is it irreducible or not ?

(Main case - complex numbers, comments on other cases are also welcome. "Given" means finite set of matrices is given).

Question 2 Given a representation of a finite group, what algorithms can be used to decompose it to the direct sum of irreducibles) ?

---

For the question 1 I would do the following: rep is irrep if its commutant consists of scalar matrices. So I can try to find matrices commuting with all elements of the group and look whether I get only scalar matrices.

Are there more effective ways to do it ?

---

Related question: http://mathoverflow.net/questions/111379/how-to-compute-all-irreducible-representations-of-a-finite-group-how-gap-is-do

Answer 1

I think this question is not quite so trivial as Qiaochu suggests. Devising practical algorithms for problems of this type is certainly an active area of research within the computational group theory community.

The first problem is that the group may be too large for it to be feasible to compute its conjugacy classes and character table. It might be one of the large sporadic simple groups for example. Over finite fields, the so-called Meataxe methods, which are actually just based on linear algebra, have been used to find the composition factors of some modules of dimensions in the hundreds of thousands. There are ongoing efforts to extend these methods to characteristic zero.

If your representation is in characteristic zero, and you can compute the classes and character table, then the straightforward character theoretic methods will tell you what the absolutely irreducible constituents of the module are, but that does not immediately enable you to decompose the module explicitly.

Another problem that arises in practice is that your representation may be over the rationals, for example, but its absolutely irreducible constituents might not be realizable over the rationals. In that case, the reducibility of the module will depend on the Schur Index of representation',s constituents, which can be calcualated from the character table. But again, if you find out, for example, that a rational representation is the direct sum of two isomorphic irreducibles, then it can be very difficult to find the basis change that exhibits the direct sum.

Answer 2

Some years ago, we had to develop an approach inherited from Schützenberger's theory of automata (with weights) in order to explicitly split modules into indecomposable factors. The paper is available at http://lipn.univ-paris13.fr/~duchamp/Publications/decbf5.pdf and was designed for cryptography (the general framework for modules is in section 3), but I developed the same concept in characteristic zero for modules of Hecke algebras. The algorithm provides a certificate of indecomposability and I think it can give also a certificate of irreducibility.
I you are interested, I can explain.

Answer 3

I don't know how to do this exactly, but one could try a probabilistic approach. Say the representation is $V$, and $V$ is defined over a $\mathbb{C}$ (or at least $\mathbb{Q}$). Pick a random non-zero element $v \in V$ and compute the dimension of the space spanned by the orbit $Gv$. If this dimension is $< \dim V$ then $V$ is reducible and (1) is answered. If not, try again. I would guess that if, after several iterations, the subrepresentations are all equal to $V$, then with high probability $V$ is multiplicity free (Edit. This did read "irreducible". As pointed out in the comments by Daniel Litt this is not so!).

The worst part about this algorithm (aside from not detecting reducibility) is having to list the elements of $G$. But I guess this is already done according to Alexander's statement of the problem. You could also try to approximate the orbit. Say if $\dim V = 1000$ and $G = S_{12}$, then take some random $2000$ elements of $G$ and apply them $v$, and let this be your approximate orbit.

Another bad thing about this algorithm is that it can be numerically unstable.