The basic facilities provided by Magma for computing with matrix groups over finite fields, described in earlier in this chapter, depend upon being able to construct a chain of stabilizers. However, there are many examples of groups of moderately small dimension where we cannot find a suitable chain and the question arises as to whether one can say anything useful at all about the group in those cases. The functions described in this section represent a first attempt in this direction. This is currently an area of intense research activity, and further facilities can be expected in the near future. The code for the operations in this section has been written by Derek F. Holt, C.R. Leedham-Green, E.A. O'Brien & Sarah Rees, in the form of Magma packages.
According to a theorem of Aschbacher, (M. Aschbacher, (On the maximal subgroups of the finite classical groups, Invent. Math. 76 (1984) 469-514.)), a matrix group G acting on the finite dimensional KG-module V over a finite field K satisfies at least one of the following conditions (which we have simplified slightly for brevity):
Groups which acts irreducibly but not absolutely irreducibly on V fall theoretically into Category (ii), and furthermore act linearly over an extension field of K. In fact, absolute irreducibility can be tested using the built-in Magma functions and, by redefining their field to be an extension field L of K and reducing, they can be rewritten as absolutely irreducible groups of smaller dimension, but over L instead of K. We can therefore concentrate on absolutely irreducible matrix groups.
In this chapter, we restrict our attention to Categories (ii)--(vi). (Theoretical details may be found in two papers by Holt, Leedham-Green, O'Brien, and Rees (Derek F. Holt, C.R. Leedham-Green, E.A. O'Brien & Sarah Rees (1996), "Testing primitivity for matrix groups", J. Algebra 184; Derek F. Holt, C.R. Leedham-Green, E.A. O'Brien & Sarah Rees (1996), "Computing decompositions for modules with respect to a normal subgroup", J. Algebra, 184.).) These all involve a decomposition of G with respect to a normal subgroup N (which may sometimes be trivial or scalar). In (ii), N is the subgroup of G acting linearly over the extension field irreducibly on V. In (iii), N is the subgroup which fixes each of the subspaces in the imprimitive decomposition of V. In (iv), it is the subgroup acting as scalar matrices on one of the factors in the tensor-product decomposition. In (v), N is already described, and in (vi), it is the subgroup fixing each of the factors in the symmetric tensor-product decomposition (so N itself falls in Category (iv)).
Although N may be trivial, if any one of these decompositions can be found explicitly, then we will have an explicit representation of G/N which should be easier to compute with than that of G itself, and so we have achieved a partial reduction of the original problem of analysing G to one or more simpler problems. For example, in Category (iii), G/N will be given as a permutation group on the subspaces in the imprimitive decomposition of V.
Currently, there are essentially two major functions available for recognising
groups in these categories. They both start by checking that the group acts
absolutely irreducibly on V, and exit if it does not.
The first function, Smash() searches for
a decomposition of G of types (ii)--(vi) with respect to the normal
closure N of a specified subgroup H of G. It will always find such a
decomposition if it exists, and also provide an explicit representation of
the group G/N. Of course, the disadvantage is that the subgroup H needs
to be provided by the user. The second function, Explore(),
using only G as input, searches for a decomposition of type (ii) or (iii).
It is guaranteed to find such a decomposition if it exists although, if
more than one such decomposition exists, it is not possible to predict
(or even to influence) which one will be found. This function usually runs
reasonably fast, but occasionally it needs to carry out very lengthy searches,
and can be quite slow. Two additional functions,
IsSemiLinear () and IsPrimitive (),
take as input G, and return a boolean
or "unknown" according to the decision each reaches.
In each case, the MatGpTup for G is returned
as the second argument.
Matrix Group Tuples
The functions in this chapter require fast access to various items of data
associated with the matrix group G under investigation. The most important of
these are G itself, its generators, the underlying KG-module V and
its dimension, and the field K. They also need to remember properties of
G that have already been calculated. These data items are all stored in
a single Magma object known as a MatGpTup.
Most of the functions and procedures take a MatGpTup as argument,
and may modify it. (The chief exceptions are Explore(),
IsSemiLinear (), and IsPrimitive () which operate
directly on G, and return the associated MatGpTup.)
The functions described here create MatGpTup
and access its components.
MakeMatgpTup(~MGT,X) : SetCartElt, GrpMat ->
Construct the MatGpTup MGT from X. Here, X can be any one of:
- a matrix group G over a finite field;
- a sequence of matrices generating such a group;
- a KG-module over a finite field.
The first few of these functions return the fundamental data items used
to define the MatGpTup. The remainder return information on the
results of computations that have been carried out. They return the string
"unknown" if these computations have not yet taken place.
In the following descriptions, MGT will always be a MatGpTup
associated with the matrix group G acting on KG-module V.
GroupTup(MGT) : SetCartElt -> GrpMat
Return the matrix group G of MGT.
Return the sequence of matrices that generate G.
Return the field K.
Return the dimension of V.
Return V.
Returns "true", "false" or "unknown" according to the current state of knowledge of the imprimitivity of G.
If G is known to be imprimitive, then a tuple T is returned, which contains information on the imprimitive action found. The three components of T are:If G is not known to be imprimitive, then the string "unknown" is returned.
- -- the number of blocks;
- -- a basis for a block, given as a sequence of vectors;
- -- a sequence of permutations (in image form) giving the action of the generators of G on the blocks.
Returns "true", "false" or "unknown" according to the current state of knowledge of the semilinearity of G.
If G is known to be semilinear, then a tuple T is returned, which contains information on the semilinear action found. The three components of T are:While this information is perhaps not returned in the most convenient form possible, it does enable the user to construct the normal subgroup N of G which acts linearly over the extension field of K (this is precisely the centraliser of C in G), together with the quotient group G/N, which is cyclic of order dividing e.
- -- the degree e of the extension field of K over which G is semilinear;
- -- a matrix C that centralises the normal subgroup of G which acts linearly over the extension field;
- -- a sequence of positive integers, one for each generator of G. The positive integer i for the generator g is the least one such that g^(-1)Cg = C^i.
If G is not known to be semilinear, then the string "unknown" is returned.
Returns "true", "false" or "unknown" according to the current state of knowledge of whether G preserves a nontrivial tensor product decomposition of V.
If G is known to preserve a tensor product decomposition of V, then a tuple T is returned, which contains information on this decomposition. The three components of T are:If G is not known to preserve a tensor product decomposition, then the string "unknown" is returned.
- -- a basis of V, given as a square matrix in the appropriate matrix algebra, that exhibits the tensor product decomposition;
- -- a MatGpTup for the action of G on the first component of the decomposition;
- -- a MatGpTup for the action of G on the second component of the decomposition.
Returns "true", "false" or "unknown" according to the current state of knowledge of whether G normalises an extra-special p-group or 2-group of symplectic type.
If G is known to normalise a group N which is an extraspecial p-group or 2-group of symplectic type acting absolutely irreducibly on V, then a tuple T is returned, which contains information on N. The four components of T are:If G is not known to normalise such an N, then the string "unknown" is returned.
- -- integers p and r, where N has order p^(2r + 1), or p^(2r + 2) with p=2, and the degree of G is p^r;
- -- a sequence of elements of G which generate N;
- -- a sequence of generators for the action of G on N/Z(N) by conjugation, given as matrices of dimension 2r over GF(p).
Returns "true", "false" or "unknown" according to the current state of knowledge of whether G preserves a nontrivial symmetric tensor product decomposition of V.
If G is known to preserve a symmetric tensor product decomposition of V, then a tuple T is returned, which contains information on this decomposition. The two components of T are:If G is not known to preserve a symmetric tensor product decomposition, then the string "unknown" is returned.
- -- a basis of V, given as a square matrix in the appropriate matrix algebra, that exhibits the tensor product decomposition;
- -- a sequence of permutations giving the action of the generators of G on the tensor factors of the decomposition.
Here, S must be a list of matrices in G. The parameter mode is a string, and it should normally be the empty string.Let N be the normal closure of S in G. This procedure starts by checking whether G acts absolutely irreducibly on V and exits immediately if it does not. It then tests to see whether G, with respect to N, has a decomposition corresponding to one of the categories (ii)--(vi) in the Aschbacher Theorem stated at the beginning of this chapter. More precisely, it tests for one of the following possibilities:
If mode has the value "partial", then decompositions of types (d) and (e) will not be sought, and the procedure will halt as soon as N is known to act absolutely irreducibly on V. Note that new matrices in N may be added to the list S during the course of the computation; however, there is no guarantee that S will actually generate its normal closure at the end.
- G acts semilinearly over an extension field L of K, and N acts linearly over L;
- G acts imprimitively on V and N fixes each block of imprimitivity;
- G preserves a tensor product decomposition U tensor W of V, where N acts as scalar matrices on U;
- N acts absolutely irreducibly on V and is an extra-special p-group for some prime p, or 2-group of symplectic type;
- G preserves a symmetric tensor product decomposition V = tensor ^mU of V for some m>1, where N acts absolutely irreducibly on V and fixes each of the m factors.
Smash is a procedure, and does not return a value. If a decomposition is found, then the last diagnostic to be printed will be a message to this effect. Instead, it stores details of any decomposition found in MGT itself. This information can be accessed using the functions described in the previous section. If a decomposition of a particular type has not been found, then the relevant function (such as ImprimitiveTup(MGT), for example) will return "unknown" rather than "false", because Smash() has only excluded such a decomposition with respect to N, and has not ruled it out altogether.
> G:=GL(4, 5); > MakeMatgpTup(~MGT, G); > S:=[G.1]; > Smash(~MGT, ~S, ""); At top of main loop, S has size 1 Dimension of <S>-module is 1 Translates of W are not modules At top of main loop, S has size 2 Dimension of <S>-module is 1 Translates of W are not modules At top of main loop, S has size 3 S acts absolutely irreducibly on the module [ ... output deleted ... ]Here no decomposition is found. So, for example, we get:
> print ImprimitiveTup(MGT); unknown > print SymTensorProdTup(MGT); unknown
> P:=GL(6,3); > g1:=P![0,1,0,0,0,0,-1,0,0,0,0,0, > 0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1]; > g2 := P![-1,0,0,0,1,0,0,-1,0,0,0,1, > -1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0]; > g3 := P![1,0,0,0,0,0,0,-1,0,0,0,0, > 0,0,1,0,0,0,0,0,0,-1,0,0,0,0,0,0,1,0,0,0,0,0,0,-1]; > gens := [g1,g2,g3]; > G := sub<P| gens >; > MakeMatgpTup(~MGT, G); > S:=[g1,g2]; > Smash(~MGT, ~S, ""); At top of main loop, S has size 2 <S> acts irreducibly Testing for a semilinear decomposition Found a semilinear decomposition Group embeds in GammaL( 3 , 3 ^ 2 ) > print SemiLinearTup(MGT); true > I:=SemiLinearInfoTup(MGT); > print I[1], I[2], I[3]; 2 [0 2 0 0 0 0] [1 0 0 0 0 0] [0 0 0 2 0 0] [0 0 1 0 0 0] [0 0 0 0 0 2] [0 0 0 0 1 0] [ 1, 1, 3 ]The degree of the extension L of K = GF(3) over which G acts semilinearly is I[1] = 2. The matrix I[2] centralises the subgroup acting linearly over L = GF(9), and together with the scalar matrices generates (as an algebra) the field L. From the list I[3], we see that the first two generators act linearly over L, but the third generator acts as the field automorphism of L which maps the matrix I[2] to its third power.
> MG:=GL(4,7);
> PG:=Sym(3);
> G:=WreathProduct(MG,PG);
> MakeMatgpTup(~MGT,G);
> gens:=MatricesTup(MGT);
> S:=[gens[1],gens[2]];
> Smash(~MGT,~S,"");
At top of main loop, S has size 2
Dimension of <S>-module is 4
Module is decomposed as a sum of 3 irreducibles of dimension 4
The number of blocks is 3
> print ImprimitiveTup(MGT);
true
> B:=BlockSystemTup(MGT);
> print B[1];
3
> print B[3];
[
[ 1, 2, 3 ],
[ 1, 2, 3 ],
[ 2, 3, 1 ],
[ 2, 1, 3 ]
]
Note that B[1] is the number of blocks,
and B[3] is a list of the generators of G in their permutation
action on the blocks. These are listed in image form.
> F:=GF(5);
> MG1:=GL(5,F); MG2:=GL(3,F); P:=GL(15,F);
> A1:=MatrixAlgebra(F,5); A2:=MatrixAlgebra(F,3);
> g1:=A1!MG1.1; g2:=A1!MG1.2; g3:=A1!Identity(MG1);
> h1:=A2!MG2.1; h2:=A2!MG2.2; h3:=A2!Identity(MG2);
> w:=TensorProduct(g1,h3);
> x:=TensorProduct(g2,h3);
> y:=TensorProduct(g3,h1);
> z:=TensorProduct(g3,h2);
> gens := [ P!w,P!x,P!y,P!z ];
> G:=sub< P | gens >;
> MakeMatgpTup(~MGT, G );
> S:=[gens[1],gens[2]];
> Smash(~MGT,~S,"");
At top of main loop, S has size 2
Dimension of <S>-module is 5
Module is decomposed as a sum of 3 irreducibles of dimension 5
Testing for a tensor product decomposition
Module is a tensor product of modules of dimensions 3 and 5
> print TensorProdTup(MGT);
true
> I:=TensorProdInfoTup(MGT);
> MGT1:=I[2]; MGT2:=I[3];
>print DimTup(I[2]), DimTup(I[3]);
3 5
> print MatricesTup(I[2]);
[
[1 0 0]
[0 1 0]
[0 0 1],
[1 0 0]
[0 1 0]
[0 0 1],
[1 0 0]
[2 3 0]
[3 0 3],
[0 1 0]
[0 0 1]
[1 0 4]
]
Note that I[2] and I[3] are MatGpTups
for matrix groups of dimensions 2 and 3. Of course, this
example is artificial, since all we have done is to reconstruct the
original matrix groups MG1 and MG2 that were used to construct G.
> P:=GL(4,5);
> g1:=P![ 1,0,0,0,0,4,0,0,2,0,2,3,3,0,4,3];
> g2:=P![ 4,0,0,1,2,4,4,0,1,0,1,2,0,0,0,1];
> g3:=P![ 4,0,1,1,0,1,0,0,0,1,3,4,0,4,3,2];
> g4:=P![ 2,0,4,3,4,4,2,4,0,1,3,4,4,2,0,1];
> g5:=P![ 1,1,3,4,0,0,3,4,2,0,0,4,3,1,3,4];
> g6:=P![ 2,0,0,0,0,2,0,0,0,0,2,0,0,0,0,2];
> gens := [g1,g2,g3,g4,g5,g6];
> G := sub < P | gens >;
> MakeMatgpTup(~MGT,gens );
> S:=[g4];
> Smash(~MGT,~S,"");
[ ... output deleted ... ]
S acts absolutely irreducibly on the module
Testing to see if the group normalises an extraspecial group
Group normalises symplectic-type subgroup of order 2 ^ 6
> print ExtraSpecialTup(MGT);
true
> I:=ExtraSpecialInfoTup(MGT);
> print I[3];
[
[2 0 4 3]
[4 4 2 4]
[0 1 3 4]
[4 2 0 1],
[1 1 3 4]
[0 0 1 1]
[0 0 4 0]
[0 1 1 0],
[4 0 0 1]
[0 4 0 2]
[0 2 1 3]
[0 0 0 1],
[3 0 0 2]
[3 2 0 1]
[2 1 3 4]
[0 0 0 2]
]
Note that I[3] contains a list of matrices giving the
symplectic action of the generators of G on N/Z(N).
> MG:=GL(3,2); PG:=Sym(3); > G:=TensorProduct(MG,PG); > MakeMatgpTup(~MGT,G); > gens:=MatricesTup(MGT); > S:=[gens[1]]; > Smash(~MGT,~S,""); [ ... output deleted ... ] Testing for a tensor product decomposition Module is a tensor product of modules of dimensions 3 and 3 Found a tensor power decomposition Module is 3 -th power of a 3 -dimensional module 1 -th generator acts as permutation Id($) on factors 2 -th generator acts as permutation Id($) on factors 3 -th generator acts as permutation (1, 2, 3) on factors 4 -th generator acts as permutation (1, 2) on factors > print SymTensorProdTup(MGT); true > I:=SymTensorProdInfoTup(MGT);As usual, I contains information on the decomposition; for example I[2] contains the action of the generators of G on the blocks, which was already printed out at the end of the diagnostics.
This function starts by checking whether G acts absolutely irreducibly on V and exits, with a message, if it does not, returning false as its first value. Otherwise, it tests G for semilinearity and returns a boolean as its first value. The MatGpTup MGT defined from G is returned as the second value.
This procedure starts by checking whether G acts absolutely irreducibly on V and exits immediately, with a message, if it does not and returns true. Otherwise, it tests G for semilinearity. If it finds that G is semilinear, it exits with a message, and returns as its first value "unknown". Otherwise, it decides if the group is primitive and returns a boolean as its value. The MatGpTup MGT defined from G is returned as the second value.
This procedure starts by checking whether G acts absolutely irreducibly on V and exits immediately, with a message, if it does not, returning true as first value. It then tests G for semilinearity and imprimitivity. The first value returned is true if it finds a decomposition of one or other of these two types, and otherwise it is the string "unknown". The MatGpTup MGT defined from G is returned as the second value. The decompositions found can be identified by accessing the components of MGT. If G happens to be both semilinear and imprimitive, or if it has two distinct imprimitive actions, then it is not possible to predict or to influence which decomposition will be found by Explore.
> P:=GL(6,3); > g1:=P![0,1,0,0,0,0,-1,0,0,0,0,0, > 0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1]; > g2 := P![-1,0,0,0,1,0,0,-1,0,0,0,1, > -1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0]; > G:=sub<P|g1,g2>; > Status, MGT := Explore(G);Dimension = 6 F is Finite field of size 3
First, check for (absolute) irreducibility and semilinearity --------------------------------------------------------------
Module is not absolutely irreducible > print Status; true
> P:=GL(6,3); > g1:=P![0,1,0,0,0,0,-1,0,0,0,0,0, > 0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1]; > g2 := P![-1,0,0,0,1,0,0,-1,0,0,0,1, > -1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0]; > g3 := P![1,0,0,0,0,0,0,-1,0,0,0,0, > 0,0,1,0,0,0,0,0,0,-1,0,0,0,0,0,0,1,0,0,0,0,0,0,-1]; > G := sub<P| g1,g2,g3 >; > Status, MGT := Explore(G);Dimension = 6 F is Finite field of size 3
First, check for (absolute) irreducibility and semilinearity --------------------------------------------------------------
At top of main loop, S has size 3 Dimension of <S>-module is 2 Translates of W are not modules At top of main loop, S has size 4 <S> acts irreducibly Testing for a semilinear decomposition Found a semilinear decomposition Group embeds in GammaL( 3 , 3 ^ 2 ) Module is semilinear > print Status; true > print SemiLinearTup(MGT); true
> P:=GL(6,3); > g1:=P![0,1,0,0,0,0,-1,0,0,0,0,0, > 0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1]; > g2 := P![-1,0,0,0,1,0,0,-1,0,0,0,1, > -1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0]; > g3 := P![1,0,0,0,0,0,0,-1,0,0,0,0, > 0,0,1,0,0,0,0,0,0,-1,0,0,0,0,0,0,1,0,0,0,0,0,0,-1]; > G := sub<P| g1,g2,g3 >; > Status, MGT := Explore(G);Dimension = 6 F is Finite field of size 3^2
First, check for (absolute) irreducibility and semilinearity --------------------------------------------------------------
At top of main loop, S has size 3 Dimension of <S>-module is 1 Translates of W are not modules At top of main loop, S has size 4 Dimension of <S>-module is 3 Module is decomposed as a sum of 2 irreducibles of dimension 3 The number of blocks is 2 Matrix group is imprimitive > print Status; true > print ImprimitiveTup(MGT); true
> G:=GL(5,4); > Status, MGT := Explore(G);Notice that, after the run, we can definitively conclude that G is neither imprimitive nor semilinear. [Next] [Prev] [_____] [Left] [Up] [Index] [Root]Dimension = 5 F is Finite field of size 2^2
First, check for (absolute) irreducibility and semilinearity --------------------------------------------------------------
At top of main loop, S has size 2 Dimension of <S>-module is 1 Translates of W are not modules At top of main loop, S has size 3 Dimension of <S>-module is 1 Translates of W are not modules At top of main loop, S has size 4 S acts absolutely irreducibly on the module
Group is (absolutely) irreducible and is not semilinear
Secondly, check for primitivity ---------------------------------
Element has order 126
Group is primitive > print SemiLinearTup(MGT); false > print ImprimitiveTup(MGT); false