The Matrix Group Recognition Project

An international research project within computational group theory. The aim is to produce efficient algorithms for solving problems with matrix groups over finite fields, as well as making efficient implementations of these algorithms. The primary computer algebra system used is Magma, but GAP is also used.

The project dates back to the early 1990's, and a major goal has been to produce an algorithm that computes a composition tree of a matrix group, given by a set of generators. From a composition tree, one can readily construct a composition series of the group, as well as homomorphisms to the composition factors. This provides basic structural information about the group, and also tools for further computational tasks.

The approach for finding a composition tree is to use a divide-and-conquer strategy, by constructing a homomorphism into another group, and recursively finding a composition tree of the image and the kernel of the homomorphism. To construct homomorphisms, one uses Aschbacher's classification of the subgroups of the general linear group into 9 categories. This has led to a series of papers that present algorithms for deciding if a given matrix group lies in a specified Aschbacher category, and for constructing the corresponding homomorphism.

The base cases of the recursion are groups without proper normal subgroups, the finite simple groups. Problems which arise in the base cases include constructive membership testing and constructive recognition. This has led to a series of papers that present algorithms for these problems in various classes of the finite simple groups.

The composition tree algorithm is probabilistic of the type known as one-sided Monte Carlo. This means that there is a non-zero probability that the constructed composition tree is incorrect, which in this case means that it only is a composition tree for a proper subgroup. To determine if this is the case, one can construct a presentation of the group recursively, using presentations of the simple groups in the base cases, and then verify that the group satisfies the presentation. In order for this to be an efficient algorithm, the presentations of the simple groups have to be short presentations. This has led to a series of papers that present short presentations for various classes of the finite simple groups.

More detailed information about the project up to the year 2005 can be found in this survey.


Here is a list of published papers that could be considered a part of the project, with pointers to MathSciNet. Also pointers to the papers on the web, if available.

Ongoing work


Lots of code that have been produced is already included in the standard Magma package distribution.
Main Magma package for computing composition trees: tar.bz2, tar.gz, zip.
Last updated 2008-06-10