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.
An on-going international research program seeks to develop algorithms to explore the structure of such groups. The program adopts a different approach and relies on the following theorem of Aschbacher (1984). [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 in Category (i) can be recognised easily by means of the Meataxe functions described in the chapter on R-modules.
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.
The Magma package currently provides access to functions which seek to decide membership of categories (ii)-(vii). It was prepared by E.A. O'Brien. It combines, updates, and replaces material originally developed by Holt, Leedham-Green, O'Brien, and Rees for categories (ii) and (iii).
Theoretical details of the algorithms used may be found in papers by
Holt, Leedham-Green, O'Brien, & Rees (1996a, 1996b) [Derek
F. Holt, C.R. Leedham-Green, E.A. O'Brien & Sarah Rees (1996a),
"Testing matrix groups for primitivity", J. Algebra 184,
795--817;
Derek F. Holt, C.R. Leedham-Green, E.A. O'Brien & Sarah Rees (1996b),
"Computing decompositions for modules with respect to
a normal subgroup", J. Algebra, 184, 818--838.];
Leedham-Green & O'Brien
(1997a, 1997b) [C.R. Leedham-Green
& E.A. O'Brien (1997a),
"Tensor Products are Projective Geometries", J. Algebra 189,
514--528; C.R. Leedham-Green & E.A. O'Brien (1997b),
`Recognising tensor products of matrix groups",
Internat. J. Algebra Comput. 7, 541--559.];
and Glasby & Howlett (1997)footnote{dag dag dag}
{S.P. Glasby and R.B. Howlett,
"Writing representations over minimal fields" Comm.
Algebra 25 (1997), no. 6, 1703--1711.}.
Primitivity Testing
Let G be a subgroup of GL(d, q) and assume that
G acts irreducibly on the underlying vector space V.
Then G acts imprimitively on V if there is a non-trivial
direct sum decomposition
V = V_1 direct-sum V_2 direct-sum ... direct-sum V_r
where V_1, ..., V_r are permuted by G.
In such a case, each block V_i has the same dimension
or size, and we have the block system {V_1, ..., V_r}.
If no such system exists, then G is primitive.
IsPrimitive(G) : GrpMat -> BoolElt
Return true if G is primitive, false if G is not primitive, or "unknown" if no decision can be reached.
If G is imprimitive, then a record B is returned, which contains information on the imprimitive action found. The three components of B are:
- B`NmrBlocks -- the number of blocks;
- B`Block -- a basis for a block, given as a sequence of vectors;
- B`Perms -- a sequence of permutations (in image form) giving the action of the generators of G on the blocks.
Return the group induced by the action of G on the system of imprimitivity.
> MG := GL (4, 7);
> PG := Sym (3);
> G := WreathProduct (MG, PG);
>
> IsPrimitive (G);
false
>
> /* block system */
> B := BlockSystem (G);
> B;
rec<recformat<NmrBlocks: RngIntElt, Block: SeqEnum, Perms:
SeqEnum, BlockSystem: BoolElt> | NmrBlocks := 3, Block := [
(0 0 0 0 0 0 0 0 1 0 0 0),
(0 0 0 0 0 0 0 0 0 1 0 0),
(0 0 0 0 0 0 0 0 0 0 1 0),
(0 0 0 0 0 0 0 0 0 0 0 1)
], Perms := [
[ 1, 2, 3 ],
[ 1, 2, 3 ],
[ 2, 3, 1 ],
[ 1, 3, 2 ]
], BlockSystem := true>
>
> /* permutation representation */
> P := BlocksImage (G);
> P;
Permutation group P acting on a set of cardinality 3
(1, 2, 3)
(2, 3)
Let G be a subgroup of GL(d, q) and assume that G acts absolutely irreducibly on the underlying vector space V. Assume that a normal subgroup N of G embeds in GL(d/e, q^e), for e>1, and a d x d matrix C acts as multiplication by a scalar lambda (a field generator of GF(q^e)) for that embedding.
We say that G acts as a semilinear group of automorphisms on
the d/e-dimensional
space if and only if, for each generator g of G, there is an integer
i = i(g) such that Cg = gC^(i), that is, g corresponds to the
field automorphism lambda -> lambda^(i).
If so, we have a map from G to the (cyclic) group
( Aut)(GF(q^e)), and C centralises the kernel of this map,
which thus lies in GL(d, q^e).
IsSemiLinear(G) : GrpMat -> BoolElt
Return true if G is semilinear, false if G is not semilinear, or "unknown" if no decision can be reached.
G is defined over K = GL(d, q). Return the degree e of the extension field of K over which G is semilinear.
Return the matrix C which centralises the normal subgroup of G which acts linearly over the extension field.
Return a sequence S of positive integers, one for each generator of G. The element S[i] is the least positive integer such that G.i^(-1) C G.i = C^(S[i]).
Return
- the normal subgroup N of G which is the kernel of the map from G to C_e; this subgroup acts linearly over the extension field of K and is precisely the centraliser of C in G;
- N rewritten as a subgroup of GL(d/e, q^e),
- a cyclic group E of order e which is isomorphic to G/N; and
- a sequence of images of the generators of G in E.
> 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 >;
>
> IsSemiLinear (G);
true
> DegreeOfFieldExtension (G);
2
> CentralisingMatrix (G);
[2 2 0 0 0 0]
[1 2 0 0 0 0]
[0 0 2 2 0 0]
[0 0 1 2 0 0]
[0 0 0 0 2 2]
[0 0 0 0 1 2]
> FrobeniusAutomorphisms (G);
[ 1, 1, 3 ]
> K, R, E, phi := WriteOverLargerField (G);
>
> /* kernel of homomorphism from G into E */
> K.1;
[0 1 0 0 0 0]
[2 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]
>
> /* now K rewritten as subgroup of GL(6/2, 3^2) */
> R;
MatrixGroup(3, GF(3^2))
Generators:
[ 1 0 0]
[ 0 1 0]
[ 0 0 $.1^6]
[ 0 2 0]
[ 0 0 2]
[ 1 0 2]
[ 1 0 0]
[ 0 1 0]
[ 0 0 $.1^2]
>
> /* E is cyclic group of order e */
>
> E;
Abelian Group isomorphic to Z/2
Defined on 1 generator
Relations:
2*E.1 = 0
>
> /* sequence of images of G.i in E */
> phi;
[ 0, 0, E.1 ]
Let G be a subgroup of GL(d, K), where K = GF(q),
and let V be the natural KG-module. We say that G preserves a
tensor decomposition of V as U tensor W if there is
an isomorphism of V onto U tensor W such that the
induced image of G in GL(U tensor W)
lies in GL(U) o GL(W).
IsTensor(G) : GrpMat -> BoolElt
Return true if G preserves a non-trivial tensor decomposition, false if G is does not preserve a tensor decomposition, or "unknown" if no decision can be reached.
Return the change-of-basis matrix which exhibits the tensor decomposition of G.
Return the tensor factors of G.
Return true iff the matrix X is composed of k x k blocks which differ only by scalars; if so, return also the tensor decomposition of X.
> P := GL (6, 3);
>
> g := P![ 0, 1, 1, 2, 1, 0, 2, 2, 1, 2, 1, 1, 1, 0, 2, 1, 2, 2, 1, 2, 2,
> 2, 2, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 2, 2 ];
>
> h := P![ 1, 0, 2, 1, 1, 2, 0, 0, 2, 0, 0, 2, 2, 0, 1, 0, 2, 1, 2, 1, 2,
> 2, 1, 1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 2, 1, 2 ];
>
> G := sub < P | g, h >;
> IsTensor (G);
true
> /* change-of-basis matrix */
> C := TensorBasis (G);
> /* if we conjugate G.1 by C, we obtain a visible Kronecker product */
> G.1^C;
[0 0 2 0 2 0]
[0 0 2 2 2 2]
[2 0 0 0 2 0]
[2 2 0 0 2 2]
[0 0 0 0 1 0]
[0 0 0 0 1 1]
>
> /* verify that G.1^C is a Kronecker product */
> IsProportional (G.1^C, 2);
true
<[2 0]
[2 2],
[0 1 1]
[1 0 1]
[0 0 2]>
>
> /* tensor factors */
> A := TensorFactors (G);
> A[1];
MatrixGroup(2, GF(3))
Generators:
[1 2]
[2 2]
[2 0]
[2 2]
> A[2];
MatrixGroup(3, GF(3))
Generators:
[0 1 0]
[1 2 1]
[1 2 0]
[0 1 1]
[1 0 1]
[0 0 2]
S is a sequence of elements in G. The normal closure N of S in G is constructed by this function which seeks to decide whether or not G, with respect to N, has a decomposition corresponding to one of the categories (ii)--(vi) in the Theorem of Aschbacher stated at the beginning of this section.In summary, it tests for one of the following possibilities:
If one of the listed decompositions is found, then the function reports the type found and returns true; if no decomposition is found with respect to N, then the function returns false. The answer provided by the function is conclusive for decompositions of types (ii)--(v), but a negative answer for (vi) is not necessarily conclusive.
- 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 extraspecial 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.
Each involves a decomposition of G with respect to the 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)).
If any one of these decompositions can be found, then we may be able to obtain an explicit representation of G/N and hence reduce the study of G to a smaller problem. For example, in Category (iii), G/N acts as a permutation group on the subspaces in the imprimitive decomposition of V. Currently only limited facilities are provided to construct G/N.
The access functions described in Sections Primitive, Semilinearity, and Tensor Products may be used to extract information about decompositions of type (ii), (iii) and (iv). We illustrate such decompositions below.
Here we record the functions to extract information about decompositions of type (v) and (vi).
> /* no decomposition found */
> G := GL(4, 5);
> SearchForDecomposition (G, [G.1]);
Smash: No decomposition found
false
>
> /* imprimitive decomposition */
> M := GL (4, 7);
> P := Sym (3);
> G := WreathProduct (M, P);
> SearchForDecomposition (G, [G.1, G.2]);
Smash: G is imprimitive
true
> IsPrimitive (G);
false
> BlockSystem (G);
rec<recformat<NmrBlocks: RngIntElt, Block: SeqEnum, Perms: SeqEnum,
BlockSystem:
BoolElt> | NmrBlocks := 3, Block := [
(1 0 0 0 0 0 0 0 0 0 0 0),
(0 1 0 0 0 0 0 0 0 0 0 0),
(0 0 1 0 0 0 0 0 0 0 0 0),
(0 0 0 1 0 0 0 0 0 0 0 0)
], Perms := [
[ 1, 2, 3 ],
[ 1, 2, 3 ],
[ 2, 3, 1 ],
[ 2, 1, 3 ]
], BlockSystem := true>
> BlocksImage (G);
Permutation group acting on a set of cardinality 3
(1, 2, 3)
(1, 2)
>
> /* semilinear decomposition */
> 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 >;
>
> SearchForDecomposition (G, [g1]);
Smash: G is semilinear
true
> IsSemiLinear (G);
true
> DegreeOfFieldExtension (G);
2
> CentralisingMatrix (G);
[2 2 0 0 0 0]
[1 2 0 0 0 0]
[0 0 2 2 0 0]
[0 0 1 2 0 0]
[0 0 0 0 2 2]
[0 0 0 0 1 2]
> FrobeniusAutomorphisms (G);
[ 1, 1, 3 ]
>
> /* tensor product decomposition */
> F := GF(5);
> G := GL(5, F);
> H := GL(3, F);
> P := GL(15, F);
> A := MatrixAlgebra (F, 5);
> B := MatrixAlgebra (F, 3);
> g1 := A!G.1; g2 := A!G.2; g3 := A!Identity(G);
> h1 := B!H.1; h2 := B!H.2; h3 := B!Identity(H);
> w := TensorProduct (g1, h3);
> x := TensorProduct (g2, h3);
> y := TensorProduct (g3, h1);
> z := TensorProduct (g3, h2);
> G := sub < P | w, x, y, z>;
> SearchForDecomposition (G, [G.1, G.2]);
Smash: G is a tensor product
true
> IsTensor (G);
true
> TensorBasis (G);
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
[4 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 4 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 4 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 4 0 1]
[0 0 0 0 0 0 0 0 0 4 0 1 0 0 0]
[1 4 4 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 4 4 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 4 4 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 4 4]
[0 0 0 0 0 0 0 0 0 1 4 4 0 0 0]
Return true if G normalises an extraspecial p-group or 2-group of symplectic type, false if G is known not to normalise an extraspecial p-group or a 2-group of symplectic type, or "unknown".If SearchForDecomposition has not found a decomposition of this type, then IsExtraSpecialNormaliser simply returns "unknown".
Return sequence of integers, p and n, where the extraspecial subgroup N normalised by G has order p^(n).
Return the generators for N, the subgroup normalised by G.
> /* normaliser of an extraspecial group */ > F := GF(5); > P := GL(4,F); > 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]; > G := sub < P | g1, g2, g3, g4, g5, g6 >; > SearchForDecomposition (G, [G.4]); Smash: G is normaliser of extraspecial p-group true > > IsExtraSpecialNormaliser (G); true > ExtraSpecialParameters (G); <2, 5> > E := ExtraSpecialGroup (G); > #E; 32
Return true if G is known to preserve a non-trivial symmetric tensor product, false if G is known not to preserve a non-trivial symmetric tensor product, otherwise "unknown".If SearchForDecomposition has not found a decomposition of this type, then IsSymmetricTensor simply returns "unknown".
Return a basis of the underlying vector V of G that exhibits the tensor product decomposition.
Return the symmetric tensor factors when G preserves a symmetric tensor product decomposition.
Return a sequence of permutations giving the action of the generators of G on the tensor factors of the decomposition.
> /* symmetric tensor product */
> M := GL (3, GF(2));
> P := Sym (3);
> G := TensorWreathProduct (M, P);
> SearchForDecomposition (G, [G.1]);
Smash: G is symmetric tensor product
true
>
> IsSymmetricTensor(G);
true
> F := SymmetricTensorFactors (G);
> #F;
3
> F[1];
MatrixGroup(3, GF(2))
Generators:
[0 1 0]
[1 0 0]
[0 0 1]
[0 0 1]
[1 0 0]
[1 1 0],
> SymmetricTensorPermutations (G);
[ Id(P), Id(P), (1, 3, 2), (1, 3) ]
The algorithm implemented by these functions is due to Glasby &
Howlett (1997) [S.P. Glasby and R.B. Howlett,
"Writing representations over minimal fields", Comm.
Algebra 25 (1997), no. 6, 1703--1711.].
IsOverSmallerField(G) : GrpMat -> BoolElt, GrpMat
Decide whether or not an absolutely irreducible group G <= GL(d, K) has an equivalent representation over a subfield of K. If so, it returns true and the representation over the smallest possible subfield.
Decide whether or not an absolutely irreducible group G <= GL(d, K) has an equivalent representation over a proper subfield of K having degree d. If so, it returns true and the representation over this subfield.
> G := GL (2, GF (3, 2));
> H := GL (2, GF (3, 8));
> K := sub < H | G.1, G.2 >;
> K;
MatrixGroup(2, GF(3^8))
Generators:
[ $.1^820 0]
[ 0 1]
[ 2 1]
[ 2 0]
> flag, M := IsOverSmallerField (K);
> flag;
true
> M;
MatrixGroup(2, GF(3^2))
Generators:
[$.1^7 $.1^2]
[ 1 2]
[$.1^7 $.1^6]
[$.1^2 $.1^5]
> flag, M := IsOverSmallerField (K, 3);
> flag;
false
Given a group G of d x d matrices over a finite field E having degree e and a subfield F of E having degree f, write the matrices of G as de/f by de/f matrices over F and return the group and the isomorphism.
> G := GL(2, 4);
> H := WriteOverSmallerField(G, GF(2));
> H;
MatrixGroup(4, GF(2))
Generators:
[0 1 0 0]
[1 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 0 0]
[0 1 0 0]
> #H;
180
> #G;
180
[Next] [Prev] [_____] [Left] [Up] [Index] [Root]