Expressing a matrix in terms of subgroup generators using Magma

Question

With Magma, it is possible to define a subgroup $H$ of a finite matrix group $G$ in terms of generators. Given a matrix $M\in G$, Magma can also determine whether $M\in H$. Presumably, if Magma decides that $M\in H$, it has internally found an expression for $M$ in terms of the generators of $H$. Is it possible to obtain this expression from Magma, or another CAS?

Answer 1

It is possible to do this in GAP. You may paste the following code into GAP to see the example:

G:=GL(3,5);
Size(G);
Random(G);
gens:=[ [ [ 0, 0, 4 ], 
          [ 4, 3, 1 ], 
          [ 4, 1, 3 ] ],
        [ [ 2, 3, 0 ], 
          [ 0, 4, 2 ], 
          [ 2, 0, 2 ] ] ];;
gens:=gens*One(GF(5));;
Display(gens[1]);
Display(gens[2]);
H:=Subgroup(G,gens);
Size(H);
F:=FreeGroup("x","y");
hom := GroupHomomorphismByImages( F, H, GeneratorsOfGroup(F), GeneratorsOfGroup(H) );
h:=Random(H);
PreImagesRepresentative(hom,h);
h:=Random(H);
PreImagesRepresentative(hom,h);

Below there is the actual GAP session with the output and my annotations.

First we create some group, for example:

gap> G:=GL(3,5);
GL(3,5)
gap> Size(G);
1488000
gap> Random(G);
[ [ Z(5)^0, Z(5)^3, Z(5) ], [ 0*Z(5), Z(5)^2, Z(5)^2 ], [ Z(5), Z(5)^2, 0*Z(5) ] ]

Now prepare generators for the subgroup:

gap> gens:=[ [ [ 0, 0, 4 ],
>              [ 4, 3, 1 ],
>              [ 4, 1, 3 ] ],
>            [ [ 2, 3, 0 ],
>              [ 0, 4, 2 ],
>              [ 2, 0, 2 ] ] ];;
gap> gens:=gens*One(GF(5));;
gap> Display(gens[1]);
 . . 4
 4 3 1
 4 1 3
gap> Display(gens[2]);
 2 3 .
 . 4 2
 2 . 2

The subgroup is of order 48000:

gap> H:=Subgroup(G,gens);
Group(
[
  [ [ 0*Z(5), 0*Z(5), Z(5)^2 ], [ Z(5)^2, Z(5)^3, Z(5)^0 ], [ Z(5)^2, Z(5)^0, Z(5)^3 ]
     ], [ [ Z(5), Z(5)^3, 0*Z(5) ], [ 0*Z(5), Z(5)^2, Z(5) ], [ Z(5), 0*Z(5), Z(5) ]
     ] ])
gap> Size(H);
48000

Now we use the same approach as in the Rubik's Cube example: create a free group of the same rank as the number of generators of the subgroup H and a homomorphism from this free group onto H:

gap> F:=FreeGroup("x","y");
<free group on the generators [ x, y ]>
gap> hom := GroupHomomorphismByImages( F, H, GeneratorsOfGroup(F), GeneratorsOfGroup(H) );
[ x, y ] ->
[
  [ [ 0*Z(5), 0*Z(5), Z(5)^2 ], [ Z(5)^2, Z(5)^3, Z(5)^0 ], [ Z(5)^2, Z(5)^0, Z(5)^3 ]
     ], [ [ Z(5), Z(5)^3, 0*Z(5) ], [ 0*Z(5), Z(5)^2, Z(5) ], [ Z(5), 0*Z(5), Z(5) ]
     ] ]

Using this homomorphism, we are able to factorise elements of H in terms of its generators (note that in this case the answers are not necessarily the shortest possible words):

gap> h:=Random(H);
[ [ Z(5), 0*Z(5), Z(5)^3 ], [ Z(5)^2, Z(5)^3, 0*Z(5) ], [ Z(5)^2, 0*Z(5), Z(5)^3 ] ]
gap> PreImagesRepresentative(hom,h);
y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-3*x^-1*y*x^-2
gap> h:=Random(H);
[ [ Z(5), Z(5)^2, Z(5)^2 ], [ Z(5)^3, Z(5)^2, Z(5)^0 ], [ Z(5)^2, Z(5)^3, 0*Z(5) ] ]
gap> PreImagesRepresentative(hom,h);
x^-1*y^-2*(x^-1*y)^2*y*x^-4*y^-1*x^3*y^-1

---

P.S. Since GAP is open-source, it's not hard to find out which method it uses for the membership test. In the setup above, let's trace all calls to 'in' (i.e. membership test):

gap> TraceMethods(\in);
gap> h:=Random(G);
[ [ 0*Z(5), Z(5)^2, Z(5)^3 ], [ Z(5), Z(5)^2, Z(5) ], 
  [ Z(5)^0, 0*Z(5), Z(5)^3 ] ]
gap> h in H;
#I  in: by nice monomorphism
#I  in: for a permutation, and a permutation group
false

The first of the two methods is the one that is used in this example to checks the membership of h in H. It is contained in lib/grpnice.gi, and it does not seem to store the factorisation of h in case of a positive answer.