[GAP Forum] Computing kernel

Mathieu Dutour mathieu.dutour at gmail.com
Wed Apr 23 13:00:47 BST 2014


Dear all,

I have a 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 ?

The problem happens already when we take GL2 and the
determinant representation, which is my primary example, though
not the only one.

Any help would be appreciated.

  Mathieu

PS: Below, the example that shows the problem and an attempt solution
at it in the particular case of a permutation representation to Sym(2).
I do not claim optimality, but I think it is correct.

TestGL:=function(n)
  local TheG, ListGen, ListPerm, eGen, eDet, Sym2, phi, TheKer;
  TheG:=GL(n, Integers);
  ListGen:=GeneratorsOfGroup(TheG);
  ListPerm:=[];
  for eGen in ListGen
  do
    eDet:=DeterminantMat(eGen);
    if eDet=1 then
      Add(ListPerm, ());
    else
      Add(ListPerm, (1,2));
    fi;
  od;
  Sym2:=SymmetricGroup(2);
  Print("Before computing phi\n");
  phi:=GroupHomomorphismByImagesNC(TheG, Sym2, ListGen, ListPerm);
  Print("Before computing TheKer\n");
  TheKer:=Kernel(phi);
  Print("After computing TheKer\n");
  return rec(phi:=phi, TheKer:=TheKer);
end;



GetIndexOneTwoKernelOfMapping:=function(GRP1, GRP2, ListGens1, ListGens2)
  local nbGen, ListPosPlus, ListPosMinus, ListGenRet, x1, TheId, eGenMinus,
eGenPlus, List1, List2, i1, i2;
  if First(ListGens2, x->x<>() and x<>(1,2))<>fail then
    Error("The ListGens2 must be only () or (1,2)");
  fi;
  if GRP2<>SymmetricGroup(2) then
    Error("The second group must be SymmetricGroup(2)");
  fi;
  nbGen:=Length(ListGens2);
  ListPosPlus:=Filtered([1..nbGen], x->ListGens2[x]=());
  ListPosMinus:=Filtered([1..nbGen], x->ListGens2[x]=(1,2));
  if Length(ListPosMinus)=0 then
    return GRP1;
  fi;
  ListGenRet:=ListGens1{ListPosPlus};
  x1:=ListGens1[ListPosMinus[1]];
  TheId:=Identity(GRP1);
  for eGenMinus in ListGens1{ListPosMinus}
  do
    for eGenPlus in Concatenation(ListPosPlus, TheId)
    do
      List1:=[eGenMinus, Inverse(eGenMinus)];
      List2:=[x1, Inverse(x1)];
      for i1 in [1,2]
      do
        for i2 in [1,2]
        do
          Add(ListGenRet, List1[i1]*eGenPlus*List2[i2]);
          Add(ListGenRet, List2[i2]*eGenPlus*List1[i1]);
        od;
      od;
    od;
  od;
  return Group(ListGenRet);
end;


More information about the Forum mailing list