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.

Articles

• The computational matrix group project
• Towards effective algorithms for linear groups, PDF
• Constructive recognition of PSL(2,q), PDF
• Writing projective representations over subfields, PDF
• Finding the characteristic of a group of Lie type, PDF
• Constructive recognition of SL(3,q), PDF
• Recognising tensor-induced matrix groups, PDF
• Recognising tensor products of matrix groups, PDF
• Computing matrix group decompositions with respect to a normal subgroup, PDF
• Testing matrix groups for primitivity, PDF
• Selecting base points for the Schreier-Sims algorithm for matrix groups, PDF
• Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules, DOI
• A black-box group algorithm for recognizing finite symmetric and alternating groups, DOI
• Fast recognition of classical groups over large fields
• A constructive recognition algorithm for the special linear group, PDF
• A non-constructive recognition algorithm for the special linear and other classical groups, PDF
• Calculating the order of an invertible matrix, PDF
• Complexity and computation in matrix groups
• A recognition algorithm for non-generic classical groups over finite fields
• A recognition algorithm for classical groups over finite fields, DOI
• Implementing a recognition algorithm for classical groups
• Computation with matrix groups over finite fields
• A recognition algorithm for special linear groups, DOI
• A reduction algorithm for matrix groups with an extraspecial normal subgroup, PDF
• Constructive recognition of normalizers of small extra-special matrix groups, DOI
• Black-box recognition of finite simple groups of Lie type by statistics of element orders, PDF
• Computing with matrix groups
• A data structure for a uniform approach to computations with finite groups, PDF
• Fast constructive recognition of a black box group isomorphic to S_n or A_n using Goldbach's conjecture, DOI
• Constructive recognition of classical groups in their natural representation, PDF
• Fast constructive recognition of black box orthogonal groups, PDF
• Fast constructive recognition of black box unitary groups, PDF
• On constructive recognition of a black box PSL(d, q), PDF
• A constructive recognition algorithm for the matrix group Omega(d, q), PDF
• Testing matrix groups for irreducibility, PS
• Recognising the Suzuki groups in their natural representations, arXiv
• Simple groups in computational group theory, PDF
• Short presentations for finite groups, PDF
• An implementation of the Neumann-Praeger algorithm for the recognition of special linear groups, PS
• Black box classical groups, PDF
• Variants of product replacement, PDF
• Generating random elements of a finite group, PDF
• Writing representations over minimal fields, DOI
• On the maximal subgroups of finite classical groups, DOI
• Small degree representations of finite Chevalley groups in defining characteristic, PDF
• Matrix generators for the Ree groups 2G2(q), PDF

Ongoing work

• Composition tree, new version
• Chief tree
• Exceptional groups
• Classical groups natural representation, even characteristic
• Classical groups, arbitrary representation
• Short presentations

Software