(d, q),
Omega = Omega^(d, q)
The basic facilities provided by Magma for computing with matrix groups over finite fields, as described 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 [Asc84].
A matrix group G acting on the finite dimensional K[G]-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 act 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 matrix package currently includes functions which seek to decide membership of categories (ii)-(viii). It was prepared by E.A. O'Brien. It replaces material developed by Holt, Leedham-Green, O'Brien, and Rees for categories (ii) and (iii). The classical forms and classical recognition code was prepared by Alice C. Niemeyer.
Let G be an absolutely irreducible subgroup of GL(d, q). The following functions compute symplectic, unitary and orthogonal forms of the underlying vector space V left invariant by the action of G.
A bilinear form is a bilinear function kappa from V x V -> F. It is G-invariant modulo scalars if for each g in G there is a mu_g in F such that kappa(vg, wg) = mu_g kappa(v, w) for all v, w in V.
Now suppose that a |-> bar(a) is an automorphism of F of order 2. A sesquilinear form is a biadditive function kappa from V x V -> F such that kappa( au, bv) = a bar(b) kappa(u, v) for all u, v in V and a, b in F. It is G-invariant modulo scalars if for each g in G there is a mu_g in F such that kappa(vg, w bar(g)) = mu_g kappa(v, w) for all v, w in V (where bar(g) denotes the matrix obtained from g by replacing each entry g_(ij) by bar(g_(ij))).
A quadratic form is a function chi : V -> F such that
A bilinear form is represented a matrix B such that g * B * (g)^(tr) = mu_g B for all g in G and is unique up to multiplication by an element of F. Assume F has an automorphism a |-> bar(a) of order 2; a sesquilinear form is a matrix B such that g * B * bar(g)^(tr) = mu_g B for all g in G and is unique up to multiplication by an element of F. A quadratic form is represented by an upper triangular matrix Q such that the matrix g * Q * g^(tr), normalized into an upper triangular matrix, equals mu_g Q.
Given as input a group G acting absolutely irreducibly on the underlying vector space V over the field F and dimension at least 3, ClassicalForms will try to find a classical form which is G-invariant modulo scalars or prove that no such form exists.The classical forms are: symplectic (non-degenerate, alternating bilinear), unitary (non-degenerate sesquilinear) or orthogonal (a symmetric bilinear form and a quadratic form).
The function ClassicalForms returns a record forms which contains the components formType, bilinearForm, sesquilinearForm, quadraticForm and scalars. Depending on the entry formType the record components are set to indicate:
- "unknown": it is not known whether G fixes a classical form.
- "linear": it is known that G does not fix a classical form modulo scalars.
- "symplectic": G fixes a symplectic form modulo scalars. The matrix of the form is stored in bilinearForm and the scalars for each generator of G are stored in scalars. In characteristic two this also implies that no quadratic form is fixed.
- "unitary": G fixes a unitary form modulo scalars. The matrix of the form is stored in sesquilinearForm. The scalars for each generator of G are stored in scalars.
- "orthogonalcircle":
- "orthogonalplus":
- "orthogonalminus": G fixes an orthogonal form modulo scalars. The matrix of the bilinear form is stored in bilinearForm and the corresponding quadratic form in quadraticForm. The scalars for each generator of G are stored in scalars.
If the absolutely irreducible group G preserves a symplectic form modulo scalars, this function returns the matrix of the form. If it is known that G does not preserve such a form it returns false. Otherwise it returns "unknown".
If the absolutely irreducible group G preserves a symplectic form (non-degenerate, alternating bilinear) modulo scalars, this function returns the scalars corresponding to the generators of the group of the form. If it is known that G does not preserve such a form it returns false. Otherwise it returns "unknown".
preserves an orthogonal form modulo scalars, and so as one component a symmetric bilinear form modulo scalars, this function returns the matrix of the symmetric bilinear form. If it is known that G does not preserve an orthogonal form modulo scalars, it returns false. Otherwise it returns "unknown".
If the absolutely irreducible group G preserves an orthogonal form modulo scalars, and so as one component a symmetric bilinear form modulo scalars, this function returns the scalars corresponding to the generators of the group of the symmetric bilinear form. If it is known that G does not preserve an orthogonal form modulo scalars, it returns false. Otherwise it returns "unknown".
If the absolutely irreducible group G preserves a quadratic form modulo scalars, this function returns the matrix of the form in upper triangular form. If it is known that G does not preserve such a form it returns false. Otherwise it returns "unknown".
If the absolutely irreducible group G preserves a quadratic form modulo scalars, this function returns the scalars corresponding to the generators of the group of the form. If it is known that G does not preserve such a form it returns false. Otherwise it returns "unknown".
If the absolutely irreducible group G preserves a unitary form (non-degenerate sesquilinear) modulo scalars, this function returns the matrix of the form. Otherwise it returns "unknown".
If the absolutely irreducible group G preserves a unitary form modulo scalars, this function returns the scalars corresponding to the generators of the group of the form. If it is known that G does not preserve such a form it returns false. Otherwise it returns "unknown".
If the absolutely irreducible group G preserves a classical form this function returns type. Otherwise it returns "unknown".
> G := Omega( 9, 11 ); > ClassicalForms( G ); rec<recformat<bilinearForm, quadraticForm, sesquilinearForm, bilinFlag, sesquiFlag, scalars, formType, bc, n> | bilinearForm := [ 0 0 0 0 0 0 0 0 1] [ 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 0 1 0 0] [ 0 0 0 0 0 1 0 0 0] [ 0 0 0 0 6 0 0 0 0] [ 0 0 0 1 0 0 0 0 0] [ 0 0 1 0 0 0 0 0 0] [ 0 1 0 0 0 0 0 0 0] [ 1 0 0 0 0 0 0 0 0], quadraticForm := [ 0 0 0 0 0 0 0 0 1] [ 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 0 1 0 0] [ 0 0 0 0 0 1 0 0 0] [ 0 0 0 0 3 0 0 0 0] [ 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0], sesquilinearForm := false, bilinFlag := true, sesquiFlag := false, scalars := [ 1, 1 ], formType := orthogonalcircle, n := 13> > FormType( G ); orthogonalcircle > SymplecticForm( G ); false
Let G be an irreducible subgroup of GL(d, q). The following algorithm is designed to test whether G contains the corresponding classical group Omega and is contained in Delta. Here Omega and Delta are defined as follows:
(d, q),
Omega = Omega^(d, q)
Case: MonStgElt Default: "unknown"
NumberOfElements: RngIntElt Default: 25
SetVerbose("User1", n): Maximum: 1
RecognizeClassical takes as input a group G, which is a subgroup of GL(d, q).The parameter Case is one of "linear", "symplectic", "orthogonalplus", "orthogonalminus", "orthogonalcircle", "unitary" or "unknown"; if Case is supplied, then the algorithm seeks to decide for this case only.
The parameter NumberOfElements is the number of random elements selected from G during the execution of the algorithm.
The output of RecognizeClassical is either true, false or "Does not apply". If the algorithm returns true, then we know with certainty that G contains Omega and is contained in Delta. Note that the proof of correctness of the algorithm depends on the finite simple group classification. If it returns false then either G does not contain Omega, or G is not contained in Delta, or G is not irreducible, or there is a small chance that G is contained in Delta and contains Omega. More precisely, if the irreducible group G is contained in Delta and really does contain Omega then the probability with which the algorithm returns false is less than varepsilon, where varepsilon is a real number between 0 and 1. The smaller the value of varepsilon, the larger NumberOfElements must be. If the algorithm returns "Does not apply" then it is not applicable to the given group.
If "User1" is set to verbose then, where RecognizeClassical returns true, it also prints the statement "Proved that the group contains a classical group of type case in n random selections", where n is the number of selections needed. If it returns false, it prints a statement giving some indication of why the algorithm reached this conclusion.
Theoretical details of the algorithms used may be found in Niemeyer & Praeger [NP97][NP98] [NP99] and Praeger [Pra99]. Its approach is based on the SL-recognition algorithm (Neumann & Praeger, [NP92]). This implementation also uses algorithms described in Celler & Leedham-Green [CLG97a][CLG97b] and Celler et al. [CLGM+95].
For small fields (q < 2^(16)), the cost of this implementation for a given value of NumberOfElements is O( d^3 log d ) bit operations.
This function tests whether the subgroup G of GL(d, q) contains SL(d, q). If the function can establish this fact, it returns true and otherwise false. Hence, if IsLinearGroup returns false, there is a small chance that G nevertheless contains SL(d, q). See RecognizeClassical for more details.
This function tests whether the subgroup G of GSp(d, q) contains Sp(d, q). If the function can establish this fact, it returns true and otherwise false. Hence, if IsSymplecticGroup returns false, there is a small chance that G nevertheless contains Sp(d, q). See RecognizeClassical for more details.
This function tests whether the subgroup G of GO^epsilon(d, q) contains Omega^epsilon(d, q). If the function can establish this fact, it returns true and otherwise false. Hence, if IsOrthogonalGroup returns false, there is a small chance that G nevertheless contains Omega^epsilon(d, q). See RecognizeClassical for more details.
This function tests whether the subgroup G of GU(d, q) contains SU(d, q). If the function can establish this fact, it returns true and otherwise false.
If G is known to be a classical subgroup of GL(d, q) this function returns the appropriate classical type as a string, i.e. "linear", "symplectic", "orthogonalplus", "orthogonalminus", "orthogonalcircle", or "unitary". Otherwise the function returns false.
> G := SU (60, 9); > SetVerbose( "User1", true ); > RecognizeClassical( G ); The group is not an extension field group The group is not nearly simple. The group acts irreducibly Proved that the group contains a classical group of type unitary in 6 random selections. true > IsLinearGroup( G ); false > IsUnitaryGroup( G ); true > IsSymplecticGroup( G ); false > IsOrthogonalGroup( G ); false > ClassicalType( G ); "unitary" > G := Sp (462, 3); > RecognizeClassical( G ); Proved that the group contains a classical group of type symplectic in 13 random selections. true
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.
Theoretical details of the algorithm used may be found in Holt, Leedham-Green, O'Brien, & Rees [DFH96b].
SetVerbose ("Smash", 1) will provide information on the progress of the algorithm.
BlockSizes: [RngIntElt] Default: []
Return true if G is primitive, false if G is not primitive, or "unknown" if no decision can be reached.If BlockSizes is supplied, then we search for systems of imprimitivity whose block sizes are in BlockSizes only. Otherwise we consider all valid sizes.
If G is imprimitive, return the blocks of imprimitivity of G.
Return the group induced by the action of G on the system of imprimitivity.
Return action of g on blocks of imprimitivity of G.
> MG := GL (4, 7); > PG := Sym (3); > G := WreathProduct (MG, PG); > > IsPrimitive (G); falseWe investigate the block system for G.
> B := Blocks (G); > B; > #B; 4 > B[1]; Vector space of degree 12, dimension 4 over GF(7) Generators: (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 0 0 0 0) Echelonized basis: (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 0 0 0 0)Now we obtain a permutation representation of G in its action on the blocks.
> P := BlocksImage (G);
> P;
Permutation group P acting on a set of cardinality 3
(1, 2, 3)
(2, 3)
> g := G.4 * G.3;
> ImprimitiveAction (G, g);
(1, 2)
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).
Theoretical details of the algorithm used may be found in Holt, Leedham-Green, O'Brien, & Rees [DFH96a]
SetVerbose ("SemiLinear", 1) will provide information on the progress of the algorithm.
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
- (i)
- 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;
- (ii)
- N rewritten as a subgroup of GL(d/e, q^e),
- (iii)
- a cyclic group E of order e which is isomorphic to G/N; and
- (iv)
- a sequence of images of the generators of G in E.
We analyze a semilinear group.
> 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);
The variable K is the kernel of the 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]
The variable R is 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]
Finally, E is the cyclic group of order e while phi gives the sequence of images of G.i in E.
> E;
Abelian Group isomorphic to Z/2
Defined on 1 generator
Relations:
2*E.1 = 0
>
> phi;
[ 0, 0, E.1 ]
Let G be a subgroup of GL(d, K), where K = GF(q),
and let V be the natural K[G]-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) GL(W).
Theoretical details of the algorithm used may be found in Leedham-Green & O'Brien [O'B97a][O'B97b].
SetVerbose ("Tensor", 1) will provide information on the progress of the algorithm.
Factors: [SeqEnum] Default: []
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.A sequence of valid dimensions Factors for potential factors may be supplied; for all elements [u, w] of Factors, we search for decompositions of V as U tensor W, where U has dimension u and W has dimension w only. Otherwise we consider all valid factorisations.
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 > C := TensorBasis(G);
So C is the change-of-basis matrix. 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] >
We use the function IsProportional to 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] >
Finally, we display the 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]
Let G be a subgroup of GL(d, K), where K = GF(q) and q = p^e for some prime p, and let V be the natural K[G]-module. Assume that d has a proper factorisation as u^r. We say that G is tensor-induced if G preserves a decomposition of V as U_1 tensor U_2 tensor ... tensor U_r where each U_i has dimension u > 1 and r > 1, and the set of U_i is permuted by G. If G is tensor-induced, then there is a homomorphism of G into the symmetric group S_r.
Theoretical details of the algorithm used may be found in Leedham-Green & O'Brien [LGO02].
SetVerbose ("TensorInduced", 1) will provide information on the progress of the algorithm.
InducedDegree: RngIntElt Default: "All"
Return true if G is tensor-induced, false if G is not tensor-induced, or "unknown" if no decision can be reached.If the value of InducedDegree is r, then we search for homomorphisms into the symmetric group of degree r only. Otherwise we consider all valid degrees.
Return the change-of-basis matrix which exhibits that G is tensor-induced.
Return a sequence whose i-th entry is the homomorphic image of G.i in S_r.
Return tensor induced action of g.
We illustrate the use of the functions for determining if a matrix group is tensor induced.
> G := GL(2, 3); > S := Sym(3); > G := TensorWreathProduct(G, S); > IsTensorInduced(G); true
We recover the permutations.
> TensorInducedPermutations(G);
[
Id(S),
Id(S),
(1, 2, 3),
(1, 2)
]
Hence G.1 and G.2 are in the kernel of the homomorphism from G to S. We extract the change-of-basis matrix C and then conjugate G.1 by C, thereby obtaining a visible Kronecker product.
> C := TensorInducedBasis(G); > x := G.1^C; > x; [2 0 0 0 0 0 0 0] [0 2 0 0 0 0 0 0] [0 0 2 0 0 0 0 0] [0 0 0 2 0 0 0 0] [1 0 0 0 1 0 0 0] [0 1 0 0 0 1 0 0] [0 0 1 0 0 0 1 0] [0 0 0 1 0 0 0 1]
Finally, we verify that x = G.1^C is a Kronecker product for each of 2 and 4.
> IsProportional(x, 2); true <[2 0] [0 2], [1 0 0 0] [0 1 0 0] [2 0 2 0] [0 2 0 2]> > IsProportional(x, 4); true <[2 0 0 0] [0 2 0 0] [0 0 2 0] [0 0 0 2], [1 0] [2 2]>
Let G <= GL(d, q), where for some prime r, d=r^m. If G is contained in the normaliser of an r-group R, of order either r^(2m + 1) or 2^(2m + 2), then either R is extraspecial (in the first case), or R is a 2-group of symplectic type (that is, a central product of an extraspecial 2-group with a cyclic group of order 4).
IsExtraSpecialNormaliser searches for elements of the normal subgroup, and can only reach negative conclusions in certain limited cases.
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".
Return sequence of integers, p and n, where the extraspecial or symplectic subgroup N normalised by G has order p^(n).
Return the extraspecial or symplectic subgroup normalised by G.
Return the action of generators of G on its normal extraspecial or symplectic subgroup as a sequence of matrices, one for each generator of G.
Action matrix of element g on extraspecial or symplectic group normalised by G.
Return basis of the extraspecial or symplectic subgroup normalised by G.
> F:=GF(8);
> P:=GL(7,F);
> w := PrimitiveElement(F);
> g1:=P![
> w,0,w^2,w^5,0,w^3,w,w,1,w^6,w^3,0,w^4,w,w^2,w^6,w^4,1,w^3,w^3,w^5,
> w^6,w,w^3,1,w^5,0,w^4,1,w^6,w^3,w^6,w^3,w^2,w^2,w^3,w^6,w^6,w^4,1,w^2,w^4,
> w^5,w^4,w^2,w^6,1,w^5,w ];
> g2:=P![w^3,w^4,w^2,w^6,w,w,w^3,w^3,w^4,w,w,w^2,w^3,w^3,w,w^3,w^5,w,1,w^3,w,
> 0,w^2,w^6,w,w^5,1,w,w^6,0,w^3,0,w^4,w,w^5,w^3,w^3,1,w^3,w^5,w^5,w^3,
> w^4,w^6,w,w^6,w^4,w^4,0 ];
> g3:=P![w^5,w^6,w^2,w,w,w^4,w^6,w^6,w^6,w,w^6,w,1,w^3,w,w^6,w^2,w,w^6,w^3,w^6,
> w^2,w^6,w^6,w^3,w,w^6,w^5,0,w^4,w^6,w^6,w,w^2,0,w,w^3,w^5,w^2,w^3,w^4,w^6,
> 0,w^3,w,w^3,w^4,w^3,1];
> gens := [g1,g2,g3];
> G := sub< P | gens >;
> IsExtraSpecialNormaliser(G);
Found element of kernel after 1 attempts
true
> ExtraSpecialParameters (G);
[ 7, 3 ]
> N:=ExtraSpecialNormaliser(G);
> N;
[
[3 4]
[1 4],
[4 3]
[0 2],
[1 0]
[0 1]
]
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. Theoretical details of the algorithms used may be found in Holt, Leedham-Green, O'Brien, & Rees [DFH96a].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.
- (ii)
- G acts semilinearly over an extension field L of K, and N acts linearly over L;
- (iii)
- G acts imprimitively on V and N fixes each block of imprimitivity;
- (iv)
- G preserves a tensor product decomposition U tensor W of V, where N acts as scalar matrices on U;
- (v)
- N acts absolutely irreducibly on V and is an extraspecial p-group for some prime p, or 2-group of symplectic type;
- (vi)
- G preserves a tensor-induced 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 tensor-induced 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.
Progress of the algorithm is provided by SetVerbose ("Smash", 1).
The access functions described in the sections on Primitivity Testing, Semilinearity, Tensor Products, Tensor Induction, and Normalisers of Extraspecial groups may be used to extract information about decompositions of type (ii), (iii), (iv), (v) and (vi). We illustrate such decompositions below.
We begin with an example where no decomposition exists.
> G := GL(4, 5); > SearchForDecomposition (G, [G.1]); Smash: No decomposition found false
The second example is of an 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
> BlocksImage (G);
Permutation group acting on a set of cardinality 3
Id()
Id()
(1, 2, 3)
(1, 2)
The third example admits a 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 ]
The fourth example admits a 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]
Our fifth example is of a tensor-induced decomposition.
> M := GL (3, GF(2)); > P := Sym (3); > G := TensorWreathProduct (M, P); > SearchForDecomposition (G, [G.1]); Smash: G is tensor induced true > > IsTensorInduced (G); true > TensorInducedPermutations (G); [ Id(P), Id(P), (1, 3, 2), (1, 3) ]
Our final example is of a normaliser of a symplectic 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 symplectic 2-group true > IsExtraSpecialNormaliser (G); true > ExtraSpecialParameters (G); [2, 6] > g := G.1 * G.2; > ExtraSpecialAction(G, g); [0 1 0 0] [1 1 0 0] [0 1 1 1] [1 1 1 0]
The algorithm implemented by these functions is due to Glasby & Howlett [GH97].
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]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]