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;
_______________________________________________
Forum mailing list
[email protected]
http://mail.gap-system.org/mailman/listinfo/forum
