|
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:
 - A set of vectors of M;
- A set of k element subsets of vectors of M;
- A set of k element sequences of vectors of M;
- A set of submodules of M, each of which has fixed dimension k;
- A cartesian product of G-sets.
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.
Orbit(G, y) : GrpMat, Elt -> SetEnum
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.
We continue with the group J2A2 introduced above.
> 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].
NumberOfFixedSpaces(x, s) : AlgMatElt, RngIntElt -> RngIntElt
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
EstimateOrbit(G, U: parameters) : GrpMat, ModTupFld -> RngIntElt, RngIntElt, RngIntElt
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 3 3.
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:
- (a)
- The natural homomorphism φ: G -> L;
- (b)
- The induced group L;
- (c)
- The kernel of the action (a subgroup of G).
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.
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.
We look for a small G-set for the group J2A2 (defined above)
by examining eigenspaces of its generators. Having found a reasonably sized
set, we then construct a permutation representation for G on this set.
> [ 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.
We construct G = SL(3, 3), a subgroup H of G, and
the permutation representation of G given by its action on the cosets
of H.
> 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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|