# "CompCAM" berechnet aus gegebener Permutationsdarstellung der Gruppe alle zugehoerigen # kollabierten Adjazenzmatrizen. # # Als Input wird erwartet: # 1.) Die Gruppe als Permutationsdarstellung gegeben. # 2.) Die Anzahl der Punkte auf denen operiert wird. # 3.) Der Gruppenname in Anf"uhrungsstrichen. # # Der Output besteht dann aus einer Liste von Matrizen, die als Liste # von Zeilen gegeben sind. CompCAM:=function(arg) local s, N, OrbitAndTransversal, RepresentativeFromTransversal, alpha, S, orbs, alphas, reps, r, mats, i, j, k, G, n, gens, record; # "OrbitAndTransversal" beschreibt einen Bahnalgorithmus. OrbitAndTransversal:=function(gens,pt) local orb,from,use,sort,i,g,img ; # Dieser besteht aus vier Listen "orb" (der Bahn des # Punktes "pt"), "from" (die Liste der Vorgaenger), # "use" (die Liste der Woerter) und "sort" (eine sortierte # Liste von "orb"). orb:=[pt]; from:=[fail]; use:=[fail]; sort:=[pt]; # In der Hauptschleife werden Bilder der Bahnpunkte unter # den Erzeugern berechnet, und falls sie neu sind, an die # richtigen Positionen der Listen angehaengt. for i in orb do for g in gens do img:=i^g; if not img in sort then AddSet(sort,img); Add(orb,img); Add(from,i); Add(use,Position(gens,g)); fi; od; od; # Die drei Listen "orb","from" und "use", die die Bahn # des Punktes "pt" eindeutig beschreiben, werden zurueck- # gegeben. return rec(orb:=orb, from:=from, use:=use); end; # "RepresentativeFromTransversal" ermittelt einen Repraesentanten der # Bahn, in der "pt2" liegt. RepresentativeFromTransversal:=function(record,gens,pt2) local rep,pos,orb,from,use; orb:=record.orb ; from:=record.from ; use:=record.use ; rep:=(); while pt2<>orb[1] do pos:= Position(orb,pt2); rep:=gens[use[pos]]*rep; pt2:=from[pos]; od; return rep; end; # Die Argumente werden eingelesen: # "arg[1]" ist die Gruppe "G", "arg[2]" die Anzahl # der Punkte "n" auf denen die max. Untergruppe operiert, # und "arg[3]" ist der Gruppename "N". # Optional kann als viertes Argument der Stabilisator # mitgegeben werden. G:=arg[1]; n:=arg[2]; N:=arg[3]; gens:=GeneratorsOfGroup(G); alpha:=n; # Falls der Stabilisator als Input gegeben wurde, wird er an # dieser Stelle "S" genannt. Anderenfalls # wird der Gruppenname "N" benoetigt, um aus der (in GAP # vorimplementieren) Charaktertafel der Gruppe die Gruppenordnung "s" # zu bestimmen. Mit "s" und durch den Aufruf StabChain kann nun # vorteilhaft der Stabilisator "S" berechnet werden. if Length(arg)=4 then S:=arg[4]; else s:=Size(CharacterTable(N)); StabChain(G,rec(random:=1,size:=s)); S:=Stabilizer(G,n); fi; # Die Bahnen "orbs" der Operation von S auf den Punkten 1..n # werden berechnet und die einzelnen Bahnen jeweils sortiert. orbs:=ShallowCopy(Orbits(S,[1..n])); for i in [1..Length(orbs)] do orbs[i]:=Set(orbs[i]); od; # Falls er existiert, wird ein Fixpunkt der Bahnen "orbs" an den Anfang der # Liste "orbs" geholt. if [n] in orbs then orbs:=Concatenation([[[n]], Difference(orbs,[[n]])]); else i:=First(orbs,x->Length(x)=1); orbs:=Concatenation([[i], Difference(orbs,[i])]); fi; alphas:=List(orbs,x->x[1]); reps:=[]; record:=OrbitAndTransversal(gens,alphas[1]); reps:=List(alphas,alphai->RepresentativeFromTransversal(record,gens,alphai)); r:=Length(orbs); # Die Matrizeneintraege werden berechnet. mats:=[]; for i in [1..r] do mats[i]:=[]; for k in [1..r] do mats[i][k]:=[]; for j in [1..r] do mats[i][k][j]:=Number(Intersection(orbs[j],OnTuples(orbs[i],reps[k]))); od; od; od; return mats; end;