Decompose representations of finite groups into irreducibles

Version 1.1.0

Released 2020-02-15

This project is maintained by Kaashif Hymabaccus, Dmitrii Pasechnik

The main function of this package is to compute the decomposition of a representation ρ, of a finite group G over the complex numbers into irreducibles, as well as the corresponding decomposition of the centraliser of R.

While methods for doing this were well known before this package was written (cf. Serre’s book “Linear Representations of Finite Groups”), there were no open-source computer programs that implemented these methods, nor were details on how to achieve good performance of such an implementation published.

This package is useful in, for example, semidefinite programming and optimisation/feasibility problems involving coding theory, graph theory, algebraic geometry, combinatorics and more (see https://arxiv.org/abs/1007.2905 for more examples of possible applications). Specifically, it allows to achieve substantial reductions in the dimension of these problems; potentially known results, e.g. on upper bounds on sizes of nonlinear codes, could be improved with the functions implemented in this package.

This package was written as part of my (Kaashif Hymabaccus’s) Master’s degree at the University of Oxford, supervised by Dmitrii Pasechnik.

First, install GAP following the instructions
here. Then, create a
directory `~/.gap/pkg`

, which will contain your local packages and
clone this into it. Commands to run:

```
$ mkdir -p ~/.gap/pkg
$ cd ~/.gap/pkg
$ git clone https://github.com/gap-packages/RepnDecomp.git
```

Make sure that, when you installed GAP, you installed all of the packages! Our package uses GRAPE and IO for some functions.

Now, you can run GAP however you like, load the package and use the functions provided:

```
$ gap
<some output>
gap> LoadPackage("RepnDecomp");
───────────────────────────────────────────────────────────────────────────────
Loading GRAPE 4.8.2 (GRaph Algorithms using PErmutation groups)
by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~lsoicher/).
Homepage: https://gap-packages.github.io/grape
Report issues at https://github.com/gap-packages/grape/issues
───────────────────────────────────────────────────────────────────────────────
───────────────────────────────────────────────────────────────────────────────
Loading RepnDecomp 0.1 (Decompose representations of finite groups into irreducibles)
by Kaashif Hymabaccus (https://kaashif.co.uk).
with contributions by:
Dmitrii Pasechnik.
Homepage: http://gitlab.com/kaashif/decomp/
───────────────────────────────────────────────────────────────────────────────
true
gap> A := IdentityMat(5);
[ [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ],
[ 0, 0, 0, 0, 1 ] ]
gap> B := LDLDecomposition(A);
rec( D := [ 1, 1, 1, 1, 1 ],
L := [ [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 1 ] ] )
```

Where `LDLDecomposition`

is a function provided by this package.

First, generate the tests from the documentation:

```
$ gap -q < makedoc.g
```

To run the tests, make sure you have all needed packages installed (GRAPE and also IO if you want to compute in parallel).

```
$ gap tst/testall.g
```

This will run all tests and (hopefully) pass. In order for the tests to be as useful as possible to me i.e. catch as many bugs as possible, there is a lot of randomness in them. This means that sometimes the tests pick a pathologically bad example to decompose which causes the tests to hang forever. The tests will be fixed to be more deterministic.

There’s a GAPDoc documentation book hosted
here. This
is generated from the source files and comments in the `lib/`

directory of this repo, so you can also look there for the same
information.

There are also some examples in the `examples`

directory, which are
embedded in the manual, but the most complete examples are in the
`old_tst`

directory. These are the old, poorly documented, but
essentially complete tests. They are being converted into nicer
looking tests that can be embedded into the manual, but this could
take some time.

This package has been submitted as a paper to the
Journal of Open Source Software, the paper
can be found at `paper.md`

.

Open a pull request or issue in this repository. You can also email me directly, I’ll be more likely to notice an email.