Matrix Group Actions

The functions described in this section apply only to finite groups for which a base and strong generating set may be constructed.

Orbits and Stabilizers

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.

u * g: ModTupRngElt, GrpMatElt -> ModTupRngElt: 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\).

y ^ g: Elt, GrpMatElt -> Elt: 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\).

y ^ G: Elt, GrpMat -> SetEnum
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\).

OrbitBounded(G, y, b): GrpMat, Elt, RngIntElt -> BoolElt, 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, 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.

Orbits(G): GrpMat -> [ SetIndx ]: 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.

LineOrbits(G): GrpMat -> [ SetIndx ]: 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.

OrbitClosure(G, S): GrpMat, { Elt } -> GSet: 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\).

Stabilizer(G, y): GrpMat, Elt -> GrpMat: 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\).

Example: Orbits of Vectors and Subspaces (ex-3be539)

Run in calculator (opens in a new tab)

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

Run in calculator (opens in a new tab)

Orbit and Stabilizer Functions for Large Groups

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.

OrbitsOfSpaces(G, k): GrpMat, RngIntElt -> SeqEnum: 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 [OBr90].

NumberOfFixedSpaces(x, s): GrpMatElt, RngIntElt -> RngIntElt
NumberOfFixedSpaces(x, s): AlgMatElt, RngIntElt -> RngIntElt: Return number of subspaces of dimension \(s\) fixed by matrix \(x\).

Example: Orbits of 2-Spaces under an Exterior Square (ex-dc691e)

Run in calculator (opens in a new tab)

> 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

Run in calculator (opens in a new tab)

EstimateOrbit(G, v: parameters): GrpMat, ModTupFldElt -> RngIntElt, RngIntElt, RngIntElt

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].

ApproximateStabiliser(G, A, U: parameters): GrpMat, GrpMat, ModTupFld -> GrpMat, GrpMat, RngIntElt, RngIntElt, RngIntElt

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.

Example: Estimating an Orbit and Stabiliser (ex-32857e)

Run in calculator (opens in a new tab)

> 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

Run in calculator (opens in a new tab)

StabiliserOfSpaces(Q): SeqEnum -> GrpMat, SeqEnum: 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 [Sch00b]; this implementation was prepared by Eamonn O’Brien.

Example: Stabiliser of Spaces (ex-3c31f0)

Run in calculator (opens in a new tab)

> 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\).

Run in calculator (opens in a new tab)

IsUnipotent(G): GrpMat -> BoolElt: 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.

UnipotentStabiliser(G, U: parameters): GrpMat, ModTupFld -> GrpMat, ModTupFld, GrpMatElt, GrpSLPElt: 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 \(U^x = 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 [Sch00b]; this implementation was prepared by Elliot Costi.

Example: Unipotent Stabiliser of Spaces (ex-78b096)

Run in calculator (opens in a new tab)

> 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]

Run in calculator (opens in a new tab)

Action on Orbits

OrbitAction(G, T): GrpMat, Elt -> Hom(Grp), GrpPerm, GrpMat

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 \(\phi: G \rightarrow L\), where the permutation group \(L\) gives the action of \(G\) on the set \(Y\). The function returns:

(a): The natural homomorphism \(\phi: G \rightarrow 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 \(\phi\) can be used to pass between \(X\) and \(Y\). If \(k\in X\) then \(\phi(k)\) is the corresponding element of \(Y\), while if \(t\in Y\) then the inverse image of \(t\) under \(\phi\) is the corresponding element of \(X\).

OrbitActionBounded(G, T, b): GrpMat, Elt, RngIntElt -> BoolElt, Hom(Grp), GrpPerm, GrpMat

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 \(\phi: G \rightarrow 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 \(\phi: G \rightarrow 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).

OrbitImage(G, T): GrpMat, Set -> GrpPerm, SetIndx: 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\).

OrbitImageBounded(G, T, b): GrpMat, Set, RngIntElt -> BoolElt, GrpPerm, SetIndx: 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.

OrbitKernel(G, T): GrpMat, Set -> GrpMat: 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 kernel of the action of \(G\) on \(Y\).

OrbitKernelBounded(G, T, b): GrpMat, Set, RngIntElt -> BoolElt, GrpMat: 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.

Example: Permutation Representation from Eigenspaces (ex-2b1162)

Run in calculator (opens in a new tab)

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 \(J_2\) of Janko as a composition factor.

> Order(G);
1209600

Hence the kernel of this action has order 2.

Run in calculator (opens in a new tab)

Action on a Coset Space

CosetAction(G, H): GrpMat, GrpMat -> Hom(Grp), GrpPerm, GrpMat

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 \rightarrow L\);
(b): The induced permutation group \(L\);
(c): The kernel \(K\) of the action (a subgroup of \(G\)).

CosetImage(G, H): GrpMat, GrpMat -> GrpPerm: 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.

CosetKernel(G, H): GrpMat, GrpMat -> GrpMat: 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\).

Example: Action on Cosets in SL(3, 3) (ex-71335a)

We construct \(G = {\operatorname{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)

Run in calculator (opens in a new tab)

Action on the Natural \(G\)-Module

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.

GModule(G): GrpMat -> ModGrp: The natural \(R[G]\)-module \(M\) for the matrix group \(G\).

IsIrreducible(G): GrpMat -> BoolElt, ModGrp: 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.

SubmoduleAction(G, S): GrpMat -> Map, GrpMat: 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\).

SubmoduleImage(G, S): GrpMat -> GrpMat: 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\).

QuotientModuleAction(G, S): GrpMat -> Map, GrpMat: 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\).

QuotientModuleImage(G, S): GrpMat -> GrpMat: 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\).

IsAbsolutelyIrreducible(G): GrpMat -> BoolElt: 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\).

AbsoluteRepresentation(G): GrpMat -> GrpMat, Map: 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.

MinimalField(G): GrpMat -> FldFin: Given a matrix group \(G\) defined over a finite field \(K\), return the minimal subfield of \(K\) over which \(G\) can be realised.

Matrix Group Actions#

Orbits and Stabilizers#

Orbit and Stabilizer Functions for Large Groups#

Action on Orbits#

Action on a Coset Space#

Action on the Natural \(G\)-Module#

Matrix Group Actions

Orbits and Stabilizers

Orbit and Stabilizer Functions for Large Groups

Action on Orbits

Action on a Coset Space

Action on the Natural \(G\)-Module