A representation of the Symmetric Group $S_n$ over $\mathbb{Z}$ is a homomorphism $rho: S_n \rightarrow M(\mathbb{Z})$, i.e. from permutations to square integer matrices.

My understanding (from my elementary knowledge of representation theory) is that the right-hand side of this mapping can always be expressed as a direct sum of irreducible matrices, i.e. matrices which cannot themselves be expressed as a sum of the other irreducibles.

Is there a named algorithm for decomposing a permutation into this sum of irreducible matrices?

In particular, are this algorithm (and its inverse) implemented in GAP?

EDIT: As pointed out by Alexander Hulpke in an answer below, this question is poorly-phrased (in particular, the use of the term decomposition) in terms of what I'm actually looking for, which is the ability to apply the above homomorphisms to some element $g$, then recover $g$ via their pre-images.

  • $\begingroup$ What do you mean by 'decomposing a permutation into a direct sum of irreducible representation matrices'? $\endgroup$ – Orat Jun 17 '17 at 19:11
  • $\begingroup$ Edited, in an attempt to further clarify $\endgroup$ – NietzscheanAI Jun 17 '17 at 20:18
  • 1
    $\begingroup$ What is an irreducible matrix ? $\endgroup$ – user171326 Jun 17 '17 at 20:20
  • $\begingroup$ More detail added. $\endgroup$ – NietzscheanAI Jun 17 '17 at 22:34
  • $\begingroup$ Your definition of irreducible should refer to direct sums of matrices. $\endgroup$ – Mariano Suárez-Álvarez Jun 17 '17 at 23:06

There is a set of algorithms, going by the name of "MeatAxe" that take a representation and return the irreducible constituents. The version implemented in GAP is over finite fields, but presumably by working modulo suitable large primes you could recover the result over Z.

If you do not care about the actual decomposition, but only how it decomposes character theory will give an easier approach.

I am unsure what you mean by inverse algorithm -- this would be just direct sums of generator matrices.

| cite | improve this answer | |

I can confirm (thanks to Stefan Kohl, Marc Keilberg and Max Horn) that it's possible to obtain the irreducible representation homomorphisms, apply them to some element g and then recover it (the 'inverse' operation referred to in original phrasing of the question) via the GAP method IrreducibleRepresentations.

IrreducibleRepresentations uses Dixon's algorithm under the hood and yields a list of homomorphisms (irr in the listing below).

These homomorphisms (images in the listing below) are invertible (PreImagesElm) and the original g can be recovered by forming the direct sum of these preimages:

gap> G:=SymmetricGroup(5);;
gap> irr:=IrreducibleRepresentations(G);;
gap> g:=Random(G);
gap> images := List(irr,r->Image(r,g));;
gap> pre:=Intersection(List([1..Length(irr)], i -> PreImagesElm(irr[i], images[i])));
[ (1,4,3) ]
| cite | improve this answer | |
  • $\begingroup$ IrreducibleRepresentations determines representations, it does not decompose a given representation (as the question asked). The algorithm is by Dixon, but rather "Constructing representations of finite groups. Groups and computation (New Brunswick, NJ, 1991), 105–112, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 11, Amer. Math. Soc., Providence, RI, 1993. (MR 1235797). $\endgroup$ – ahulpke Jun 19 '17 at 5:03
  • $\begingroup$ @ahulpke - Many thanks - I didn't accept my own answer precisely because I felt it could be improved with feedback. I've edited both it and the original question: is there anything I should still change? $\endgroup$ – NietzscheanAI Jun 19 '17 at 6:42
  • $\begingroup$ With your edit it is clear what you want. Be aware that Dixon's algorithm will give you some (potentially horrendous) representation over a number field, while (if you go through the combinatorial definitions, which alas GAP does not implement) you could get nicer homomorphisms. $\endgroup$ – ahulpke Jun 19 '17 at 9:01
  • $\begingroup$ @ahulpke - thanks for the additional info. Would I be better off trying to work via 'Young's Orthogonal Representations'? $\endgroup$ – NietzscheanAI Jun 19 '17 at 9:05
  • $\begingroup$ Yes, but that might be overkill. If you work in bounded degree the easiest might be to take the permutation representation (factor out the all-1 vector) and then check with characters which tensor products/reductions will give you all representations. $\endgroup$ – ahulpke Jun 19 '17 at 10:24

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.