The functions described in this section apply only to finite groups for which a base and strong generating set may be constructed.
Let G be a matrix group and let M be its natural module. Now G has an action on the elements and submodules of M. A derived G-set for G consists of the closure under the natural action of G of one of the following:
Given an element g belonging to the matrix group G with natural module M and an element u of this module, return the vector u * g.
Given an element g belonging to the matrix group G with natural module M and an object y which is an element of some derived G-set of M, find the image of y under g.
Given a matrix group G with natural module M and an object y which is either a vector of M, a submodule of M, or a tuple whose components are either vectors or submodules, find the orbit of y under G.
Given a matrix group G with natural module M and an object y which is either a vector of M, a submodule of M, or a tuple whose components are either vectors or submodules, return true if the orbit of y under G has length less than or equal to b. Otherwise the function returns false. If it returns true, then the orbit of y is returned as the second value.
Given a matrix group G with natural R-module M, construct the orbits of G on the vectors of M. The orbits are returned as a sequence of sets.
Given a matrix group G with natural R-module M, construct the orbits of G on the rank-1 submodules of M. The orbits are returned as a sequence of sets.
Given a matrix group G with natural module M and a set S of vectors or subspaces of M, return the union of orbits of the elements of S under the natural action of G on M.
Given a matrix group G with natural module M and an object y which is either a vector of M, a submodule of M, or a tuple whose components are either vectors or submodules, determine the stabilizer of y in G.
> V := RSpace(G); > u := V![1,0,0,0,0,0]; > U := sub< V | u >; > x := < u, U >; > W := sub< V | u, u*G.1 >; > u^G.1; (w^6 w^3 w^2 0 0 0) > U^G.1; Vector space of degree 6, dimension 1 over GF(3, 2) Echelonized basis: ( 1 w^5 2 0 0 0) > W^G.1; Vector space of degree 6, dimension 2 over GF(3, 2) Echelonized basis: ( 1 w^5 0 0 0 0) ( 0 0 1 0 0 0) > x^G.1; <(w^6 w^3 w^2 0 0 0), Vector space of degree 6, dimension 1 over GF(3, 2) Echelonized basis: ( 1 w^5 2 0 0 0)> > H := sub< G | G.1, G.2 >; > #Orbit(H, u); 252 > #Orbit(H, U); 63 > #Orbit(G, U); 3150 > Stabilizer(G, U); MatrixGroup(6, GF(3^2)) of order 384 = 2^7 * 3 Generators: [ 2 0 0 0 0 0] [w^3 w w 0 2 w^2] [w^5 w^7 w^7 0 1 w^2] [ 0 0 1 2 1 0] [w^7 w^5 0 0 0 w^6] [ w w^3 0 0 0 w^6] [w^2 0 0 0 0 0] [w^5 w^5 w^5 0 w 0] [w^7 w^3 w^3 0 0 w^7] [w^2 w^3 w w^6 w w^3] [w^3 1 w^6 0 w w^7] [ w w^6 2 0 w w^7] [w^6 0 0 0 0 0] [ 0 2 0 0 0 0] [ 0 0 w^6 0 0 0] [w^2 w^7 w^6 w^2 0 0] [ w 0 w 0 2 0] [w^6 w^7 w^2 0 0 w^2] [ 2 0 0 0 0 0] [ 0 2 0 0 0 0] [ 0 0 2 0 0 0] [ 0 0 0 2 0 0] [ 0 0 0 0 2 0] [ 0 0 0 0 0 2] > #Orbit(H, x); 252 > #Orbit(H, W); 28
In this section we describe a number of constructions for orbits and stabilizers which in certain circumstances may be applicable to much larger groups than the functions described above.
Determine representatives and lengths for the orbits of all k-dimensional subspaces of the natural vector space under action of a matrix group defined over a prime field; return a sequence of tuples each containing an orbit length and representative. This function is very space-efficient and hence has a significantly larger range than the general-purpose Orbits; however, only representatives and lengths are stored. Theoretical details of the algorithm used may be found in O'Brien [O'B90].
Return number of subspaces of dimension s fixed by matrix x.
> G := GL (4, 5);
> H := ExteriorSquare (G);
> H;
MatrixGroup(6, GF(5))
Generators:
[2 0 0 0 0 0]
[0 2 0 0 0 0]
[0 0 1 0 0 0]
[0 0 0 2 0 0]
[0 0 0 0 1 0]
[0 0 0 0 0 1]
[0 0 0 1 0 0]
[1 0 0 0 1 0]
[1 0 0 0 0 0]
[0 1 0 0 0 1]
[0 1 0 0 0 0]
[0 0 1 0 0 0]
> O := OrbitsOfSpaces (H, 2);
We see that there are four orbits:
> O;
[
<
4836,
Vector space of degree 6, dimension 2 over GF(5)
Generators:
(1 0 0 0 0 0)
(0 1 0 0 0 0)
Echelonized basis:
(1 0 0 0 0 0)
(0 1 0 0 0 0)
>,
<
96720,
Vector space of degree 6, dimension 2 over GF(5)
Generators:
(1 0 1 1 0 0)
(0 1 0 0 0 0)
Echelonized basis:
(1 0 1 1 0 0)
(0 1 0 0 0 0)
>,
<
251875,
Vector space of degree 6, dimension 2 over GF(5)
Generators:
(1 0 0 0 1 0)
(0 1 0 0 0 0)
Echelonized basis:
(1 0 0 0 1 0)
(0 1 0 0 0 0)
>,
<
155000,
Vector space of degree 6, dimension 2 over GF(5)
Generators:
(1 0 1 1 1 0)
(0 1 1 1 0 0)
Echelonized basis:
(1 0 1 1 1 0)
(0 1 1 1 0 0)
>
]
We compute the number of spaces of dimension 2 fixed by H.1 and the number
of spaces of dimension 3 fixed by H.2.
> NumberOfFixedSpaces(H.1, 2); 1023 > NumberOfFixedSpaces(H.2, 3); 2
MaxSize: RngIntElt Default: 10000
NumberCoincidences: RngIntElt Default: 15
Estimate the size of the orbit of the vector v or subspace U of natural vector space under the action of matrix group G by constructing at most MaxSize random elements of the orbit and counting at most NumberCoincidences coincidences. The function returns a lower bound, upper bound, and estimate of size; if insufficient coincidences are found to estimate the orbit size, the function returns 0. Theoretical details of the algorithm used may be found in Eick, Leedham-Green and O'Brien [ELGO02].
ImageGenerators: SeqEnum Default: []
MaxSize: RngIntElt Default: 10000
NumberCoincidences: RngIntElt Default: 15
OrderCheck: BoolElt Default: false
The matrix group A is the image of the representation of the matrix group G and A acts on U, a subspace or vector. Approximate the stabiliser of U under A. We assume either a 1 - 1 correspondence between generators of G and those of A, or between generators of G and those elements of A supplied as ImageGenerators. Elements of G whose images in A fix U are obtained by constructing at most MaxSize elements of the orbit of U under A or until we find Numbercoincidences repetitions in this orbit; if OrderCheck is true, report the order of the subgroup S of A which is found. Return preimage of S in G and S, together with a lower bound, upper bound, and estimate of the size of orbit of U. If insufficient coincidences are found to estimate the orbit size, the function returns these last values as 0.
> G := GL (4, 5); > A := ExteriorSquare (G); > V := VectorSpace (GF (5), 6); > U := sub < V | [Random (V): i in [1..2]]>; > U; Vector space of degree 6, dimension 2 over GF(5) Generators: (4 3 2 1 0 2) (3 2 2 4 4 1) Echelonized basis: (1 0 2 0 2 4) (0 1 3 2 4 2) > EstimateOrbit (A, U); 209316 594421 324272 > H, B, lb, ub, estimate := ApproximateStabiliser (G, A, U); > #H, #B; 460800 230400
Determine the subgroup of GL(d, F), for F a finite field, which stabilises the sequence Q of subspaces of the natural vector space. The function also returns generators for the largest unipotent subgroup of the stabiliser. For a description of this algorithm, see Schwingel [Sch00]; this implementation was prepared by Eamonn O'Brien.
> V := VectorSpace(GF (3), 4);
> Spaces := [sub< V | [1,1,0,2]>, sub < V | [ 1, 0, 2, 0 ], [ 0, 1, 0, 0]>];
> S, P := StabiliserOfSpaces(Spaces);
> #S;
5184
> P;
[
[1 1 0 0]
[0 1 0 0]
[0 1 1 0]
[0 1 0 1],
[2 0 2 0]
[0 1 0 0]
[1 0 0 0]
[1 0 2 1],
[1 0 1 2]
[0 1 0 0]
[0 0 2 2]
[0 0 1 0]
]
Thus, the unipotent subgroup generated by P has order 33.
If G is a p-subgroup of GL(d, F), where F is a finite field of characteristic p, then return true, else return false.
Given a unipotent subgroup G of GL(d, F), for F a finite field, U a subspace of the natural vector space, determine the stabiliser in G of U. The function returns the stabiliser in G of U, the canonical element C of the orbit of U under G, an element x of G such that Ux = C, and an SLP for x as an element of WordGroup(G). This function does not compute the orbit of U under G, but instead constructs the canonical element of the orbit. Hence it can be used to decide whether or not two subspaces belong to the same orbit. For a description of this algorithm, see [Sch00]; this implementation was prepared by Elliot Costi.
> V := VectorSpace(GF (3), 4);
> G := sub< GL (4, 3) |
> [ 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1 ],
> [ 2, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 2, 1 ],
> [ 1, 0, 1, 2, 0, 1, 0, 0, 0, 0, 2, 2, 0, 0, 1, 0 ] >;
> U := sub < V | [ 1, 2, 0, 1 ],[ 2, 2, 1, 0 ]>;
> S, C, x, w := UnipotentStabiliser(G, U);
> S;
MatrixGroup(4, GF(3))
Generators:
[2 1 2 0]
[0 1 0 0]
[1 1 0 0]
[1 1 2 1]
> #S;
3
> Index(G, S);
9
So the stabiliser of U has order 3 and U lies in an orbit of size 9.
We print the canonical element of the orbit of U under G.
The element x maps U to C and w evaluates to x.
> C; Vector space of degree 4, dimension 2 over GF(3) Echelonized basis: (1 0 0 0) (0 1 2 0) > U^x; Vector space of degree 4, dimension 2 over GF(3) Echelonized basis: (1 0 0 0) (0 1 2 0) > W, phi := WordGroup (G); > phi (w); [1 0 2 1] [0 1 0 0] [0 0 0 1] [0 0 2 2]
Given a matrix group G with natural module M, and a set T consisting of either (a) elements of M, (b) submodules of M or (c) tuples, form the G-closure Y of T and construct the homomorphism φ: G -> L, where the permutation group L gives the action of G on the set Y. The function returns:The permutation group L acts on the set X = {1..#Y}. The map φ can be used to pass between X and Y. If k∈X then φ(k) is the corresponding element of Y, while if t∈Y then the inverse image of t under φ is the corresponding element of X.
- (a)
- The natural homomorphism φ: G -> L;
- (b)
- The induced group L;
- (c)
- The kernel of the action (a subgroup of G).
Given a matrix group G with natural module M, and a set T consisting of either (a) elements of M, (b) submodules of M or (c) tuples, form the G-closure Y of T. If the cardinality of Y does not exceed b, then construct the homomorphism φ: G -> L, where the permutation group L gives the action of G on the set Y. In this case the function returns:
- (a)
- The boolean value true.
- (b)
- The natural homomorphism φ: G -> L;
- (c)
- The induced group L;
- (d)
- The kernel of the action (a subgroup of G). If the cardinality of Y exceeds b, simply return false. (The action of G on Y is not constructed in this case).
Given a matrix group G with natural module M, and a set T consisting of either (a) elements of M, (b) submodules of M or (c) tuples, form the G-closure Y of T and return the permutation group L giving the action of G on Y. The second return value is Y, with the indexing of Y giving the correspondence between Y and the points acted on by L.
Given a matrix group G with natural module M, and set T consisting of either (a) elements of M, (b) submodules of M or (c) tuples, form the G-closure Y of T. If the cardinality of Y does not exceed b, return true together with the permutation group L giving the action of G on Y. If the cardinality of Y does exceed b, the action is not constructed and the single value false is returned.
Given a matrix group G with natural module M, and a set T consisting of either (a) elements of M, (b) submodules of M or (c) tuples, form the G-closure Y of T and return the the kernel of the action of G on Y.
Given a matrix group G with natural module M, and set T consisting of either (a) elements of M, (b) submodules of M or (c) tuples, form the G-closure Y of T. If the cardinality of Y does not exceed b, return the boolean value true together with the kernel of the action of G on Y. If the cardinality of Y does exceed b, the kernel is not constructed and the single value false is returned.
> [ Factorization(CharacteristicPolynomial(G.i)) : i in [1..3] ];
[
[
<x^3 + w^5*x^2 + w^3*x + 2, 1>,
<x^3 + w^7*x^2 + w*x + 2, 1>
],
[
<x + 2, 6>
],
[
<x + w^2, 3>,
<x + w^6, 3>
]
]
> y := Eigenspace(G.2, -2);
> y;
Vector space of degree 6, dimension 3 over GF(3, 2)
Echelonized basis:
(1 0 0 1 2 1)
(0 1 0 2 1 2)
(0 0 1 1 2 1)
> #Orbit(G, y);
280
> P := OrbitImage(G, y);
> P;
Permutation group P of degree 280
> Order(P);
604800
> CompositionFactors(P);
G
| J2
1
Thus, our group has the simple group J2 of Janko as a composition factor.
> Order(G); 1209600
Hence the kernel of this action has order 2.
Given a subgroup H of the group G, construct the permutation representation of G given by the action of G on the set of (right) cosets of H in G. The function returns:
- (a)
- The natural homomorphism f: G -> L;
- (b)
- The induced permutation group L;
- (c)
- The kernel K of the action (a subgroup of G).
Given a subgroup H of the group G, construct the image L of G given by the action of G on the set of (right) cosets of H in G. L is returned as a permutation group.
Given a subgroup H of the group G, construct the kernel of the action of G on the set of (right) cosets of H in G.
> G := MatrixGroup< 3, GF(3) | [0,2,0, 1,1,0, 0,0,1], [0,1,0, 0,0,1, 1,0,0] >;
> Order(G);
5616
> H := sub< G | G.1^2, G.2 >;
> Order(H);
216
> P := CosetImage(G, H);
> P;
Permutation group P of degree 26
(1, 2)(3, 4, 6, 5, 7, 9)(8, 11)(10, 13, 15, 20, 18, 17)
(12, 16, 21, 14, 19, 24)(23, 26)
(2, 3, 5)(4, 6, 8)(7, 10, 14)(9, 12, 17)(11, 15, 20)(13, 18, 23)
(16, 22, 21)(19, 25, 24)
A set of functions is provided for working with the action of G on the natural G-module M, for a matrix group G defined over a finite field. Many of these functions are similar to those presented in the general module chapter.
The natural R[G]-module M for the matrix group G.
Given a matrix group G, return true iff G acts irreducibly on its natural module M. If G acts reducibly on M, a proper submodule S of M is also returned.
Given a matrix group G and a submodule S of the natural module M of G, return the action homomorphism f of G on S, together with the image of f.
Given a matrix group G and a submodule S of the natural module M of G, return the image of the action homomorphism of G on S.
Given a matrix group G and a submodule S of the natural module M of G, return the quotient action homomorphism f of G on S, together with the image of f.
Given a matrix group G and a submodule S of the natural module M of G, return the quotient image of the action homomorphism of G on S.
Given a matrix group G, return true if and only if G acts absolutely irreducibly on its natural module M. In addition, if G is absolutely irreducible, the function returns the (matrix algebra) generator of the endomorphism algebra E of M (which is always a field), and the dimension of E.
Given an irreducible matrix group G, return the isomorphic reduced-degree absolute representation A of G, which is over the absolute field of the natural module M of G and is absolutely irreducible, together with the corresponding isomorphism.
Given a matrix group G defined over a finite field K, return the minimal subfield of K over which G can be realised.