RecogniseMatrixGroup( G )
RecogniseMatrixGroup attempts to recognise at least one of the
Aschbacher categories in which the matrix group G lies. It then
attempts to use features of this category to determine the order of G
and provide a membership test for G.
The algorithm is described in [13]. This implementation is experimental and limited in its application; its inclusion in the package at this time is designed primarily to illustrate the basic features of the approach.
Currently the function attempts to recognise groups that are reducible, imprimitive, tensor products or classical in their natural representation.
The function returns a record whose components store detailed information
about the decomposition of G that it finds. The record contents can be
viewed using DisplayMatRecord.
The record consists of layers of records which are the kernels at the various stages of the computation. Individual layers are accessed via the component .kernel. We number these layers 1 to n where layer 0 is G. The n-th layer is a p-group generated by lower uni-triangular matrices. Information about this p-group is stored in the component .pGroup. At the i-th layer (1 leq i leq n) we have a group generated by matrices with at most i-1 identity blocks down the diagonal, followed by a non-singular block. Below the blocks we have non-zero entries and above them we have zero entries. Call this group G_i and the group generated by the non-singular block on the diagonal T_i. In the i-th layer we have a component .quotient. If the module for T_i is irreducible, then .quotient is T_i. If the module for T_i is reducible, then it decomposes into an irreducible submodule and a quotient module. In this case .quotient is the restriction of T_i to the submodule.
The central part of RecogniseMatrixGroup is the recursive function
GoDownChain which takes as arguments a record and a list of matrices.
RecogniseMatrixGroup initialises this record and then calls
GoDownChain with the record and a list of the generators of G.
Assume we pass GoDownChain the i-th layer of our record and a list of
matrices (possibly empty) in the form described above.
If the i-th layer is the last, then we construct a power-commutator presentation for the group generated by the list of matrices.
Otherwise, we now check if we have already decomposed T_i. If not, we
split the module for T_i using IsIrreducible. We set .quotient to be
the trivial group of dimension that of the irreducible submodule, and we
store the basis-change matrix. We also initialise the next layer of our
record, which will correspond to the kernel of the homomorphism from
G_i to .quotient. Then we call GoDownChain with the layer and the
list of matrices we started with.
If we have a decomposition for T_i, then we apply the basis-change
stored in our record to the list of matrices and decide whether the new
matrices preserve the decomposition. If they do not, then we discard the
current decomposition of T_i and all the layers below the i-th, and
recall GoDownChain.
If the matrices preserve the decomposition, then we extract the blocks in
the matrices which correspond to .quotient. We decide if these blocks
lie in .quotient.
If the blocks lie in .quotient, then the next step is to construct
relations on .quotient which we will then evaluate on the generators of
G_i to put into the next layer. There are two approaches to
constructing relations on .quotient. Let F be the free group on the
number of generators of .quotient. We construct a permutation
representation on .quotient. The first approach is to take the image of
an element of .quotient in the permutation group and then pull it back
to the permutation group. The second approach is to take a random word in
F, map it into the permutation group and then pull the permutation back
into F. The relations from approach one are "generator relations" and
those from approach two are "random relations". If .quotient
contains SL, then we use special techniques.
If the list of matrices with which we called GoDownChain is empty, then
we construct random relations on .quotient, evaluate these in G_i to
get a new list of matrices and then call GoDownChain with this list and
the next layer of our record. We use parameters similar to those in the
Random Schreier-Sims algorithm to control how hard we work.
If the list of matrices is non-empty, then we take generator relations on
the list of blocks and evaluate these in G_i. This gives us a new list
of matrices and we call GoDownChain with the list and the next layer of
our record.
If, in evaluating the relations in G_i, we get a non-identity block, then we deduce that our permutation representation is not faithful. In this case, the next layer corresponds to the kernel of the action that provided the representation.
If these blocks do not lie in .quotient, then we have to enlarge it. We
then try to find out the Aschbacher category in which .quotient lies,
and its size. After applying these tests and computing the size we then
construct generator relations on the list of generators of .quotient
and put them into the kernel. We then call GoDownChain with our record
and an empty list of matrices.
We first test whether .quotient is a classical group in its natural
representation using RecogniseClassicalNP. If .quotient contains SL,
we use Constructively-Recognise-Classical to obtain both its size and
a membership test; if .quotient contains one of the other classical
groups, we simply report this. If .quotient contains a classical
group, we terminate the testing. If RecogniseClassicalNP returns
false, then we call RecogniseClassicalCLG. If .quotient contains
one of the classical groups, then we behave as before. If .quotient is
not a classical group, then we obtain a list of possibilities for
.quotient. This list may help to rule out certain Aschbacher
categories and will give pointers to the ones which we should investigate
further.
If .quotient might be imprimitive, then we test this using
IsPrimitive. If .quotient is imprimitive, then we obtain a
permutation representation for the action on the blocks and we store this
in .quotient. We set the size of .quotient to be the size of the
permutation group. If the action is not faithful, then we compute the
kernel of the action at the next layer and then we have the correct size
for .quotient. If .quotient is imprimitive, then the testing ends
here. If IsPrimitive returns unknown or true, then we store this in
.quotient. We then reprocess .quotient using RecogniseClassicalCLG.
If .quotient might be a tensor product, then we test this using
IsTensor. If .quotient is a tensor product, then we store the tensor
factors in .quotient. Currently, we do not exploit this conclusion . If
IsTensor returns unknown or false then we store this in
.quotient. We then reprocess .quotient using RecogniseClassicalCLG.
By default, we obtain the size of .quotient using
PermGroupRepresentation. We advise the user if the list returned by
RecogniseClassicalCLG suggests that the group contains an almost
simple group or an alternating group. PermGroupRepresentation
constructs a faithful permutation representation for .quotient and we
store this in .quotient.
We illustrate some of these features in the following example.
Additional examples can be found in matrix/reduce/examples.tex.
gap> # Construct the group SL(2, 3) x SP(4, 3)
gap> G1 := SL(2, 3);;
gap> G2 := SP(4, 3);;
gap> m1 := DiagonalMat( GF(3), G1.1, G2.1 );;
gap> m2 := DiagonalMat( GF(3), G1.2, G2.2 );;
gap> # Put something in the bottom left hand corner to give us a p-group
gap> m1[3][1] := Z(3)^0;;
gap> m2[5][2] := Z(3);;
gap> G := Group( [m1, m2], m1^0 );;
gap> # Apply RecogniseMatrixGroup to G
gap> x := RecogniseMatrixGroup( G );;
#I Input group has dimension 6 over GF(3)
#I Layer number 1: Type = "Unknown"
#I Size = 1, # of matrices = 2
#I Computing the next quotient
#I <new> acts non-trivially on the block of dim 6
#I Found a quotient of dim 2
#I Restarting after finding a decomposition
#I Layer number 1: Type = "Perm"
#I Size = 1, # of matrices = 2
#I Submodule is invariant under <new>
#I Enlarging quotient, old size = 1
#I Is quotient classical?
#I Dimension of group is <= 2, you must supply form
#I The quotient contains SL
#I New size = 24
#I Adding generator relations to the kernel
#I Layer number 2: Type = "Unknown"
#I Size = 1, # of matrices = 2
#I Computing the next quotient
#I <new> acts non-trivially on the block of dim 4
#I Found a quotient of dim 4
#I Restarting after finding a decomposition
#I Layer number 2: Type = "Perm"
#I Size = 1, # of matrices = 2
#I Submodule is invariant under <new>
#I Enlarging quotient, old size = 1
#I Is quotient classical?
#I The case is symplectic
#I This algorithm does not apply in this case.
#I The quotient contains SP
#W Applying Size to (matrix group) quotient
#I New size = 51840
#I Adding generator relations to the kernel
#I Restarting after enlarging the quotient
#I Layer number 2: Type = "Perm"
#I Size = 51840, # of matrices = 0
#I Using a permutation representation
#I Adding random relations at layer number 2
#I Adding a random relation at layer number 2
#I Layer number 3: Type = "PGroup"
#I Size = 1, # of matrices = 3
#I Reached the p-group case
#I New size = 27
#I Adding a random relation at layer number 2
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 27
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 2
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Kernel is finished, size = 340122240
#I Restarting after enlarging the quotient
#I Layer number 1: Type = "SL"
#I Size = 8162933760, # of matrices = 0
#I Using the SL recognition
#I Adding random relations at layer number 1
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Adding a random relation at layer number 1
#I Layer number 2: Type = "Perm"
#I Size = 340122240, # of matrices = 3
#I Submodule is invariant under <new>
#I Using a permutation representation
#I Adding generator relations to the kernel
#I Kernel p-group, old size = 6561
#I Kernel p-group, new size = 6561
#I Kernel is finished, size = 8162933760
gap> # Let us look at what we have found
gap> DisplayMatRecord( x );
#I Matrix group over field GF(3) of dimension 6 has size 8162933760
#I Number of layers is 3
gap> DisplayMatRecord( x, 1 );
#I Layer Number = 1
#I Type = SL
#I Dimension = 2
#I Size = 24
gap> # The module for G splits into an irreducible submodule of dimension
gap> # 2 and a quotient module of dimension 4. The restriction of G to
gap> # the submodule contains SL(2, 3). Call this group G1.
gap> DisplayMatRecord( x, 2 );
#I Layer Number = 2
#I Type = Perm
#I Dimension = 4
#I Size = 51840
gap> # We have now taken relations on G1 and evaluated them in G to get
gap> # a group H, which is the kernel of the homomorphism from G to G1.
gap> # The group generated by the last 4x4 block on the diagonal of the
gap> # matrices of H has an irreducible module and we have computed
gap> # a permutation representation on it. Call this group H1.
gap> DisplayMatRecord( x, 3 );
#I Layer Number = 3
#I Type = PGroup
#I Dimension = 6
#I Size = 6561
gap> # We have now taken relations on H1 and evaluated them in H to get the
gap> # kernel of the homomorphism from H to H1. This kernel consists of
gap> # lower uni-triangular matrices. It is a p-group of size 6561.
GAP 3.4.4