[GAP Forum] Computing kernel

[Alexander Hulpke]

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;