A matrix group G may be defined over any ring R for which Magma has a method for computing the inverse of a matrix. The methods used to compute structural information of matrix groups depend upon the coefficient ring R as well as whether G is finite or infinite. Until quite recently, our techniques for computing with matrix groups of large degree were limited. However, the Large Matrix Group project led by C. Leedham-Green and E. O'Brien has developed a computational model known as Composition Tree which makes it possible to compute with matrix groups over finite fields that are too large for a useful BSGS to be constructed. The current approaches for computing structural properties of matrix groups that exist within Magma include the following:
Matrix groups are usually defined by giving a set of generating matrices for the group. In addition to this, Magma provides a large number of constructions for standard matrix groups. Standard constructions include most families of finite groups of Lie type. Functions for constructing matrix groups from other groups include direct products, wreath products, and tensor wreath products.
Databases of matrix groups in Magma include:
Let G be a matrix group defined over some reasonable ring (field or Euclidean ring). Let M be the natural module for G. Then G has a natural action on elements and submodules of M and functions exist to to compute their orbits. For groups defined over GF(q) a number of special tools are provided for constructing or estimating (the length of) very large orbits.
Using the G-set machinery a G-action can be defined on a range of objects associated with M. However, at present the calculation of stabilisers is restricted to BSGS groups and the stabiliser request must be of a single object from some G-set. Working with the action of G on the cosets of a subgroup of G is supported.
The BSGS approach was extended to matrix groups by G. Butler and J. Cannon. The orbits here are the G-orbits obtained by the action of G on the vectors of the natural module associated with G. Given that suitable orbits can be found, a BSGS is constructed using similar algorithms to those employed in the permutation group case. Given a BSGS most of the algorithms used for the permutation group case can be carried across to matrix groups.
The matrix group BSGS method works well provided that the degree of the matrix group is not too large, that suitable orbits can be found, and that the group is not extremely large. Consequently, BSGS is the preferred method when applicable.
When BSGS is not applicable and the matrix group is defined over a finite field, the Composition Tree method can be used. However, there are many computations available under BSGS that are not yet available under Composition Tree.
Matrix groups present a challenge for computational group theorists since the base and strong generating set (BSGS) paradigm, which is the basis for permutation group computations, is restricted to those matrix groups having relatively small order and degree. A new paradigm, the composition tree (CT) method, developed specifically to overcome this problem, has only recently matured to the point where it can handle matrix groups beyond the limit of the BSGS method. The method applies to permutation groups and matrix groups over a finite field.
The CT is a binary tree whose vertices are sections of the group. The leaves of the tree will correspond to the composition factors of G. If the vertex labelled H is not a leaf then the left child of H will correspond to a normal subgroup N of H and the right child will correspond to the section H/N. The algorithm to construct a composition tree is extremely complex and it has only recently been made generally available in Magma. The CT datastructure includes the order of G and the composition factors of G; it also supports testing membership of matrices in G.
For CT groups, normal closure type algorithms exist for calculating the normal closure of a subgroup and the derived group. Various algorithms that work off the CT datastructure have been implemented for composition series, composition factors, chief series, chief factors, soluble radical, Fitting subgroup, centre, and Sylow subgroup.
The following CT group lifting type algorithms will work only if a permutation representation can be computed for G/L, where L is the soluble radical of G: centraliser, conjugacy of elements, normaliser, conjugacy of subgroups, conjugacy classes of elements, and maximal subgroups.
Consider a 40-dimensional integer matrix group of order 7,172,259,840. It takes Magma 1081 seconds to compute the lattice of 6 normal subgroups of the group.
Unlike the BSGS datastructure, the CT scheme is still under development. For example, when constructing a subgroup of a CT group it does not come equipped with a compatible CT structure (or any CT structure unless the user asks for it). The BSGS scheme in Magma automatically creates a BSGS for any subgroup in such a way that subgroups and homomorphisms can seamlessly pass between subgroup and group.