|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Frank Celler.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains the methods for matrix groups.
##
#############################################################################
##
#M KnowsHowToDecompose( <mat-grp> )
##
InstallMethod( KnowsHowToDecompose, "matrix groups",
[ IsMatrixGroup, IsList ], ReturnFalse );
#############################################################################
##
#M DefaultFieldOfMatrixGroup( <mat-grp> )
##
InstallMethod(DefaultFieldOfMatrixGroup,"for a matrix group",[IsMatrixGroup],
function( grp )
local gens,R;
gens:= GeneratorsOfGroup( grp );
if IsEmpty( gens ) then
return Field( One( grp )[1,1] );
else
R:=DefaultScalarDomainOfMatrixList(gens);
if not IsField(R) then
R:=FieldOfMatrixList(gens);
fi;
fi;
return R;
end );
InstallMethod( DefaultFieldOfMatrixGroup,
"for matrix group over the cyclotomics",
[ IsCyclotomicMatrixGroup ],
grp -> Cyclotomics );
InstallMethod( DefaultFieldOfMatrixGroup,
"for a matrix group over an s.c. algebra",
[ IsMatrixGroup and IsSCAlgebraObjCollCollColl ],
grp -> ElementsFamily( ElementsFamily( ElementsFamily(
FamilyObj( grp ) ) ) )!.fullSCAlgebra );
# InstallOtherMethod( DefaultFieldOfMatrixGroup,
# "from source of nice monomorphism",
# [ IsMatrixGroup and HasNiceMonomorphism ],
# grp -> DefaultFieldOfMatrixGroup( Source( NiceMonomorphism( grp ) ) ) );
#T this was illegal,
#T since it assumes that the source is a different object than the
#T original group; if this fails then we run into an infinite recursion!
#############################################################################
##
#M FieldOfMatrixGroup( <mat-grp> )
##
InstallMethod( FieldOfMatrixGroup,
"for a matrix group",
[ IsMatrixGroup ],
function( grp )
local gens;
gens:= GeneratorsOfGroup( grp );
if IsEmpty( gens ) then
return Field( One( grp )[1,1] );
else
return FieldOfMatrixList(gens);
fi;
end );
#############################################################################
##
#M DimensionOfMatrixGroup( <mat-grp> )
##
InstallMethod( DimensionOfMatrixGroup, "from generators",
[ IsMatrixGroup and HasGeneratorsOfGroup ],
function( grp )
if not IsEmpty( GeneratorsOfGroup( grp ) ) then
return NumberRows( GeneratorsOfGroup( grp )[1] );
else
TryNextMethod();
fi;
end );
InstallMethod( DimensionOfMatrixGroup, "from one",
[ IsMatrixGroup and HasOne ], 1,
grp -> NumberRows( One( grp ) ) );
# InstallOtherMethod( DimensionOfMatrixGroup,
# "from source of nice monomorphism",
# [ IsMatrixGroup and HasNiceMonomorphism ],
# grp -> DimensionOfMatrixGroup( Source( NiceMonomorphism( grp ) ) ) );
#T this was illegal,
#T since it assumes that the source is a different object than the
#T original group; if this fails then we run into an infinite recursion!
#T why not delegate to `Representative' instead of installing
#T different methods?
#############################################################################
##
#M TransposedMatrixGroup( <G> ) . . . . . . . . .transpose of a matrix group
##
InstallMethod( TransposedMatrixGroup,
[ IsMatrixGroup ],
function( G )
local T;
T := GroupByGenerators( List( GeneratorsOfGroup( G ), TransposedMat ),
One( G ) );
#T avoid calling `One'!
UseIsomorphismRelation( G, T );
SetTransposedMatrixGroup( T, G );
return T;
end );
#############################################################################
##
#F NaturalActedSpace( [<G>,]<acts>,<veclist> )
##
InstallGlobalFunction(NaturalActedSpace,function(arg)
local f,i,j,veclist,acts;
veclist:=arg[Length(arg)];
acts:=arg[Length(arg)-1];
if Length(arg)=3 and IsGroup(arg[1]) and acts=GeneratorsOfGroup(arg[1]) then
f:=DefaultFieldOfMatrixGroup(arg[1]);
else
f:=FieldOfMatrixList(acts);
fi;
for i in veclist do
for j in i do
if not j in f then
f:=ClosureField(f,j);
fi;
od;
od;
return f^Length(veclist[1]);
end);
InstallGlobalFunction(BasisVectorsForMatrixAction,function(G)
local F, gens, evals, espaces, is, ise, gen, i, j,module,list,ind,vecs,mins;
F := DefaultFieldOfMatrixGroup(G);
# `Cyclotomics', the default field for rational matrix groups causes
# problems with a subsequent factorization
if IsIdenticalObj(F,Cyclotomics) then
# cyclotomics really is too large here
F:=FieldOfMatrixGroup(G);
fi;
list:=[];
if false and ValueOption("nosubmodules")=fail and IsFinite(F) then
module:=GModuleByMats(GeneratorsOfGroup(G),F);
if not MTX.IsIrreducible(module) then
mins:=Filtered(MTX.BasesCompositionSeries(module),x->Length(x)>0);
if Length(mins)<=5 then
mins:=MTX.BasesMinimalSubmodules(module);
else
if Length(mins)>7 then
mins:=mins{Set([1..7],x->Random(1,Length(mins)))};
fi;
fi;
# now get potential basis vectors from submodules
for i in mins do
ind:=MTX.InducedActionSubmodule(module,i);
vecs:=BasisVectorsForMatrixAction(Group(ind.generators):nosubmodules);
Append(list,vecs*i);
od;
fi;
fi;
# use Murray/OBrien method
gens := ShallowCopy( GeneratorsOfGroup( G ) ); # Need copy for mutability
while Length( gens ) < 10 do
Add( gens, PseudoRandom( G ) );
od;
evals := []; espaces := [];
for gen in gens do
evals := Concatenation( evals, GeneralisedEigenvalues(F,gen) );
espaces := Concatenation( espaces, GeneralisedEigenspaces(F,gen) );
od;
is:=[];
# the `AddSet' wil automatically put small spaces first
for i in [1..Length(espaces)] do
for j in [i+1..Length(espaces)] do
ise:=Intersection(espaces[i],espaces[j]);
if Dimension(ise)>0 and not ise in is then
Add(is,ise);
fi;
od;
od;
Append(list,Concatenation(List(is,i->BasisVectors(Basis(i)))));
return list;
end);
#############################################################################
##
#F DoSparseLinearActionOnFaithfulSubset( <G>,<act>,<sort> )
##
## computes a linear action of the matrix group <G> on the span of the
## standard basis. The action <act> must be `OnRight', or
## `OnLines'. The calculation of further orbits stops, once a basis for the
## underlying space has been reached, often giving a smaller degree
## permutation representation.
## The boolean <sort> indicates, whether the domain will be sorted.
BindGlobal("DoSparseLinearActionOnFaithfulSubset",
function(G,act,sort)
local field, dict, acts, start, j, zerov, zero, dim, base, partbas, heads,
orb, delay, permimg, maxlim, starti, ll, ltwa, img, v, en, p, kill,
i, lo, imgs, xset, hom, R;
field:=DefaultFieldOfMatrixGroup(G);
acts:=GeneratorsOfGroup(G);
if Length(acts)=0 then
start:= RowsOfMatrix( One( G) );
elif act=OnRight then
start:= Concatenation( BasisVectorsForMatrixAction( G ),
RowsOfMatrix( One( G ) ) );
elif act=OnLines then
j:=One(G);
start:=Concatenation(List(BasisVectorsForMatrixAction(G),
x->OnLines(x,j)),j);
else
Error("illegal action");
fi;
start:=List(start,x->ImmutableVector(field,x));
zerov:=Zero(start[1]);
zero:=zerov[1];
dim:=Length(zerov);
base:=[]; # elements of start which are a base in the permgrp sense
partbas:=[]; # la basis of space spanned so far
heads:=[];
orb:=[];
delay:=[]; # Vectors we delay later, because they are potentially very
# expensive.
permimg:=List(acts,i->[]);
maxlim:=200000;
starti:=1;
while Length(partbas)<dim or
(act=OnLines and not OnLines(Sum(base),One(G)) in orb) do
Info(InfoGroup,2,"dim=",Length(partbas)," ",
"|orb|=",Length(orb));
if Length(partbas)=dim and act=OnLines then
Info(InfoGroup,2,"add sum for projective action");
img:=OnLines(Sum(base),One(G));
else
if starti>Length(start) then
Sort(delay);
for i in delay do
Add(start,i[2]);
od;
maxlim:=maxlim*100;
Info(InfoGroup,2,
"original pool exhausted, use delayed. maxlim=",maxlim);
delay:=[];
fi;
ll:=Length(orb);
ltwa:=Maximum(maxlim,(ll+1)*20);
img:=start[starti];
v:=ShallowCopy(img);
for j in [ 1 .. Length( heads ) ] do
en:=v[heads[j]];
if en <> zero then
AddRowVector( v, partbas[j], - en );
fi;
od;
fi;
if not IsZero(v) then
# do not go positional dictionary if we know it to be overkill
if HasSize(G) then
dict := NewDictionary( v, true , field ^ Length( One( G ))
:blistlimi:=Maximum(10,Size(field))*Size(G) );
else
dict := NewDictionary( v, true , field ^ Length( One( G ) ) );
fi;
# force `img' over field
if (Size(field)=2 and not IsGF2VectorRep(img)) or
(Size(field)>2 and Size(field)<=256 and not (Is8BitVectorRep(img)
and Q_VEC8BIT(img)=Size(field))) then
img:=ShallowCopy(img);
ConvertToVectorRep(img,Size(field));
fi;
Add(orb,img);
p:=Length(orb);
AddDictionary(dict,img,Length(orb));
kill:=false;
# orbit algorithm with image keeper
while p<=Length(orb) do
i:=1;
while i<=Length(acts) do
img := act(orb[p],acts[i]);
v:=LookupDictionary(dict,img);
if v=fail then
if Length(orb)>ltwa then
Info(InfoGroup,2,"Very long orbit, delay");
Add(delay,[Length(orb)-ll,orb[ll+1]]);
kill:=true;
for p in [ll+1..Length(orb)] do
Unbind(orb[p]);
for i in [1..Length(acts)] do
Unbind(permimg[i][p]);
od;
od;
i:=Length(acts)+1;
p:=Length(orb)+1;
else
Add(orb,img);
AddDictionary(dict,img,Length(orb));
permimg[i][p]:=Length(orb);
fi;
else
permimg[i][p]:=v;
fi;
i:=i+1;
od;
p:=p+1;
od;
fi;
starti:=starti+1;
if not kill then
# break criterion: do we actually *want* more points?
i:=ll+1;
lo:=Length(orb);
while i<=lo do
v:=ShallowCopy(orb[i]);
for j in [ 1 .. Length( heads ) ] do
en:=v[heads[j]];
if en <> zero then
AddRowVector( v, partbas[j], - en );
fi;
od;
if v<>zerov then
Add(base,orb[i]);
Add(partbas,ShallowCopy(orb[i]));
# filter for vector objects, not compressed FF vectors
if ForAny(partbas,x->IsVectorObj(x) and not IsDataObjectRep(x)) then
partbas:=Matrix(BaseDomain(partbas[1]),partbas);
fi;
TriangulizeMat(partbas);
if IsMatrixObj(partbas) then
partbas:=ShallowCopy(RowsOfMatrix(partbas));
fi;
heads:=List(partbas,PositionNonZero);
if Length(partbas)>=dim then
# full dimension reached
i:=lo;
fi;
fi;
i:=i+1;
od;
fi;
od;
# Das Dictionary hat seine Schuldigkeit getan
Unbind(dict);
Info(InfoGroup,1,"found degree=",Length(orb));
# any asymptotic argument is pointless here: In practice sorting is much
# quicker than image computation.
if sort then
imgs:=Sortex(orb); # permutation we must apply to the points to be sorted.
# was: permimg:=List(permimg,i->OnTuples(Permuted(i,imgs),imgs));
# run in loop to save memory
for i in [1..Length(permimg)] do
permimg[i]:=Permuted(permimg[i],imgs);
permimg[i]:=OnTuples(permimg[i],imgs);
od;
fi;
#check routine
# Print("check!\n");
# for p in [1..Length(orb)] do
# for i in [1..Length(acts)] do
# img:=act(orb[p],acts[i]);
# v:=LookupDictionary(dict,img);
# if v<>permimg[i][p] then
# Error("wrong!");
# fi;
# od;
# od;
# Error("hier");
for i in [1..Length(permimg)] do
permimg[i]:=PermList(permimg[i]);
od;
if fail in permimg then
Error("not permutations");
fi;
xset:=ExternalSet( G, orb, acts, acts, act);
# when acting projectively the sum of the base vectors must be part of the
# base -- that will guarantee that we can distinguish diagonal from scalar
# matrices.
if act=OnLines then
if Length(base)<=dim then
Add(base,OnLines(Sum(base),One(G)));
fi;
fi;
# We know that the points corresponding to `start' give a base of the
# vector space. We can use
# this to get images quickly, using a stabilizer chain in the permutation
# group
SetBaseOfGroup( xset, base );
xset!.basePermImage:=List(base,b->PositionCanonical(orb,b));
hom := ActionHomomorphism( xset,"surjective" );
if act <> OnLines then
SetIsInjective(hom, true); # we know by construction that it is injective.
fi;
R:=Group(permimg,()); # `permimg' arose from `PermList'
SetBaseOfGroup(R,xset!.basePermImage);
if HasSize(G) and act=OnRight then
SetSize(R,Size(G)); # faithful action
fi;
SetRange(hom,R);
SetImagesSource(hom,R);
SetMappingGeneratorsImages(hom,[acts,permimg]);
# p:=RUN_IN_GGMBI; # no niceomorphism translation here
# RUN_IN_GGMBI:=true;
# SetAsGroupGeneralMappingByImages ( hom, GroupHomomorphismByImagesNC
# ( G, R, acts, permimg ) );
#
# SetFilterObj( hom, IsActionHomomorphismByBase );
# RUN_IN_GGMBI:=p;
if act=OnRight or act=OnPoints then
# only store for action on right. projective action needs is own call to
# `LinearActionBase' as this will set other needed parameters.
base:=ImmutableMatrix(field,base);
SetLinearActionBasis(hom,base);
fi;
return hom;
end);
#############################################################################
##
#M IsomorphismPermGroup( <mat-grp> )
##
BindGlobal( "NicomorphismOfGeneralMatrixGroup", function( grp,canon,sort )
local nice,img,module,b;
b:=SeedFaithfulAction(grp);
if canon=false and b<>fail then
Info(InfoGroup,1,"using predefined action seed");
# the user (or code) gave a seed for a faithful action
nice:=MultiActionsHomomorphism(grp,b.points,b.ops);
# don't be too clever if it is a matrix over a non-field domain
elif not IsField(DefaultFieldOfMatrixGroup(grp)) then
Info(InfoGroup,1,"over nonfield");
#nice:=ActionHomomorphism( grp,AsSSortedList(grp),OnRight,"surjective");
if canon then
nice:= SortedSparseActionHomomorphism( grp,
RowsOfMatrix( One( grp ) ) );
SetIsCanonicalNiceMonomorphism(nice,true);
else
nice:= SparseActionHomomorphism( grp,
RowsOfMatrix( One( grp ) ) );
nice:=nice*SmallerDegreePermutationRepresentation(Image(nice):cheap);
fi;
elif IsFinite(grp) and ( (HasIsNaturalGL(grp) and IsNaturalGL(grp)) or
(HasIsNaturalSL(grp) and IsNaturalSL(grp)) ) then
# for full GL/SL we get never better than the full vector space as domain
Info(InfoGroup,1,"is GL/SL");
return NicomorphismFFMatGroupOnFullSpace(grp);
elif canon then
Info(InfoGroup,1,"canonical niceo");
nice:= SortedSparseActionHomomorphism( grp,
RowsOfMatrix( One( grp ) ) );
SetIsCanonicalNiceMonomorphism(nice,true);
else
Info(InfoGroup,1,"act to find base");
nice:=DoSparseLinearActionOnFaithfulSubset( grp, OnRight, sort);
SetIsSurjective( nice, true );
img:=Image(nice);
if not IsFinite(DefaultFieldOfMatrixGroup(grp)) or
Length(GeneratorsOfGroup(grp))=0 then
module:=fail;
else
module:=GModuleByMats(GeneratorsOfGroup(grp),DefaultFieldOfMatrixGroup(grp));
fi;
#improve, unless not wanted
if ValueOption("cheap")<>true then
# try hard, unless absirr and orbit lengths at least 1/q^2 of domain --
#then we expect improvements to be of little help
if module<>fail and not (NrMovedPoints(img)>=
Size( DefaultFieldOfMatrixGroup( grp ) )^( NumberRows( One( grp ) )-2 )
and MTX.IsAbsolutelyIrreducible(module)) then
nice:=nice*SmallerDegreePermutationRepresentation(img:cheap);
else
nice:=nice*SmallerDegreePermutationRepresentation(img:cheap);
fi;
fi;
fi;
SetIsInjective( nice, true );
return nice;
end );
#############################################################################
##
#M IsomorphismPermGroup( <mat-grp> )
##
## We want to use a method based on 'NicomorphismOfGeneralMatrixGroup'
## for the finite matrix group <mat-grp>.
##
## If <mat-grp> does not know whether it is finite,
## there is currently no concurrent method,
## thus no rank shift is necessary for the method installation.
##
## If <mat-grp> knows to be finite, we want our method to beat the one for
## 'IsGroup and IsFinite and IsHandledByNiceMonomorphism'.
##
## Installing just *one* method (with requirement 'IsMatrixGroup') would be
## possible via (dynamic) upranking,
## but here we install our method twice, with the different requirements
## 'IsMatrixGroup' and 'IsMatrixGroup and IsFinite'.
## (Note that 'IsHandledByNiceMonomorphism' is implied by the latter,
## and that we apply the same downranking in the second installation
## that happens in the installation of the method for
## 'IsGroup and IsFinite and IsHandledByNiceMonomorphism';
## we could get rid of the two downrankings, but this might affect code
## that is not distributed with GAP.)
##
BindGlobal( "IsomorphismPermGroupForMatrixGroup",
function(G)
local map;
if HasNiceMonomorphism(G) and IsPermGroup(Range(NiceMonomorphism(G))) then
map:=NiceMonomorphism(G);
else
if not HasIsFinite(G) then
Info(InfoWarning,1,
"IsomorphismPermGroup: The group is not known to be finite");
fi;
map:=NicomorphismOfGeneralMatrixGroup(G,false,false);
SetNiceMonomorphism(G,map);
fi;
if IsIdenticalObj(Source(map),G) then
return map;
fi;
return GeneralRestrictedMapping(map,G,NiceObject(G));
end);
InstallMethod( IsomorphismPermGroup,
"matrix group",
[ IsMatrixGroup ],
IsomorphismPermGroupForMatrixGroup );
InstallMethod( IsomorphismPermGroup,
"finite matrix group",
[ IsMatrixGroup and IsFinite and IsHandledByNiceMonomorphism ],
# We do not want the upranking via 'IsHandledByNiceMonomorphism',
# analogous to the situation with the method for
# 'IsGroup and IsFinite and IsHandledByNiceMonomorphism'in
# 'lib/grpnice.gi'.
[ [ IsMatrixGroup and IsFinite ], 1 ],
IsomorphismPermGroupForMatrixGroup );
#############################################################################
##
#M NiceMonomorphism( <mat-grp> )
##
InstallMethod( NiceMonomorphism,"use NicomorphismOfGeneralMatrixGroup",
[ IsMatrixGroup and IsFinite ],
G->NicomorphismOfGeneralMatrixGroup(G,false,false));
#############################################################################
##
#M CanonicalNiceMonomorphism( <mat-grp> )
##
InstallMethod( CanonicalNiceMonomorphism, [ IsMatrixGroup and IsFinite ],
G->NicomorphismOfGeneralMatrixGroup(G,true,true));
#############################################################################
##
#F ProjectiveActionHomomorphismMatrixGroup(<G>)
##
InstallGlobalFunction(ProjectiveActionHomomorphismMatrixGroup,
G->DoSparseLinearActionOnFaithfulSubset(G,OnLines,true));
#############################################################################
##
#M GeneratorsSmallest(<finite matrix group>)
##
## This algorithm takes <bas>:=the points corresponding to the standard basis
## and then computes a minimal generating system for the permutation group
## wrt. this base <bas>. As lexicographical comparison of matrices is
## compatible with comparison of base images wrt. the standard base this
## also is the smallest (irredundant) generating set of the matrix group!
InstallMethod(GeneratorsSmallest,"matrix group via niceo",
[IsMatrixGroup and IsFinite],
function(G)
local gens,s,dom,mon,no;
mon:=CanonicalNiceMonomorphism(G);
no:=Image(mon,G);
dom:=UnderlyingExternalSet(mon);
s:=StabChainOp(no,rec(base:=List(BaseOfGroup(dom),
i->Position(HomeEnumerator(dom),i))));
# call the recursive function to do the work
gens:= SCMinSmaGens( no, s, [], One( no ), true ).gens;
SetMinimalStabChain(G,s);
return List(gens,i->PreImagesRepresentative(mon,i));
end);
#############################################################################
##
#M MinimalStabChain(<finite matrix group>)
##
## used for cosets where we probably won't need the smallest generators
InstallOtherMethod(MinimalStabChain,"matrix group via niceo",
[IsMatrixGroup and IsFinite],
function(G)
local s,dom,mon,no;
mon:=CanonicalNiceMonomorphism(G);
no:=Image(mon,G);
dom:=UnderlyingExternalSet(mon);
s:=StabChainOp(no,rec(base:=List(BaseOfGroup(dom),
i->Position(HomeEnumerator(dom),i))));
# call the recursive function to do the work
SCMinSmaGens( no, s, [], One( no ), false );
return s;
end);
#############################################################################
##
#M LargestElementGroup(<finite matrix group>)
##
InstallOtherMethod(LargestElementGroup,"matrix group via niceo",
[IsMatrixGroup and IsFinite],
function(G)
local s,dom,mon, img;
mon:=CanonicalNiceMonomorphism(G);
dom:=UnderlyingExternalSet(mon);
img:= Image( mon, G );
s:=StabChainOp( img, rec(base:=List(BaseOfGroup(dom),
i->Position(HomeEnumerator(dom),i))));
# call the recursive function to do the work
s:= LargestElementStabChain( s, One( img ) );
return PreImagesRepresentative(mon,s);
end);
#############################################################################
##
#M CanonicalRightCosetElement(<finite matrix group>,<rep>)
##
InstallMethod(CanonicalRightCosetElement,"finite matric group",IsCollsElms,
[IsMatrixGroup and IsFinite,IsMatrix],
function(U,e)
local mon,dom,S,o,oimgs,p,i,g;
mon:=CanonicalNiceMonomorphism(U);
dom:=UnderlyingExternalSet(mon);
S:=StabChainOp(Image(mon,U),rec(base:=List(BaseOfGroup(dom),
i->Position(HomeEnumerator(dom),i))));
dom:=HomeEnumerator(dom);
while not IsEmpty(S.generators) do
o:=dom{S.orbit}; # the relevant vectors
oimgs:=List(o,i->i*e); #their images
# find the smallest image
p:=1;
for i in [2..Length(oimgs)] do
if oimgs[i]<oimgs[p] then
p:=i;
fi;
od;
# the point corresponding to the preimage
p:=S.orbit[p];
# now find an element that maps S.orbit[1] to p;
g:=S.identity;
while S.orbit[1]^g<>p do
g:=LeftQuotient(S.transversal[p/g],g);
od;
# change by corresponding matrix element
e:=PreImagesRepresentative(mon,g)*e;
S:=S.stabilizer;
od;
return e;
end);
#############################################################################
##
#M ViewObj( <matgrp> )
##
InstallMethod( ViewObj,
"for a matrix group with stored generators",
[ IsMatrixGroup and HasGeneratorsOfGroup ],
function(G)
local gens, nrgens;
gens:=GeneratorsOfGroup(G);
nrgens:=Length(gens);
if nrgens = 0 then
Print( "<matrix group of size 1>" );
elif nrgens * DimensionOfMatrixGroup(G)^2 / GAPInfo.ViewLength > 8 then
Print("<matrix group");
if HasSize(G) then
Print(" of size ",Size(G));
fi;
Print(" with ", Pluralize(nrgens, "generator"), ">");
else
Print("Group(");
ViewObj(gens);
Print(")");
fi;
end);
#############################################################################
##
#M ViewObj( <matgrp> )
##
InstallMethod( ViewObj,"for a matrix group",
[ IsMatrixGroup ],
function(G)
local d;
d:=DimensionOfMatrixGroup(G);
Print("<group of ",d,"x",d," matrices");
if HasSize(G) then
Print(" of size ",Size(G));
fi;
if HasFieldOfMatrixGroup(G) then
Print(" over ",FieldOfMatrixGroup(G),">");
elif HasDefaultFieldOfMatrixGroup(G) then
Print(" over ",DefaultFieldOfMatrixGroup(G),">");
else
Print(" in characteristic ",Characteristic(One(G)),">");
fi;
end);
#############################################################################
##
#M PrintObj( <matgrp> )
##
InstallMethod( PrintObj,"for a matrix group",
[ IsMatrixGroup ],
function(G)
local l;
l:=GeneratorsOfGroup(G);
if Length(l)=0 then
Print("Group([],",One(G),")");
else
Print("Group(",l,")");
fi;
end);
#############################################################################
##
#M IsGeneralLinearGroup(<G>)
##
InstallMethod(IsGeneralLinearGroup,"try natural",[IsMatrixGroup],
function(G)
if HasIsNaturalGL(G) and IsNaturalGL(G) then
return true;
else
TryNextMethod();
fi;
end);
#############################################################################
##
#M IsSubgroupSL
##
InstallMethod(IsSubgroupSL,"determinant test for generators",
[IsMatrixGroup and HasGeneratorsOfGroup],
G -> ForAll(GeneratorsOfGroup(G),i->IsOne(DeterminantMat(i))) );
#############################################################################
##
#M RespectsQuadraticForm( <Q>, <M> ) . . . . . . . . . . is form invariant?
##
## Let <Q> be the matrix of a quadratic form, and let <M> be a matrix of the
## same dimensions.
## The value of the form at the vector $v$ is $v <Q> v^{tr}$.
## If we define the matrix $i<Q>'$ by
## $<Q>'[i,i] = <Q>[i,i]$,
## $<Q>'[i,j] = 0$ for $i > j$,
## $<Q>'[i,j] = <Q>[i,j] + <Q>[j,i]$ for $i < j$,
## then $v <Q> v^{tr} = v <Q>' v^{tr}$ holds for all $v$.
## By definition, <M> leaves the form invariant
## if $v <M> <Q> <M>^{tr} v^{tr} = v <Q> v^{tr}$ holds for all $v$.
## This happens if and only if $(<M> <Q> <M>^{tr})' = <Q>'$ holds.
## (For the "only if" part,
## take the $i$-th standard basis vector $e_i$ to check the equality
## of the $i$-th diagonal element,
## and take $e_i + e_j$ to check the equality of the entry in position
## $(i,j)$.)
##
BindGlobal( "RespectsQuadraticForm", function( Q, M )
local Qimg;
Qimg:= M * Q * TransposedMat( M );
return ForAll( [ 1 .. NumberRows( M ) ],
i -> Q[i,i] = Qimg[i,i] and
ForAll( [ 1 .. i-1 ],
j -> Q[i,j] + Q[j,i] = Qimg[i,j] + Qimg[j,i] ) );
end );
#############################################################################
##
#M <mat> in <G> . . . . . . . . . . . . . . . . . . . . is form invariant?
##
InstallMethod( \in, "respecting quadratic form", IsElmsColls,
[ IsMatrix, IsFullSubgroupGLorSLRespectingQuadraticForm ],
{} -> RankFilter( IsHandledByNiceMonomorphism ), # override nice mon. method
# this method is better than the one using a nice monom.;
# it has the same rank as the method based on the inv.
# bilinear form, which is cheaper to check,
# thus we install the current method first
function( mat, G )
return IsSubset( FieldOfMatrixGroup( G ), FieldOfMatrixList( [ mat ] ) )
and ( not IsSubgroupSL( G ) or IsOne( DeterminantMat( mat ) ) )
and RespectsQuadraticForm( InvariantQuadraticForm( G ).matrix, mat );
end );
InstallMethod( \in, "respecting bilinear form", IsElmsColls,
[ IsMatrix, IsFullSubgroupGLorSLRespectingBilinearForm ],
{} -> RankFilter( IsHandledByNiceMonomorphism ), # override nice mon. method
function( mat, G )
local inv;
if not IsSubset( FieldOfMatrixGroup( G ), FieldOfMatrixList( [ mat ] ) )
or ( IsSubgroupSL( G ) and not IsOne( DeterminantMat( mat ) ) ) then
return false;
fi;
inv:= InvariantBilinearForm(G).matrix;
return mat * inv * TransposedMat( mat ) = inv;
end );
InstallMethod( \in, "respecting sesquilinear form", IsElmsColls,
[ IsMatrix, IsFullSubgroupGLorSLRespectingSesquilinearForm ],
{} -> RankFilter( IsHandledByNiceMonomorphism ), # override nice mon. method
function( mat, G )
local pow, inv;
if not IsSubset( FieldOfMatrixGroup( G ), FieldOfMatrixList( [ mat ] ) )
or ( IsSubgroupSL( G ) and not IsOne( DeterminantMat( mat ) ) ) then
return false;
fi;
pow:= RootInt( Size( FieldOfMatrixGroup( G ) ) );
inv:= InvariantSesquilinearForm(G).matrix;
return mat * inv * List( TransposedMat( mat ),
row -> List( row, x -> x^pow ) )
= inv;
end );
#############################################################################
##
#M IsGeneratorsOfMagmaWithInverses( <matlist> )
##
## Check that all entries are matrices of the same dimension, and that they
## are all invertible.
##
InstallMethod( IsGeneratorsOfMagmaWithInverses,
"for a list of matrices",
[ IsRingElementCollCollColl ],
function( matlist )
local nrows, ncols;
if IsList( matlist ) and ForAll( matlist, IsMatrixOrMatrixObj ) then
nrows:= NumberRows( matlist[1] );
ncols:= NumberColumns( matlist[1] );
return nrows = ncols and
ForAll( matlist,
mat -> NumberRows( mat ) = nrows and
NumberColumns( mat ) = ncols ) and
ForAll( matlist, mat -> Inverse( mat ) <> fail );
fi;
return false;
end );
#############################################################################
##
#M GroupWithGenerators( <mats> )
#M GroupWithGenerators( <mats>, <id> )
##
InstallMethod( GroupWithGenerators,
"list of matrices",
[ IsFFECollCollColl ],
#T ???
function( gens )
local G,f;
if not IsFinite(gens) then TryNextMethod(); fi;
f:=DefaultScalarDomainOfMatrixList(gens);
gens:=List(gens,i->ImmutableMatrix(f,i));
G:=MakeGroupyObj(FamilyObj(gens), IsGroup and IsFinite, gens,false);
if IsField(f) then SetDefaultFieldOfMatrixGroup(G,f);fi;
return G;
end );
InstallMethod( GroupWithGenerators,
"list of matrices with identity", IsCollsElms,
[ IsFFECollCollColl,IsMultiplicativeElementWithInverse and IsFFECollColl],
function( gens, id )
local G,f;
if not IsFinite(gens) then TryNextMethod(); fi;
f:=DefaultScalarDomainOfMatrixList(gens);
gens:=List(gens,i->ImmutableMatrix(f,i));
id:=ImmutableMatrix(f,id);
G:=MakeGroupyObj(FamilyObj(gens), IsGroup and IsFinite, gens,id);
if IsField(f) then SetDefaultFieldOfMatrixGroup(G,f);fi;
return G;
end );
InstallMethod( GroupWithGenerators,
"empty list of matrices with identity", true,
[ IsList and IsEmpty,
IsMultiplicativeElementWithInverse and IsFFECollColl],
function( gens, id )
local G,f;
f:=DefaultScalarDomainOfMatrixList([id]);
id:=ImmutableMatrix(f,id);
G:=MakeGroupyObj(FamilyObj([id]), IsGroup and IsTrivial, gens,id);
if IsField(f) then SetDefaultFieldOfMatrixGroup(G,f);fi;
return G;
end );
# ditto for nonprime ZmodnZ
InstallMethod( GroupWithGenerators, "list of zmodnz matrices",
[ IsZmodnZObjNonprimeCollCollColl ],
#T ???
function( gens )
local G,f;
if not IsFinite(gens) then TryNextMethod(); fi;
f:=DefaultScalarDomainOfMatrixList(gens);
gens:=List(gens,i->ImmutableMatrix(f,i));
G:=MakeGroupyObj(FamilyObj(gens), IsGroup and IsFinite, gens, false);
if IsField(f) then SetDefaultFieldOfMatrixGroup(G,f);fi;
return G;
end );
InstallMethod( GroupWithGenerators,
"list of zmodnz matrices with identity", IsCollsElms,
[ IsZmodnZObjNonprimeCollCollColl,IsMultiplicativeElementWithInverse and
IsZmodnZObjNonprimeCollColl],
function( gens, id )
local G,f;
if not IsFinite(gens) then TryNextMethod(); fi;
f:=DefaultScalarDomainOfMatrixList(gens);
gens:=List(gens,i->ImmutableMatrix(f,i));
id:=ImmutableMatrix(f,id);
G:=MakeGroupyObj(FamilyObj(gens), IsGroup and IsFinite, gens, id);
if IsField(f) then SetDefaultFieldOfMatrixGroup(G,f);fi;
return G;
end );
InstallMethod( GroupWithGenerators,
"empty list of zmodnz matrices with identity", true,
[ IsList and IsEmpty,
IsMultiplicativeElementWithInverse and IsZmodnZObjNonprimeCollColl],
function( gens, id )
local G,f;
f:=DefaultScalarDomainOfMatrixList([id]);
id:=ImmutableMatrix(f,id);
G:=MakeGroupyObj(FamilyObj([id]), IsGroup and IsTrivial, gens, id);
if IsField(f) then SetDefaultFieldOfMatrixGroup(G,f);fi;
return G;
end );
#############################################################################
##
#M IsConjugatorIsomorphism( <hom> )
##
InstallMethod( IsConjugatorIsomorphism,
"for a matrix group general mapping",
[ IsGroupGeneralMapping ], 1,
# There is no filter to test whether source and range of a homomorphism
# are matrix groups.
# So we have to test explicitly and make this method
# higher ranking than the default one in `ghom.gi'.
function( hom )
local s, r, dim, Fs, Fr, F, genss, rep;
s:= Source( hom );
if not IsMatrixGroup( s ) then
TryNextMethod();
elif not ( IsGroupHomomorphism( hom ) and IsBijective( hom ) ) then
return false;
elif IsEndoGeneralMapping( hom ) and IsInnerAutomorphism( hom ) then
return true;
fi;
r:= Range( hom );
# Check whether dimensions and fields of matrix entries are compatible.
dim:= DimensionOfMatrixGroup( s );
if dim <> DimensionOfMatrixGroup( r ) then
return false;
fi;
Fs:= DefaultFieldOfMatrixGroup( s );
Fr:= DefaultFieldOfMatrixGroup( r );
if FamilyObj( Fs ) <> FamilyObj( Fr ) then
return false;
fi;
if not ( IsField( Fs ) and IsField( Fr ) ) then
TryNextMethod();
fi;
F:= ClosureField( Fs, Fr );
if not IsFinite( F ) then
TryNextMethod();
fi;
# Compute a conjugator in the full linear group.
genss:= GeneratorsOfGroup( s );
rep:= RepresentativeAction( GL( dim, Size( F ) ), genss, List( genss,
i -> ImagesRepresentative( hom, i ) ), OnTuples );
# Return the result.
if rep <> fail then
Assert( 1, ForAll( genss, i -> Image( hom, i ) = i^rep ) );
SetConjugatorOfConjugatorIsomorphism( hom, rep );
return true;
else
return false;
fi;
end );
#############################################################################
##
#F AffineActionByMatrixGroup( <M> )
##
InstallGlobalFunction( AffineActionByMatrixGroup, function(M)
local gens,V, G, A;
# build the vector space
V := DefaultFieldOfMatrixGroup( M ) ^ DimensionOfMatrixGroup( M );
# the linear part
G := Action( M, V );
# the translation part
gens:=List( Basis( V ), b -> Permutation( b, V, \+ ) );
# construct the affine group
A := GroupByGenerators(Concatenation(gens,GeneratorsOfGroup( G )));
SetSize( A, Size( M ) * Size( V ) );
if HasName( M ) then
SetName( A, Concatenation( String( Size( DefaultFieldOfMatrixGroup( M ) ) ),
"^", String( DimensionOfMatrixGroup( M ) ), ":",
Name( M ) ) );
fi;
# the !.matrixGroup component is not documented!
A!.matrixGroup := M;
#T what the hell shall this misuse be good for?
return A;
end );
#############################################################################
##
## n. Code needed for ``blow up isomorphisms'' of matrix groups
##
#############################################################################
##
#F IsBlowUpIsomorphism
##
## We define this filter for additive as well as for multiplicative
## general mappings,
## so the ``respectings'' of the mappings must be set explicitly.
##
DeclareFilter( "IsBlowUpIsomorphism", IsSPGeneralMapping and IsBijective );
#############################################################################
##
#M ImagesRepresentative( <iso>, <mat> ) . . . . . for a blow up isomorphism
##
InstallMethod( ImagesRepresentative,
"for a blow up isomorphism, and a matrix in the source",
FamSourceEqFamElm,
[ IsBlowUpIsomorphism, IsMatrix ],
function( iso, mat )
return BlownUpMat( Basis( iso ), mat );
end );
#############################################################################
##
#M PreImagesRepresentative( <iso>, <mat> ) . . . for a blow up isomorphism
##
InstallMethod( PreImagesRepresentative,
"for a blow up isomorphism, and a matrix in the range",
FamRangeEqFamElm,
[ IsBlowUpIsomorphism, IsMatrix ],
function( iso, mat )
local B,
d,
n,
Binv,
preim,
i,
row,
j,
submat,
elm,
k;
B:= Basis( iso );
d:= Length( B );
n:= NumberRows( mat ) / d;
if not IsInt( n ) then
return fail;
fi;
Binv:= List( B, Inverse );
preim:= [];
for i in [ 1 .. n ] do
row:= [];
for j in [ 1 .. n ] do
# Compute the entry in the `i'-th row in the `j'-th column.
submat:= mat{ [ 1 .. d ] + (i-1)*d }{ [ 1 .. d ] + (j-1)*d };
elm:= Binv[1] * LinearCombination( B, submat[1] );
# Check that the matrix is in the image of the isomorphism.
for k in [ 2 .. d ] do
if B[k] * elm <> LinearCombination( B, submat[k] ) then
return fail;
fi;
od;
row[j]:= elm;
od;
preim[i]:= row;
od;
return preim;
end );
#############################################################################
##
#F BlowUpIsomorphism( <matgrp>, <B> )
##
InstallGlobalFunction( "BlowUpIsomorphism", function( matgrp, B )
local gens,
preimgs,
imgs,
range,
iso;
gens:= GeneratorsOfGroup( matgrp );
if IsEmpty( gens ) then
preimgs:= [ One( matgrp ) ];
imgs:= [ IdentityMat( Length( preimgs[1] ) * Length( B ),
LeftActingDomain( UnderlyingLeftModule( B ) ) ) ];
range:= GroupByGenerators( [], imgs[1] );
else
preimgs:= gens;
imgs:= List( gens, mat -> BlownUpMat( B, mat ) );
range:= GroupByGenerators( imgs );
fi;
iso:= rec();
ObjectifyWithAttributes( iso,
NewType( GeneralMappingsFamily( FamilyObj( preimgs[1] ),
FamilyObj( imgs[1] ) ),
IsBlowUpIsomorphism
and IsGroupGeneralMapping
and IsAttributeStoringRep ),
Source, matgrp,
Range, range,
Basis, B );
return iso;
end );
#############################################################################
##
## stuff concerning invariant forms of matrix groups
#T add code for computing invariant forms,
#T and transforming matrices for normalizing the forms
#T (which is useful, e.g., for embedding the groups from AtlasRep into
#T the unitary, symplectic, or orthogonal groups in question)
##
#############################################################################
##
#M InvariantBilinearForm( <matgrp> )
##
InstallMethod( InvariantBilinearForm,
"for a matrix group with known `InvariantQuadraticForm'",
[ IsMatrixGroup and HasInvariantQuadraticForm ],
function( matgrp )
local Q;
Q:= InvariantQuadraticForm( matgrp ).matrix;
return rec( matrix:= ( Q + TransposedMat( Q ) ) );
end );
[ Dauer der Verarbeitung: 0.12 Sekunden
(vorverarbeitet)
]
|
