[GAP Forum] Computing kernel

[Mathieu Dutour]

Dear Alexander,

thank you very much, it works.

Still, it appears to me that the FreeGroup trick serves essentially
to trigger off the checking of redundancy of generators. It looks
like a hack.   I understand that checking redundancy of generators
is expensive, but actually I am fine with having lots of generators.
Shouldn't there be a more direct way?

Also, does your two approaches use different algorithms?

  Mathieu


On Wed, Apr 23, 2014 at 5:33 PM, Alexander Hulpke <hulpke at math.colostate.edu
> wrote:

>
> Dear Forum, Dear Mathieu,
>
> > I have a
> huge, in fact infinite,
> > matrix group G and a permutation representation phi.
> > I want to find a generating set for the kernel. It seems to
> > be a hard problem with GAP and I am unsure why. Is it really
> > such a hard problem ?
>
> GAP currently does not treat subgroups of GLn(Z) special (it should in
> fact treat them more like subgroups of a finitely presented group), but
> just like other groups given by generators. The problem then is the default
> routine for closure that tries to do a membership test.
>
> As an experiment, instead of calculating the kernel, ask for
>
> CoKernelGensPermHom(InverseGeneralMapping(phi))
>
> and you will get generators for the kernel immediately. What takes
> infinitely long is effectively the test for redundancy of generators.
>
> What I would do instead is to pull your result through a finitely
> presented group. (I happen to have almost a function for this which
> constructs a homomorphism from fp->matrix SL, which might be of interest
> and which I append.)
>
> gap> slhom:=SLNZFP(3);
> [ t12, t13, t21, t23, t31, t32 ] ->
> [ [ [ 1, 1, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
>   [ [ 1, 0, 1 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
>   [ [ 1, 0, 0 ], [ 1, 1, 0 ], [ 0, 0, 1 ] ],
>   [ [ 1, 0, 0 ], [ 0, 1, 1 ], [ 0, 0, 1 ] ],
>   [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 1, 0, 1 ] ],
>   [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 1, 1 ] ] ]
>
> gap> slfp:=Source(slhom);
> <fp group on the generators [ t12, t13, t21, t23, t31, t32 ]>
> gap> slmat:=Range(slhom);
> <matrix group with 6 generators>
>
> Consider e.g. as homomorphism the reduction modulo 3.
>
>
> red:=GroupHomomorphismByImagesNC(slmat,GL(3,3),GeneratorsOfGroup(slmat),List(GeneratorsOfGroup(slmat),x->x*Z(3)^0));
>
> Now pull this back to the f.p. group  (Note that I use
> `ImagesRepresentative to avoid triggering a membership test in `slmat'
> which would run forever.
>
>
> hom:=GroupHomomorphismByImages(slfp,Range(red),GeneratorsOfGroup(slfp),List(GeneratorsOfGroup(slfp),
>              x->ImagesRepresentative(red,ImagesRepresentative(slhom,x))));
>
> Now we could calculate a kernel of `hom':
>
> k:=Kernel(hom);
>
> gens:=GeneratorsOfGroup(k);;  # can take very long if large index !
> Length(gens);
>
> kermats:=List(gens,x->ImagesRepresentative(slhom,x)); # matrices that
> generate the kernel
>
> [Yes, in the best of all worlds all of this magic would happen
> automatically, but there are actually a lot of subtle points involved in
> doing so, not least whether you actually always would want kernel
> generators]
>
> All the best,
>
>    Alexander
>
>
> SLNZFP:=function(n)
> local t,geni,m,gens,f,rels,i,j,k,l,mat,mats,id;
>   t:=function(i,j)
>     return gens[geni[i][j]];
>   end;
>   geni:=List([1..n],x->[]);
>   mats:=[];
>   id:=IdentityMat(n,1);
>   m:=0;
>   gens:=[];
>   for i in [1..n] do
>     for j in [1..n] do
>       if j<>i then
>         m:=m+1;
>         geni[i][j]:=m;
>         Add(gens,Concatenation("t",String(i),String(j)));
>         mat:=List(id,ShallowCopy);
>         mat[i][j]:=1;
>         Add(mats,mat);
>       fi;
>     od;
>   od;
>   f:=FreeGroup(gens);
>   gens:=GeneratorsOfGroup(f);
>   rels:=[];
>   for i in [1..n] do
>     for j in Difference([1..n],[i]) do
>       for k in Difference([1..n],[j]) do
>         for l in Difference([1..n],[i,k]) do
>           if i>k or j>l then
>             Add(rels,Comm(t(i,j),t(k,l)));
>           fi;
>         od;
>         if k<>i then
>           Add(rels,Comm(t(i,j),t(j,k))/t(i,k));
>         fi;
>       od;
>     od;
>   od;
>   Add(rels,(t(1,2)/t(2,1)*t(1,2))^4);
>   t:=f/rels;
>   m:=Group(mats);
>   return GroupHomomorphismByImages(t,m,GeneratorsOfGroup(t),mats);
> end;
>
>
>
>
>