# Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

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 ?

-
1) Compute the norm of its character. 2) Compute the character table of the group, then the character of the representation you're looking at. This is basic material in the representation theory of finite groups and not appropriate for MO. –  Qiaochu Yuan Nov 3 '12 at 20:41
To add a bit to Derek Holt's answer, there are two very efficient methods, "Norton's irreducibility criterion" (for your Q1) and "Parker's Meataxe" (for Q2). They were used heavily for the Atlas of finite groups, and they or their extensions (notably by Holt-Rees) seem to remain the most efficient practical methods to work with representations of big groups. Essentially they work over any field, although, as Derek writes, there are issues with Schur indices. The notes by Max Neunhoffer www-groups.mcs.st-and.ac.uk/~neunhoef/Publications/pdf/… give a very nice brief summary. –  Tim Dokchitser Nov 4 '12 at 10:22
–  Alexander Chervov Nov 4 '12 at 10:47
This is just tangentially related -- decomposing representation on the web using Sage: sheaves.github.io/… –  Vít Tuček Mar 3 at 13:38

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.

-
Thank you very much ! I will accept your answers, but let me think over them for a while. May ask you about the complexity of the algorithms you mention - are they polynomial (if yes what degree), again both "worst case" and "average". May I also kindly ask you to look at mathoverflow.net/questions/111444/… –  Alexander Chervov Nov 4 '12 at 10:54

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.

-
Thank you very much for your answer ! I will look at your paper. May I ask you what is the complexity (in size of group) of your algorithm ? (worst case/average) ? May I kindly ask you to look at mathoverflow.net/questions/111444/… –  Alexander Chervov Nov 4 '12 at 10:49
Sorry for late comment. We didn't examine the complexity in the paper because we had to compute and could not find any equivalent algo in the litterature. We use a set of generators as alphabet. The algorithm automatically computes (in principle) a presentation of the module. After one can compute the indecomposable projectors. I will prepare a rough explanation of the philosophy asap. –  Duchamp Gérard H. E. Nov 5 '12 at 20:06
[May I kindly ask you to look at ...] I just did and have no idea about the average case. The worst case seems to be provided by the free algebra because no relation cuts the exploration tree. Let me think of it. –  Duchamp Gérard H. E. Nov 5 '12 at 20:13

Here's a simple algorithm that was proposed in Dixon's 1970 paper: http://www.ams.org/journals/mcom/1970-24-111/S0025-5718-1970-0280611-6/S0025-5718-1970-0280611-6.pdf

It's split into 2 parts:

1. Construct a non-scalar commuting matrix $H$ (if possible)

Dixon presents two variants for part 1. I'll just mention the simpler one here. Let $\rho:G \to \text{GL}(n,\mathbb{C})$ be a (unitary) representation. For $r,s = 1,2,\dots,n$, define

$$H_{rs} = \begin{cases} E_{rr} &\text{if } r = s \\ E_{rs} + E_{sr} &\text{if } r > s \\ i(E_{rs} - E_{sr}) &\text{if } r < s, \end{cases}$$

where $E_{rs}$ is the $n \times n$ matrix with 1 in the $(r,s)^{th}$ entry and 0 everywhere else. Then $\{H_{rs}\}_{r,s=1}^n$ forms a Hermitian basis for the $n \times n$ matrices.

Now for each $r,s$, compute the sum

$$H = \frac{1}{|G|} \sum_{g \in G} \,\, \rho(g)^* \, H_{rs} \, \rho(g)$$

Observe that $H$ commutes with all $\rho(g)$.

If $\rho$ is irreducible, then $H$ is a scalar matrix for all $r,s$. Otherwise, there will be some $r,s$ such that $H$ is non-scalar (because $\{H_{rs}\}_{r,s=1}^n$ forms a basis). In this case, proceed to part 2:

2. Use the eigenspaces of $H$ to decompose $\rho$

Let $H = UJU^*$ be the Jordan decomposition of $H$, where $U$ is unitary. Then

$$U^* \rho(g) U$$

will have the same block-diagonal form for all $g \in G$, yielding a decomposition of $\rho$.

Of course this assumes that the $n$ and $|G|$ are small enough that one can easily run through all the $H_{rs}$ and compute the Jordan decomposition. There are more sophisticated and efficient methods, but I like the simplicity of this one.

I've written an implementation of this algorithm in Sage.

-

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.

This randomized algorithm" simply won't work. Even for a representation which is not irreducible, a random unit vector (say, chosen uniformly) will with probability one not lie in any proper subrepresentation. Think about the case of e.g $\mathbb{Z}/2\mathbb{Z}$ acting on $\mathbb{C}^2$ via the matrix $(1~0;0~-1)$. Then unless the chosen vector is a scalar multiple of $(1~0)$ or $(0~1)$, the span of its orbit will be all of $\mathbb{C}^2$. –  Daniel Litt Nov 4 '12 at 9:11
You can improve the probability by choosing a "random" element $x$ of the algebra generated by the matrices of the group elements, and factorizing its characteristic polynomial $f$. (This is what the Holt-Rees variation of the Meataxe does.) Unfortunately, in characteristic 0, the probability that $f$ is irreducible is high (like 1). But if $f$ has a factor $g$, then choosing your random vector in the nullspace of $g(x)$ is likely to be effective in finding submodules or proving irreducibility. –  Derek Holt Nov 4 '12 at 10:44