Computing structural information for a matrix group G requires,
in most cases, a representation of the set of elements of G. Magma
represents this set by means of a base and strong generating set,
or BSGS for G. Suppose the group G has the natural module M. A
base B for G is a sequence of distinct elements and submodules
of M with the property that the identity is the only element of G that
fixes B pointwise. A base B of length n determines a sequence of
subgroups G^((i)), 0 <= i <= n, where G^((i)) is the
stabilizer of the first i - 1 points of B. Given a base B for G,
a subset S of G is said to be a strong generating set for G
if G^((i)) = S intersect G^((i)), for i = 1, ..., n.
Construction of a Base and Strong Generating Set
BSGS(G) : GrpMat ->
The general procedure for constructing a base and strong generating set for the matrix group G. This version uses the default algorithm choices.
Run: RngIntElt Default: 40
Construct a probable base and strong generating set for the group G. The strong generators are constructed from a set of randomly chosen elements of G. The expectation is that if sufficient random elements are taken then, upon termination, the algorithm will have produced a BSGS for G. If the attribute Order is defined for G, the random Schreier will continue until a BSGS defining a group of the indicated order is obtained. In such circumstances this method is the fastest method of constructing a base and strong generating set for G. This is particularly so for groups of large degree. If nothing is known about G, the random Schreier algorithm provides a cheap way of obtaining lower bounds on the group's order and, in the case of a matrix group, on its degree of transitivity. This parameter has one associated parameter Run, which takes a positive integer value. If the value of Run is n, then the algorithm terminates after n consecutive random elements are found to lie in the set defined by the current BSGS (default 40). This will happen even if the Order attribute is defined for G. It should be emphasized that unpredictable results may arise if the programmer uses the base and strong generators produced by this algorithm, when in fact, it does not constitute a BSGS for G.
Random: BoolElt Default: true
Construct a BSGS for G using the Todd-Coxeter Schreier algorithm. If the parameter Random is defined true, the random Schreier algorithm is first applied to create a probable BSGS.
Given a matrix group G for which a probable BSGS is stored, verify the correctness of the BSGS. If it is not complete, proceed to complete it. The Todd-Coxeter Schreier method is used.
Random: BoolElt Default: true
Max: RngIntElt Default: 100
Run: RngIntElt Default: 20
Construct a presentation for the matrix group G on a set of strong generators and return the presentation in the form of a finitely presented group F that is isomorphic to G. In Magma, the Todd-Coxeter Schreier algorithm is used to construct the presentation. If strong generators are not already known for G, they will be constructed. If strong generators have to be constructed, the parameter Random with its associated parameters Max and Run may be used to apply the Random Schreier algorithm to construct a probable BSGS before commencing the construction of the presentation. In the case in which strong generators are already known for G, the presentation will be on these strong generators. The group homomorphism f: F -> G, defining G as a matrix representation of F, is also returned.
Define the order of the matrix group G to be the integer n (factored integer Q).
If the boolean variable b is true, the existing pseudo strong generators for the matrix group G (possibly created by RandomSchreier) are to be taken as correct.
True iff the order of the group G is known. In that case, the order is also returned as the second value of the function.
True iff the matrix group G has a verified set of strong generators.
A base for the matrix group G. The base is returned as a sequence of points of Omega. If a base is not known, one will be constructed.
The i-th base point for the matrix group G. A base and strong generating set must be known for G.
The basic orbit at level i as defined by the current base for the matrix group G. This function assumes that a BSGS is known for G.
The length of the basic orbit at level i as defined by the current base for the matrix group G. This function assumes that a BSGS is known for G.
The lengths of the basic orbits as defined by the current base for the matrix group G. This function assumes that a BSGS is known for G. The lengths are returned as a sequence of integers.
Given a matrix group G for which a base and strong generating set are known, and an integer i, where 1 <= i <= k with k the length of the base, return the subgroup of G which fixes the first i - 1 points of the base.
Given a matrix group G, return the stabilizer chain defined by the base as a sequence of subgroups of G. If a BSGS is not already known for G, it will be created.
The number of elements in the current strong generating set for G.
A set of strong generators for the matrix group G. If they are not currently available, they will be computed.
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.
According to a theorem of Aschbacher, (M. Aschbacher, ), 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). 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 in this section 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.
Here no decomposition is found. So, for example, we get:
> 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 ... ]
> print ImprimitiveTup(MGT); unknown
> print SymTensorProdTup(MGT); unknown
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.
> 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 ]
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.
> 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 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.
> 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[3] contains a list of matrices giving the symplectic action of the generators of G on N/Z(N).
> 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] ]
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.
> 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);
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
Notice that, after the run, we can definitively conclude that G is neither imprimitive nor semilinear. [Next] [Prev] [_____] [Left] [Up] [Index] [Root]
> G:=GL(5,4);
> Status, MGT := Explore(G);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