#*************************************************************************** # Reps # Copyright (C) 2005 Peter Webb # Copyright (C) 2006 Peter Webb, Robert Hank, Bryan Simpkins # Copyright (C) 2007 Peter Webb, Dan Christensen, Brad Froehle # Copyright (C) 2020 Peter Webb, Moriah Elkin # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ # # The overall structure of the reps package was designed and most of it # written by Peter Webb , who is also the maintainer. # Contributions were made by # Dan Christensen, Roland Loetscher, Robert Hank, Bryan Simpkins, # Brad Froehle and others. #*************************************************************************** GroupRepOps:=rec(); CatRepOps:=rec(); ############################################################################# ## Rep(group,matrices,optional field) ## This function creates a representation provided the group is not the ## identity group and the representation is not the zero representation. ## Modification by Craig Corsi and Peter Webb (University of Minnesota) ## 2016 to allow the optional field argument. ############################################################################## Rep:=function(arg) local G, L, rep; G:=arg[1];L:=arg[2]; if L=[] then Error("Identity group encountered: creating representations is not properly set up for the identity group."); return; fi; rep:=rec( group:=G, genimages:=L, isRepresentation:=true, dimension:=Length(L[1]), operations:=GroupRepOps ); if Length(arg)=2 then rep.field:=Field(L[1][1]); else rep.field:=arg[3]; fi; return rep; end; ############################################################################## ## ## MakeIsoToPermGroup(rep) creates fields rep.permgroup and rep.isotopermgroup ## which are used by routines which are written to work only with permutation ## groups, typically involving an algorithm which goes down a stabilizer ## chain. ## ############################################################################## MakeIsoToPermGroup:=function(rep) if IsBound(rep.permgroup) then return; fi; rep.isotopermgroup:=IsomorphismPermGroup(rep.group); rep.permgroup:=Image(rep.isotopermgroup,rep.group); return; end; ############################################################################## ## ## SafeNullspaceMat(mat, F) returns a basis for the nullspace of mat, defined ## over F. This works also when the domain or codomain are the zero vector space. ## ############################################################################## SafeNullspaceMat:=function(mat, F) if mat=[] then return([]); fi; if mat[1]=[] then return(IdentityMat(Length(mat),F)); fi; return(NullspaceMat(mat)); end; ############################################################################## ## ## SafeBaseMat(M) returns a list a basis vectors for the space spanned ## by the rows of M. If M is an empty list, so M has no rows, or if ## the elements of M are empty lists, so M has no columns, then the ## empty list is returned. ## ############################################################################## SafeBaseMat:=function(M) if IsEmpty(M) or IsEmpty(M[1]) then return []; else return BaseMat(M); fi; end; ############################################################################## ## ## SafeIdentityMat(n, F) returns an nxn identity matrix over the field F. ## When n = 0, returns an empty list. ## ############################################################################## SafeIdentityMat:=function(n, F) if n=0 then return []; else return IdentityMat(n, F); fi; end; ############################################################################## ## ## SafeMatrixMult(A, B, n) returns the product of matrices A and B, ## where A is kxm and B is mxn. n is passed in because if B has no ## rows, then we can not determine n. ## ## If k=0, returns an empty list, i.e. the matrix with 0 rows and n columns. ## If n=0, returns the matrix with k rows and 0 columns. ## If m=0, then returns the kxn zero matrix. ## ############################################################################## SafeMatrixMult:=function(A, B, n) if IsEmpty(A) then # k = 0 return []; elif n=0 then # n = 0 return List(A, row->[]); elif IsEmpty(B) then # m = 0 return NullMat(Length(A), n); else return A*B; fi; end; ######################################################### ## SocleNullspaceMat(matrix, dimension, field) ## returns a list of vectors forming a basis for the nullspace of the matrix, ## and deals with the situation where the matrix may have no rows, etc. ## It is used in SocleSeries(rep); SafeNullspaceMat works in other instances. ## Written by Peter Webb July 2016. ######################################################### SocleNullspaceMat:=function(M,n,F) if n=0 or IsEmpty(M) then return SafeIdentityMat(n,F); else return NullspaceMat(M); fi; end; ############################################################################## ## ## InverseGenImages(rep) returns the list of matrices which are the inverses ## of the matrices in rep.genimages. Two algorithms were tried: in ## OldInverseGenImages, rather than invert the matrices, they ## are raised to a power Order(g)-1 for each generator g. In fact, it appears ## on testing this out that GAP is faster at doing x -> x^-1. ## ############################################################################## InverseGenImages:=function(rep) if IsBound(rep.inversegenimages) then return(rep.inversegenimages); fi; rep.inversegenimages:=List(rep.genimages, x->x^-1); return(rep.inversegenimages); end; OldInverseGenImages:=function(rep) local orders, inverses, i; if IsBound(rep.inversegenimages) then return(rep.inversegenimages); fi; orders:=List(GeneratorsOfGroup(rep.group),Order); inverses:=[]; for i in [1..Length(orders)] do if orders[i]=infinity then inverses[i]:=rep.genimages[i]^-1; else inverses[i]:=rep.genimages[i]^(orders[i]-1); fi; od; rep.inversegenimages:=inverses; return(inverses); end; ############################################################################## ## ## RepToMatGroup(rep) returns the matrix group which is the image of the ## representation. ## ############################################################################## RepToMatGroup:=function(phi) return(Group(phi.genimages,IdentityMat(phi.dimension,phi.field))); end; ############################################################################## ## ## TrivialRep(group,field) ## ## This works even when the group is the identity group. ## ############################################################################## TrivialRep:=function(group,field) local mats,onemat; onemat:=IdentityMat(1,field); mats:=List(GeneratorsOfGroup(group), g->onemat); return rec( group:=group, genimages:=mats, field:=field, dimension:=1, isRepresentation:=true, operations:=GroupRepOps ); end; ############################################################################## ## ## TrivialRepN(group,field,n): trivial action on n-dimensional vector space ## ## Code written by Dan Christensen, modified by Peter Webb Aug 2007 to work ## also with the identity group. ## ############################################################################## TrivialRepN:=function(group,field,n) local mats,mat; mat:=IdentityMat(n,field); mats:=List(GeneratorsOfGroup(group), g->mat); return rec( group:=group, genimages:=mats, field:=field, dimension:=1, isRepresentation:=true, operations:=GroupRepOps ); end; ############################################################################## ## ## ZeroGroupRep(group,field) ## ############################################################################## ZeroGroupRep:=function(group,field) return rec( group:=group, genimages:=List(GeneratorsOfGroup(group), g->[]), field:=field, dimension:=0, isRepresentation:=true, operations:=GroupRepOps ); end; ############################################################################## ## ## FixedPoints. . . . . produce a basis for the fixed points of a module ## ## Improvement by Dan Christensen of code originally by Peter Webb. ## ############################################################################## FixedPoints:=function(rep) local v, one, i, j; if IsBound(rep.fixedPoints) then return rep.fixedPoints; fi; if IsTrivial(rep.group) then return(IdentityMat(rep.dimension,rep.field)); fi; v:=[]; one:=One(rep.field); for i in [1..rep.dimension] do v[i] := Concatenation(List(rep.genimages, m->m[i])); for j in [0..Length(rep.genimages)-1] do v[i][i+rep.dimension*j] := v[i][i+rep.dimension*j] - one; od; od; v:=NullspaceMat(v); rep.fixedPoints:=v; return(v); end; ############################################################################## ## ## FixedQuotient(rep) returns a basis for augmentation ideal . module. ## Handles trivial groups and zero-dimensional reps. ## ############################################################################## FixedQuotient:=function(rep) local onemat, v; if IsBound(rep.fixedQuotient) then return rep.fixedQuotient; fi; onemat:=SafeIdentityMat(rep.dimension, rep.field); v:=Concatenation(List(rep.genimages, g->g - onemat)); v:=SafeBaseMat(v); rep.fixedQuotient:=v; return v; end; ############################################################################## ## ## SubFixedQuotient(rep, list of vecs) ## returns a basis for augmentation ideal . submodule spanned by the vecs. ## The span of the vecs must be a submodule, and this is not checked. ## Handles trivial groups, zero-dimensional reps and empty u. ## ############################################################################## SubFixedQuotient:=function(rep,u) local onemat, v; onemat:=SafeIdentityMat(rep.dimension, rep.field); v:=Concatenation(List(rep.genimages, g->SafeMatrixMult(u, g - onemat, rep.dimension))); return SafeBaseMat(v); end; ############################################################################# ## ## DualRep(rep) ## ## Updated Aug 2007 by Peter Webb using the function InverseGenImages. ## ############################################################################## DualRep := function(rep) if rep.dimension=0 then return(rep); fi; return rec( group:=rep.group, genimages:=List(InverseGenImages(rep), TransposedMat), field:=rep.field, dimension:=rep.dimension, isRepresentation:=true, operations:=GroupRepOps ); end; ############################################################################## ## ## TensorProductMatrix(mat,mat) . . . Tensor product of two matrices ## ## The GAP command KroneckerProduct seems inexplicably slow and in tests on ## two 60 x 60 matrices takes about twice as long as the following code. ## ############################################################################## TensorProductMatrix:=function(A,B) local u, v, matrix; matrix:=[]; for u in A do for v in B do Add(matrix,Flat(List(u,x->x*v))); od; od; return(matrix); end; ############################################################################## ## ## TensorProductRep(rep,rep) . . . Kronecker product of two representations ## ## TensorProductGroupRep is called by TensorProductRep(rep,rep) when rep is a ## group representation. ## ############################################################################## TensorProductRep:=function(g,h) return g.operations.TensorProductRep(g,h); end; TensorProductGroupRep:=function(g,h) local mgens; if g.group <> h.group then Error("You must have two representations of the same group"); return; fi; mgens:=List([1..Length(g.genimages)], i->TensorProductMatrix(g.genimages[i],h.genimages[i])); return Rep(g.group,mgens); end; OldTensorProductRep:=function(g,h) local mgens; if g.group <> h.group then Error("You must have two representations of the same group"); return; fi; mgens:=List([1..Length(g.genimages)], i->KroneckerProduct(g.genimages[i],h.genimages[i])); return Rep(g.group,mgens); end; ############################################################################## ## ## TensorProductMorphism(M1,M2) Kronecker product of two morphisms ## ## Function introduced August 2007 by Dan Christensen. ## ############################################################################## TensorProductMorphism:=function(M1,M2) return TensorProductMatrix(M1,M2); end; OldTensorProductMorphism:=function(M1,M2) return KroneckerProduct(M1,M2); end; ############################################################################# ## ## SubmoduleRep(rep, list of vecs) . . returns the representation that gives ## the action on an invariant subspace. The list of vectors must be a basis ## for an invariant subspace. This is not checked. ## ## The code was tidied up by Dan Christensen Aug 2007 with the use of List ## and made to work for the identity group by Peter Webb Aug 2007. ## In Feb 2020 Peter Webb changed Size(rep.group) to rep.dimension, apparently ## correcting an error. ## ## SubmoduleGroupRep is called by SubmoduleRep(rep, list of vecs) when rep is a ## group representation. ## ############################################################################# SubmoduleRep:=function(rep,v) return rep.operations.SubmoduleRep(rep,v); end; SubmoduleGroupRep:=function(rep,v) local vs,base,newimages,g; vs:=VectorSpace(rep.field,v,[1..rep.dimension]*Zero(rep.field)); base:=Basis(vs,v); newimages:=[]; for g in rep.genimages do Add(newimages, List(base, b->Coefficients(base, b*g))); od; return rec( group:=rep.group, genimages:=newimages, field:=rep.field, dimension:=Length(base), isRepresentation:=true, operations:=GroupRepOps ); end; ############################################################################# ## ## QuotientRep(rep, list of vecs) . . . returns the representation giving the ## action on the quotient by an invariant subspace. ## ## The code includes a correction made by Roland Loetscher in March 2007 and ## was made to work for the identity group by Peter Webb in August 2007. ## ## QuotientGroupRep is called by QuotientRep(rep, list of vecs) when rep is a ## group representation. ## ############################################################################# QuotientRep:=function(rep,v) return rep.operations.QuotientRep(rep,v); end; QuotientGroupRep:=function(rep,v) local base,d,n,zero,onemat,i,positions,b,p,g, mat,newb,newimages,baseinverse, vs, tempbase; if Length(v)=0 then return rep; fi; base:=ShallowCopy(BaseMat(v)); TriangulizeMat(base); d:=Length(base); n:=rep.dimension; if d=n then return ZeroGroupRep(rep.group,rep.field); fi; zero:=Zero(rep.field); onemat:=IdentityMat(n,rep.field); i:=1; positions:=[]; for b in base do while b[i]=zero do Add(positions,i); i:=i+1; od; i:=i+1; od; Append(positions,[i..n]); for p in positions do Add(base, onemat[p]); od; baseinverse:=base^-1; newimages:=[]; for g in rep.genimages do mat:=[]; for p in positions do b:=g[p]*baseinverse; newb:=[]; for i in [d+1..n] do Add(newb,b[i]); od; Add(mat,newb); od; Add(newimages, mat); od; return rec( group:=rep.group, genimages:=newimages, field:=rep.field, dimension:=n-d, isRepresentation:=true, operations:=GroupRepOps ); end; ######################################################### ## SectionRep(rep, list of vectors, list of vectors) returns the representation ## on the quotient of the submodule spanned by the first list of vectors, by ## the submodule spanned by the second list of vectors. ## The two lists should be independent sets, and should be bases for ## submodules of rep, the second submodule contained in the first. ## This is not checked. ## Written by Peter Webb July 2016. ######################################################### SectionRep:=function(rep,vectorsa,vectorsb) local repa, v, b, newvecsb ; repa:=SubmoduleRep(rep,vectorsa); v:=VectorSpace(rep.field,vectorsa, [1..rep.dimension]*Zero(rep.field)); b:=Basis(v,vectorsa); newvecsb:=List(vectorsb,x->Coefficients(b, x)); return(QuotientRep(repa,newvecsb)); end; ############################################################################# ## ##PermutationMatrix(perm,d,field) We specify d so that the permutation is ## regarded as permuting [1..d] ## ############################################################################# PermutationMatrix:=function(perm,d, field) local m, p; m:=NullMat(d,d,field); for p in [1..d] do m[p][p^perm]:=One(field); od; return(m); end; ############################################################################# ## ## PermToMatrixGroup( permgrp, field ) . . transforms a permutation group ## to a group of permutation matrices ## ############################################################################# ## PermToMatrixGroup := function( permgrp, field ) ## ## local matrix, g, p, d, mgens; ## ## d := LargestMovedPoint(permgrp); ## mgens:=[]; ## for g in GeneratorsOfGroup(permgrp) do ## matrix:=NullMat(d,d,field); ## for p in [1..d] do ## matrix[p][p^g]:=One(field); ## od; ## Add(mgens,matrix); ## od; ## return(Group(mgens)); ## end; ############################################################################# ## ## PermGroupToRep . . transforms a permutation group to a permutation ## representation ############################################################################# PermGroupToRep := function( permgrp, field ) local matrix, g, p, d, mgens; d := LargestMovedPoint(permgrp); mgens:=[]; for g in GeneratorsOfGroup(permgrp) do matrix:=NullMat(d,d,field); for p in [1..d] do matrix[p][p^g]:=One(field); od; Add(mgens,matrix); od; return(Rep(permgrp,mgens)); end; ############################################################################## ## ## Pretty print for matrices ## ############################################################################## DisplayMatrix := function (A) PrintArray (List (A, x -> List (x, Int))); end; ############################################################################## ## ## PrintRep(rep) prints a representation nicely. ## ############################################################################## PrintRep:=function ( M ) local g; if IsBound( M.name ) then Print( M.name ); elif IsBound(M.longprint) and M.longprint then Print( "Representation( ", M.group, ", ", M.genimages, " )\n" ); else Print( "Representation( ", M.group, ", Images \n"); for g in M.genimages do DisplayMatrix(g); od; Print( " )\n" ); fi; end; ############################################################################## ## ## CanRightRep(group,subgroup,list of elements, element) ## returns the first element in the list which represents the same ## coset as the element. ## It does not verify the validity of its input. ## ############################################################################## CanRightRep:=function(G,H,L,g) local h,k; h:=g^-1; for k in L do if k*h in H then return k; fi; od; end; ############################################################################## ## ## RightCosetReps(group,subgroup) gives a list of representatives of the ## right cosets of a group relative to a given subgroup. ## ############################################################################## RightCosetReps:=function(G,H) return List(RightCosets(G,H), Representative); end; ## The function that gives the permutation representation of an element g ## on a list L of right cosets of a subgroup has a built-in definition as ## Permutation(g,L,OnRightCosets), but the problem is that L has to be a list ## whose elements are themselves lists, each containing the elements of ## a Right Coset (Cosets are not lists). ############################################################################## ## ## GLG(n,q) is a generalized version of GeneralLinearGroup ## which does accept the case of dimension 1. ## ############################################################################## GLG:= function(n,q) if n=1 then return(Group(Z(q)*IdentityMat(1,GF(q)))); else return(GeneralLinearGroup(n,q)); fi; end; ############################################################################## ## ## RepToGHBI(rep) turns a representation into a GroupHomomorphismByImages ## with the corresponding data. ## ############################################################################## RepToGHBI:=function(phi) local glg,h; glg:=GLG(phi.dimension,Size(phi.field)); h:=GroupHomomorphismByImagesNC(phi.group,glg, GeneratorsOfGroup(phi.group),phi.genimages); # h.isMapping:=true; # h.isHomomorphism:=true; # h.isGroupHomomorphism:=true; return h; end; ############################################################################ ## ## ## InducedRep(group, subgroup, rep of subgroup) computes the induction ## of a rep from a subgroup to a group. ## ## In more detail, InducedRep(G, H, M) is M tensor_{kH} kG. ## If m_1, ..., m_n is the standard basis for M and g_1, ..., g_r ## are the coset representatives of the set {Hg} of right cosets, ## then the basis chosen for the induced representation is ## ## m_1 tensor g_1, m_2 tensor g_1, ..., m_n tensor g_1, ## m_1 tensor g_2, m_2 tensor g_2, ..., m_n tensor g_2, ## ... ## m_1 tensor g_r, m_2 tensor g_r, ..., m_n tensor g_r, ## ## in that order. ## ############################################################################ InducedRep:=function(G,H,phi) local L,n,F,R,Q,g,i,j,h,S,k,l,ghbiphi; ghbiphi:=RepToGHBI(phi); R:=[]; n:=phi.dimension; F:=phi.field; L:=RightCosetReps(G,H); for g in GeneratorsOfGroup(G) do Q:=NullMat(n*Length(L),n*Length(L),F); for i in [1..Length(L)] do j:=Position(L,CanRightRep(G,H,L,L[i]*g)); h:=L[i]*g*(L[j]^-1); S:=ImagesRepresentative(ghbiphi,h); for k in [1..n] do for l in [1..n] do Q[k+(i-1)*n][l+(j-1)*n]:=S[k][l]; od; od; od; Add(R, Q); od; return Rep(G,R); end; ############################################################################ ## ## InducedMorphism(group, subgroup, matrix) computes the induced ## homomorphism of a map between representations of the subgroup. ## ## Code written by Dan Christensen, University of Western Ontario,August 2007 ## ############################################################################ InducedMorphism:=function(G,H,S) local index; index := Index(G,H); return BlockMatrix(List([1..index], i->[i,i,S]), index, index); # Alternate implementation: # K := figure out the field # return KroneckerProduct(IdentityMat(index, K), S) end; ############################################################################ ## ## InducedInclusion(group, subgroup, rep of subgroup) computes the natural ## homomorphism from rep to RestrictedRep(G, H, InducedRep(G, H, rep)). ## With the basis conventions chosen here, this is just a matrix of the ## form [ I | Z ], where I is an identity matrix and Z is a zero matrix. ## ## ## Code written by Dan Christensen, University of Western Ontario,August 2007 ## ############################################################################ InducedInclusion:=function(G,H,phi) local dim, index, M, F, i; F := phi.field; dim := phi.dimension; index := Index(G,H); M := NullMat(dim, dim*index, F); for i in [1..dim] do M[i][i] := One(F); od; return M; end; ############################################################################ ## ## InducedProjection(group, subgroup, rep of subgroup) computes the natural ## projection from RestrictedRep(G, H, InducedRep(G, H, rep)) to rep. ## With the basis conventions chosen here, this is just a matrix of the ## form [ I ], where I is an identity matrix and Z is a zero matrix. ## [ Z ] ## ## Code written by Dan Christensen, University of Western Ontario,August 2007 ## ############################################################################ InducedProjection:=function(G,H,phi) local dim, index, M, F, i; F := phi.field; dim := phi.dimension; index := Index(G,H); M := NullMat(dim*index, dim, F); for i in [1..dim] do M[i][i] := One(F); od; return M; end; ############################################################################ ## ## IsHom(rep1, rep2, mat) returns true if the matrix mat represents a ## homomorphism from rep1 to rep2. Quite useful for testing. ## ## Code written by Dan Christensen, University of Western Ontario,August 2007 ## ############################################################################ IsHom := function(rep1, rep2, mat) local i; if rep1.group <> rep2.group then Error("You must have two representations of the same group"); return; fi; for i in [1..Length(rep1.genimages)] do if rep1.genimages[i] * mat <> mat * rep2.genimages[i] then return false; fi; od; return true; end; ######################################################### ## PermutationRepOnCosets:=function(group,subgroup,field) returns the representation ## which is the permutation module determined by the right cosets ## of the subgroup in the group. ## Modification by Craig Corsi (University of Minnesota) ## 2016 to make sure the field is correctly recorded. ## ######################################################### PermutationRepOnCosets:=function(G,H,F) local n,L,M,phi,g,i,j,R,glg,k; L:=[]; R:=[]; L:=RightCosets(G,H); n:=Length(L); for k in [1..Length(GeneratorsOfGroup(G))] do g:=GeneratorsOfGroup(G)[k]; M:=NullMat(n,n,F); for i in [1..n] do j:=0; repeat j:=j+1; until L[i]*g=L[j]; M[i][j]:=Z(Size(F))^0; od; R[k]:=M; od; phi:=Rep(G,R,F); return phi; end; ############################################################################## ## ## RegularRep:=function(group, field) returns the group ring as a ## representation. ## ## The basis is given by the elements of G, in the order given ## by RightCosetReps(G, Group(Identity(G)), which is not necessarily ## the order given by Elements(G). ## ## Code written by Dan Christensen, University of Western Ontario,August 2007 ## ############################################################################## RegularRep:=function(G, field) return PermutationRepOnCosets(G, Group(Identity(G)), field); end; ############################################################################## ## ## FreeRep:=function(group, field, n) returns the direct sum of n copies ## of the group ring as a representation. ## ## Code written by Dan Christensen, University of Western Ontario,August 2007 ## ############################################################################## FreeRep:=function(G, field, n) return TensorProductRep(TrivialRepN(G, field, n), RegularRep(G, field)); end; ############################################################################## ## ## PermutationRep(group,list of permns,field) returns the representation ## on the permutation module determined by the permutation representation ## in which the group generators act as the permutations in the list. ## ############################################################################## PermutationRep:=function(group,perms,field) local d; d:=Maximum(List(perms,LargestMovedPointPerm)); return Rep(group,List(perms, x->PermutationMatrix(x,d,field))); end; ############################################################################## ## ## RelativeTrace(group,subgroup,rep) computes the matrix that corresponds to the mapping ## tr_Q^P(v)=v(sum gi), where Q is a subgroup ## of P, v is a vector in a P-representation phi, and the gi are a ## complete list of representatives of right cosets of Q in P. ## ## The real use of this function is to apply the mapping to vectors which ## are fixed by the subgroup, and then the result is fixed by the whole group. ## ## The algorithm is not very clever, and if the index of the subgroup is large ## it would be better to construct a chain of subgroups between the two groups ## and compute the relative trace as the product of the relative traces between ## pairs of groups in the chain. Such an algorithm is used in the command ## NormRep which returns the relative trace from the identity subgroup. ## ############################################################################## RelativeTrace:=function(P,Q,rep) local M,l,g,ghbi; M:=NullMat(rep.dimension,rep.dimension,rep.field); l:=RightCosetReps(P,Q); ghbi:=RepToGHBI(rep ); for g in l do M:=M+Image(ghbi,g); od; return M; end; ############################################################################## ## ## Spin(rep, veclist) returns a basis for the submodule generated by the ## vectors in veclist, which must be a list of vectors. ## ## GroupSpin is called by Spin(rep, veclist) when rep is a ## group representation. ## ############################################################################## Spin:=function(rep,veclist) return rep.operations.Spin(rep,veclist); end; GroupSpin:=function(rep,veclist) local basis, oldlength, newvecs, g,v; basis:=List(SafeBaseMat(veclist)); oldlength:=Length(basis)-1; while Length(basis) > oldlength do oldlength:=Length(basis); newvecs:=[]; for g in rep.genimages do for v in basis do Add(newvecs, v*g); od; od; Append(basis,newvecs); basis:=List(SafeBaseMat(basis)); od; return basis; end; ############################################################################## ## ## CoSpin(rep, veclist) . . .returns a basis for the largest submodule ## contained in the vector subspace spanned by veclist. ## ## GroupCoSpin is called by CoSpin(rep, veclist) when rep is a ## group representation. ## ############################################################################## CoSpin:=function(rep,veclist) return rep.operations.CoSpin(rep,veclist); end; GroupCoSpin:= function(rep,veclist) local u, fakerep; if Length(veclist)=0 then return(veclist); fi; u:=NullspaceMat(TransposedMat(veclist)); if Length(u)=0 then return(IdentityMat(rep.dimension,rep.field)); fi; fakerep:=ShallowCopy(rep); fakerep.genimages:=List(fakerep.genimages,TransposedMat); #Warning: fakerep is not a representation, because the genimages represent #the opposite group. u:= Spin(fakerep,u); u:= NullspaceMat(TransposedMat(u)); return(List(u,x->x)); end; ############################################################################## ## ## OldHomBasis(rep1,rep2) . . returns a basis for the space of ## module homomorphisms A -> B. The elements of this basis are matrices. ## ## This function is not as fast as the code for HomBasis written by ## Dan Christensen, which has a more straightforward setup matrix whose ## nullspace we find. ## ############################################################################## OldHomBasis:=function(g,h) local f, basis, i, j, m, u; f:=FixedPoints(TensorProductRep(DualRep(g),h)); basis:=[]; u:=[]; for m in f do for i in [1..g.dimension] do u[i]:=[]; for j in [1..h.dimension] do u[i][j]:=m[h.dimension*(i-1)+j]; od; od; Add(basis,ShallowCopy(u)); od; return(basis); end; ############################################################################## ## ## HomBasis(M, N) returns a basis for the space of ## kG-module homomorphisms M -> N. The elements of this basis are matrices. ## ## The algorithm used finds matrices X so that Xg-gX=0 for all group generators ## g. This sets up a linear algebra problem more efficiently than solving ## gXg^-1=X, and was observed independently by John Pliam (1993), ## Michael Smith (1993) and Dan Christensen (2007). ## This code written by Dan Christensen, August 2007. ## ## GroupHomBasis is called by HomBasis(M, N) when M is a ## group representation. ## ############################################################################## HomBasis:=function(M,N) return M.operations.HomBasis(M,N); end; GroupHomBasis:=function(M,N) local dimM, dimN, r, i, j, k, l, v, f, basis, m, u; dimM := M.dimension; dimN := N.dimension; r := Length(M.genimages); v:=NullMat(dimM*dimN, dimM*dimN*r, M.field); for i in [1..dimM] do for k in [1..dimN] do for l in [1..r] do for j in [1..dimM] do v[(j-1)*dimN+k][(l-1)*dimM*dimN+(i-1)*dimN+k] := v[(j-1)*dimN+k][(l-1)*dimM*dimN+(i-1)*dimN+k] + M.genimages[l][i][j]; od; for j in [1..dimN] do v[(i-1)*dimN+j][(l-1)*dimM*dimN+(i-1)*dimN+k] := v[(i-1)*dimN+j][(l-1)*dimM*dimN+(i-1)*dimN+k] - N.genimages[l][j][k]; od; od; od; od; f := NullspaceMat(v); basis:=[]; for m in f do u:=[]; for i in [1..M.dimension] do u[i]:=[]; for j in [1..N.dimension] do u[i][j]:=m[N.dimension*(i-1)+j]; od; od; Add(basis, u); od; return(basis); end; ############################################################################## ## ## DimHom(rep1,rep2) . . returns the dimension of the space of ## module homomorphisms rep1 -> rep2. ## ############################################################################## DimHom:=function(g,h) return Length(HomBasis(g,h)); end; ############################################################################## ## ## SumOfImages(rep,rep) . . returns a basis for the sum of images of all ## module homomorphisms A -> B ## ## GroupSumOfImages is called by SumOfImages(rep,rep) when rep is a ## group representation. ## ## Updated by Peter Webb Sep 11, 2007 ## ############################################################################## SumOfImages:=function(M,N) return M.operations.SumOfImages(M,N); end; GroupSumOfImages:=function(g,h) return SafeBaseMat(Concatenation(HomBasis(g,h))); end; ############################################################################## ## ## DecomposeSubmodule(repn, basis) . . probably returns a list of two bases ## for summands of ## the submodule of repn spanned by basis, if the module is decomposable, and ## if the module is indecomposable it returns a list whose only element is the ## given basis. ## ## GroupDecomposeSubmodule is called by DecomposeSubmodule(repn, basis) when repn ## is a group representation. ## ## This code was written by Bryan Simpkins and Robert Hank, University of ## Minnesota, April 2006. A related approach was taken by Michael Smith in ## code written in 1993. ## It was tidied up by Dan Christensen, University of Western Ontario, Aug 2007. ## In July 2016 Craig Corsi, University of Minnesota, made a change so that ## decompositions over fields larger than the field of definition of the ## representation are found. ## ############################################################################## DecomposeSubmodule:=function(M,basisstructure) return M.operations.DecomposeSubmodule(M,basisstructure); end; GroupDecomposeSubmodule:= function(repn, basis) local newrep, initlist, a, kernel, image, b, d, n, z; if Length(basis) <= 1 then return [basis]; fi; newrep := SubmoduleRep(repn, basis); z:=PrimitiveElement(repn.field); initlist := HomBasis(newrep,newrep); Add(initlist, 0 * initlist[1]); b := Length(initlist); while b > 0 do; d := b - 1; while d > 0 do; a := z*initlist[b] + initlist[d]; n := 1; while n < Length(basis) do; a:= a*a; n:= 2*n; od; kernel := NullspaceMat(a); if not(Length(kernel) = 0 or Length(kernel) = Length(basis)) then image := BaseMat(a); return [kernel * basis, image * basis]; fi; d := d - 1; od; b := b - 1; od; return [basis]; end; ############################################################################## ## ## DecomposeOnce(rep) . . probably returns a list of two bases for summands ## of the representation rep if it is decomposable, and returns a list whose ## only element is the standard basis if it is indecomposable. ## ## This code was written by Bryan Simpkins and Robert Hank, University of ## Minnesota, April 2006 ## ############################################################################## DecomposeOnce:= function(rep) return DecomposeSubmodule(rep, IdentityMat(rep.dimension, rep.field)); end; ############################################################################## ## ## Decompose(rep) . . returns a list of bases of direct summands of rep which ## are probably indecomposable. ## ## DecomposeGroupRep is called by Decompose(rep) when rep ## is a group representation. ## ## This code was written by Bryan Simpkins and Robert Hank, University of ## Minnesota, April 2006. ## It was modified by Dan Christensen and Peter Webb August 2007 so that indecomposable ## representations are only checked once (before they were checked twice), ## so as to use space more economically, and so that the result is stored ## in rep.summands. ## ############################################################################## Decompose:=function(rep) return rep.operations.Decompose(rep); end; DecomposeGroupRep:= function(rep) local summands, result, q; if IsBound(rep.summands) then return(rep.summands); fi; summands := [IdentityMat(rep.dimension,rep.field)]; q := 1; # We maintain the following invariants: # - summands is a list of lists of vectors; the union of these # lists forms a basis for rep.field^(rep.dimension). # - the summands at positions < q appear to be indecomposable; # those at positions >= q haven't been investigated completely. while IsBound(summands[q]) do; result := DecomposeSubmodule(rep, summands[q]); if Length(result) = 2 then summands[q] := result[1]; Add(summands, result[2]); else q := q + 1; fi; od; rep.summands:=summands; return summands; end; ############################################################################## ## ## MatsOfCosetReps(rep) . . returns a list ## ## [rep of a proper subgroup, ## list of matrices of right coset representatives of the subgroup, ## list of right coset representatives of the subgroup]. ## ## The coset representatives are a Schreier ## transversal for the stabilizer of a point, and the stabilizer subgroup has Schreier ## generators for the stabilizer. At the same time matrices which ## represent the elements which arise are stored. ## ## This function is called by NormRep, MatrixOfElement and RestrictedRep. ## ############################################################################## MatsOfCosetReps:=function(rep) local s, orbit, positions, mats, inversemats, perms, gens, q, x, j, ximage, table, subgroupgens, subgroupgenimages; s:=SmallestMovedPoint(rep.group); orbit:=[s]; positions:=[]; mats:=[]; mats[s]:=IdentityMat(rep.dimension,rep.field); inversemats:=[]; inversemats[s]:=IdentityMat(rep.dimension,rep.field); perms:=[]; perms[s]:=(); gens:=GeneratorsOfGroup(rep.group); InverseGenImages(rep); table:=[]; for j in [1..Length(gens)] do table[j]:=[]; od; q:=1; while IsBound(orbit[q]) do x:=orbit[q]; for j in [1..Length(gens)] do ximage:=x^gens[j]; if not ximage in orbit then Add(orbit,ximage); positions[ximage]:=j; perms[ximage]:=perms[x]*gens[j]; mats[ximage]:=mats[x]*rep.genimages[j]; inversemats[ximage]:=rep.inversegenimages[j]*inversemats[x]; else table[j][x]:=perms[x]*gens[j]*perms[ximage]^-1; fi; od; q:=q+1; od; subgroupgens:=[]; subgroupgenimages:=[]; for j in [1..Length(gens)] do for x in orbit do if IsBound(table[j][x]) and Size(Group(subgroupgens,()))< Size(Group(Concatenation(subgroupgens,[table[j][x]]))) then Add(subgroupgens,table[j][x]); Add(subgroupgenimages,mats[x]*rep.genimages[j]*inversemats[x^gens[j]]); fi; od; od; return ([rec( group:=Group(subgroupgens,()), genimages:=subgroupgenimages, field:=rep.field, dimension:=rep.dimension, isRepresentation:=true, operations:=GroupRepOps ), mats,perms]); end; ############################################################################## ## ## NormRep(rep) . . returns the matrix which represents the sum of the group ## elements. ## ## NormRep calls MatsOfCosetReps recursively until the subgroup is the identity group, and ## multiplies the sums of the matrices of the coset representatives. ## ############################################################################## NormRep:=function(rep) local output, newrep, temp, a, sum; output:=IdentityMat(rep.dimension,rep.field); MakeIsoToPermGroup(rep); newrep:=rec( group:=rep.permgroup, genimages:=rep.genimages, field:=rep.field, dimension:=rep.dimension, isRepresentation:=true, operations:=GroupRepOps ); while Size(newrep.group)>1 do temp:=MatsOfCosetReps(newrep); newrep:=temp[1]; sum:=NullMat(rep.dimension,rep.dimension,rep.field); for a in temp[2] do sum:=sum+a; od; output:=sum*output; od; return output; end; OldNormRep:= function(rep) local p, currentgroup, stablist, subgroup, replist, norm; currentgroup := rep.group; p := RepToGHBI(rep); norm := IdentityMat(rep.dimension,rep.field); while not IsTrivial(currentgroup) do; stablist := StabChain(currentgroup); subgroup := Subgroup(currentgroup,stablist.stabilizer.generators); replist := RightCosetReps(currentgroup, subgroup); replist := List( replist, x -> ImagesRepresentative(p, x)); norm := Sum(replist) * norm; currentgroup := subgroup; od; return norm; end; ############################################################################## ## ## MatrixOfElement(rep,group element) returns the matrix which represents ## the group element. ## ############################################################################## MatrixOfElement:=function(rep,g) local newrep, newg, mat, s, temp; MakeIsoToPermGroup(rep); newrep:=rec( group:=rep.permgroup, genimages:=rep.genimages, field:=rep.field, dimension:=rep.dimension, isRepresentation:=true, operations:=GroupRepOps ); newg:=Image(rep.isotopermgroup,g); mat:=IdentityMat(rep.dimension,rep.field); while Size(newrep.group)>1 do s:=SmallestMovedPoint(newrep.group); temp:=MatsOfCosetReps(newrep); newrep:=temp[1]; mat:=temp[2][s^newg]*mat; newg:=newg*temp[3][s^newg]^-1; od; return(mat); end; ############################################################################## ## ## MatricesOfElements(rep,list of group elements) returns the list of matrices ## which represent the group elements. ## ############################################################################## MatricesOfElements:=function(rep,l) local newrep, newl, matlist, s, temp, x, n; MakeIsoToPermGroup(rep); newrep:=rec( group:=rep.permgroup, genimages:=rep.genimages, field:=rep.field, dimension:=rep.dimension, isRepresentation:=true, operations:=GroupRepOps ); n:=Length(l); newl:=List(l, x->Image(rep.isotopermgroup,x)); matlist:=List(l,x->IdentityMat(rep.dimension,rep.field)); while Size(newrep.group)>1 do s:=SmallestMovedPoint(newrep.group); temp:=MatsOfCosetReps(newrep); newrep:=temp[1]; matlist:=List([1..n], x->temp[2][s^newl[x]]*matlist[x]); newl:=List(newl,x->x*temp[3][s^x]^-1); od; return(matlist); end; ############################################################################## ## ## RestrictedRep(group, subgroup, rep of group) computes the restriction ## of a rep from a group to a subgroup. ## ## This code has been rewritten September 2007 by Peter Webb. ## The algorithm calls the function MatricesOfElements which finds the ## matrices representing the generators of the subgroup by working down a ## stabilizer chain for the group and at each stage computing matrices ## which represent the coset representatives of the stabilizer subgroups ## and also the generators of the stabilizers. This approach is more ## economical that expressing each subgroup generator as a word in the ## generators of the big group and then evaluating that word on matrices, because ## in such words there are repeated subwords which get evaluated again and ## again. ## ## The previous implementation of this function appears as OldRestrictedRep. ## ################################################################################ RestrictedRep:=function(G,H,rep) local R; R:=MatricesOfElements(rep,GeneratorsOfGroup(H)); return rec( group:=H, genimages:=R, field:=rep.field, dimension:=rep.dimension, isRepresentation:=true, operations:=GroupRepOps ); end; OldRestrictedRep:=function(G,H,phi) local ghbiphi,R; ghbiphi:=RepToGHBI(phi); R:=List(GeneratorsOfGroup(H), g->ImagesRepresentative(ghbiphi, g)); return rec( group:=H, genimages:=R, field:=phi.field, dimension:=phi.dimension, isRepresentation:=true, operations:=GroupRepOps ); end; ############################################################################## ## ## SymmetricPowerRep(rep, n) computes the action of rep on the n-th symmetric power ## of the vector space V associated with rep. ## This routine was written by Brad Froehle at the University of Minnesota, January 2007. ## ############################################################################## SymmetricPowerRep := function(rep, n) local Sn; ## Define a function Sn which can be called repeatedly for each matrix corresponding to a generator of the group. Sn := function(A, n) local MyProduct, DualList, dimV, expEnd, dimOut, output, waysToSum, dual, i, j, l; ## MyProduct(A, x, y) ## ## Assumptions: A is a square n-by-n matrix, x and y are lists of the same length ## whose entries are elements of [1..n] ## ## Output: the product A[x[1]][y[1]] * A[x[2]][y[2]] * A[x[3]][y[3]] * ... ## MyProduct := function(A, x, y) local output, i; output := 1; for i in [1..Length(x)] do output := output * A[x[i]][y[i]]; od; return output; end; ## DualList(A) ## ## Assumptions: A is a list. ## ## Output: A list in which 1 is repeated A[1] times, 2 is repeated A[2] times, etc... ## DualList := function(A) local i, output; output := []; for i in [1..Length(A)] do Append(output, List([1..A[i]], x->i)); od; return output; end; ## Define some variables which are used repeatedly: ## * dimV is the dimension of the initial representation. ## * expEnd is a list whose elements describe all possible monomials of total degree dimV. ## * dimOut is the dimension of the output representation, i.e. the number of monomials in expEnd. ## dimV := Size(A); expEnd := Reversed(OrderedPartitions(dimV+n,dimV)-1); dimOut := Size(expEnd); ## Initialize output to a dimOut x dimOut matrix of all zeros ## output := []; for i in [1..dimOut] do output[i] := List([1..dimOut],x->0); od; ## Iterate, calculating each entry of output individually. ## for i in [1..dimOut] do # Because this next call (PermutationsList) might be slow, we calculate it as few times as possible. waysToSum := PermutationsList(DualList(expEnd[i])); for j in [1..dimOut] do # Calculate the ji-th entry here dual := DualList(expEnd[j]); for l in waysToSum do output[j][i] := output[j][i] + MyProduct(A, dual, l); od; od; od; return output; end; ## End function Sn. return Rep(rep.group, List(rep.genimages, x-> Sn(x,n))); end; ############################################################################## ## ## ProjectiveHomBasis(rep1,rep2) returns a list of matrices which form a basis for ## the space of module homomorphisms from rep1 to rep2 which factor through ## a projective module. The algorithm computes the image of the norm map ## applied to the representation Dual(rep1) tensor rep2. ## ############################################################################## ProjectiveHomBasis:=function(rep1,rep2) local f, basis, i, j, m, u; f:=SafeBaseMat(NormRep(TensorProductRep(DualRep(rep1),rep2))); basis:=[]; for m in f do u:=[]; for i in [1..rep1.dimension] do u[i]:=[]; for j in [1..rep2.dimension] do u[i][j]:=m[rep2.dimension*(i-1)+j]; od; od; Add(basis,u); od; return(basis); end; OldProjectiveHomBasis:=function(rep1,rep2) local f, basis, i, j, m, u; f:=SafeBaseMat(OldNormRep(TensorProductRep(DualRep(rep1),rep2))); basis:=[]; u:=[]; for m in f do for i in [1..rep1.dimension] do u[i]:=[]; for j in [1..rep2.dimension] do u[i][j]:=m[rep2.dimension*(i-1)+j]; od; od; Add(basis,ShallowCopy(u)); od; return(basis); end; ############################################################################## ## ## IsProjectiveMorphism(rep1, rep2, f) returns whether or not ## the morphism f: rep1 --> rep2 factors through a projective. ## f is assumed to be a kG-module homomorphism. ## ############################################################################## IsProjectiveMorphism:=function(M,N,f) local mat, n; mat:=ProjectiveHomBasis(M,N); n:=Length(mat); Add(mat,f); mat:=List(mat,Flat); return RankMat(mat)=n; end; ############################################################################## ## ## IsProjectiveRep(rep) returns true if the representation is a projective ## module, and false otherwise. The algorithm restricts the representation ## to a Sylow p-subgroup and tests whether |G| times the rank of the norm ## map equals the dimension of the representation. ## ############################################################################## IsProjectiveRep:=function(rep) local s, resrep, n; if Characteristic(rep.field)=0 then return(true); fi; s:=SylowSubgroup(rep.group, Characteristic(rep.field)); # s:=Subgroup(rep.group,SmallGeneratingSet(s)); This line is for permutation groups resrep:=RestrictedRep(rep.group, s, rep); n:=NormRep(resrep); if Rank(n)*Size(s) = rep.dimension then return(true); else return(false); fi; end; ############################################################################## ## ## ProjectiveFreeSummand(rep) returns a summand of rep which is probably ## projective free. The complementary summand is guaranteed to be ## projective, so the returned rep is stably isomorphic to the original rep. ## ############################################################################## ProjectiveFreeSummand:=function(M) local comps, comp, pfbasis; comps:=Decompose(M); pfbasis:=[]; for comp in comps do if not IsProjectiveRep(SubmoduleRep(M, comp)) then Append(pfbasis, comp); fi; od; return SubmoduleRep(M, pfbasis); end; ############################################################################## ## ## ProjectiveDecomposition(rep) returns a list of two bases, for a submodule ## which is projective, and for a submodule with probably no non-zero projective summands, ## whose direct sum is the whole representation. ## ############################################################################## ProjectiveDecomposition:=function(M) local comps, comp, pfbasis, pbasis; comps:=Decompose(M); pfbasis:=[]; pbasis:=[]; for comp in comps do if not IsProjectiveRep(SubmoduleRep(M, comp)) then Append(pfbasis, comp); else Append(pbasis, comp); fi; od; return ([pbasis,pfbasis]); end; ############################################################################## ## ## Interface to the Meataxe. ## ## In the following routines several of the meataxe commands available in GAP ## are converted so that they take representations as arguments and return ## representations, where the meataxe implementation would have returned ## meataxe modules. Clearly more of the meataxe commands could be implemented ## than is done below. ## ############################################################################## ############################################################################## ## ## MeataxeModuleToRep(rep,meataxemodule) converts a meataxe module to a ## representation. Because the meataxe module does not store the group ## being represented, this is obtained from a representation called rep ## whose only property is that rep.group is the required group. ## ############################################################################## MeataxeModuleToRep:=function(rep,meataxemodule) return(rec(group:=rep.group, genimages:=MTX.Generators(meataxemodule), field:=MTX.Field(meataxemodule), dimension:=MTX.Dimension(meataxemodule), isRepresentation:=true, operations:=GroupRepOps)); end; ############################################################################## ## ## RepToMeataxeModule(rep) converts a representation to a meataxe module. ## ############################################################################## RepToMeataxeModule:=function(rep) if rep.genimages=[] then return(GModuleByMats([], rep.dimension, rep.field )); elif rep.dimension=0 then return(GModuleByMats([], rep.dimension, rep.field )); else return(GModuleByMats(rep.genimages, rep.field )); fi; end; ############################################################################## ## ## ProperSubmodule(rep) calls the meataxe command MTX.ProperSubmoduleBasis ## and returns a basis for a proper submodule, or [] if there is none. ## ############################################################################## ProperSubmodule:=function(rep) local basis; if rep.dimension=0 then return([]); fi; basis:=(MTX.ProperSubmoduleBasis(RepToMeataxeModule(rep))); if basis=fail then return([]); fi; return(basis); end; IsIrreducibleRep:=function(rep) if rep.dimension=0 then return(false); fi; return(MTX.IsIrreducible(RepToMeataxeModule(rep))); end; IsAbsolutelyIrreducibleRep:=function(rep) if rep.dimension=0 then return(false); fi; return(MTX.IsAbsolutelyIrreducible(RepToMeataxeModule(rep))); end; BasesCompositionSeriesRep:=function(rep) if rep.dimension=0 then return([[]]); fi; return(MTX.BasesCompositionSeries((RepToMeataxeModule(rep)))); end; CompositionFactorsRep:=function(rep) local modules; if rep.dimension=0 then return([]); fi; modules:=MTX.CompositionFactors(RepToMeataxeModule(rep)); return(List(modules,x->MeataxeModuleToRep(rep,x))); end; RadicalRep:=function(rep) if rep.dimension=0 then return([]); fi; return(MTX.BasisRadical(RepToMeataxeModule(rep))); end; SocleRep:=function(rep) if rep.dimension=0 then return([]); fi; return(MTX.BasisSocle(RepToMeataxeModule(rep))); end; ########################################################## ## ## BrauerTraceImage(representation, p-subgroup of rep.group) returns a list ## of vectors that is a basis for the sum of the images of traces from proper ## subgroups of the p-group. Written by Peter Webb June 2016. ## ########################################################## BrauerTraceImage:=function(rep,p) local resp, resh, maxsub, image, h, M; resp:=RestrictedRep(rep.group,p,rep); maxsub:=MaximalSubgroups(p); image:=[]; for h in maxsub do M:=RelativeTrace(p,h,resp); resh:=RestrictedRep(resp.group,h,resp); Append(image,SafeMatrixMult(FixedPoints(resh),M,rep.dimension)); od; return(SafeBaseMat(image)); end; ########################################################## ## ## FixedPointRep(representation, subgroup of rep.group) returns the ## representation of the normalizer of the subgroup on the fixed points ## of the subgroup. Written by Peter Webb June 2016. ## ########################################################## FixedPointRep:=function(rep,gp) local n, resn, resgp; n:=Normalizer(rep.group,gp); resn:=RestrictedRep(rep.group,n,rep); resgp:=RestrictedRep(rep.group,gp,rep); return(SubmoduleRep(resn,FixedPoints(resgp))); end; ########################################################## ## ## BrauerRep(representation, p-subgroup of rep.group) returns the ## representation of the normalizer of the subgroup on the fixed points ## of the subgroup modulo the image of traces from proper subgroups of ## the p-group. Written by Peter Webb June 2016. ## ########################################################## BrauerRep:=function(rep,p) local n, resn, resp, fp, fprep, maxsub, traceimages, h, M, resh, v, b; n:=Normalizer(rep.group,p); resn:=RestrictedRep(rep.group,n,rep); resp:=RestrictedRep(rep.group,p,rep); fp:=FixedPoints(resp); fprep:=SubmoduleRep(resn,fp); maxsub:=MaximalSubgroups(p); traceimages:=[]; for h in maxsub do M:=RelativeTrace(p,h,resp); resh:=RestrictedRep(resp.group,h,resp); Append(traceimages,SafeMatrixMult(FixedPoints(resh),M,rep.dimension)); od; traceimages:=SafeBaseMat(traceimages); v:=VectorSpace(rep.field,fp); b:=Basis(v,fp); traceimages:=List(traceimages,x->Coefficients(b, x)); return QuotientRep(fprep, traceimages); end; ######################################################### ## ## RadicalSeries(rep) returns a list with two entries [bases, reps] where ## bases is a list of bases of the successive powers of the radical ## rep = rad^0(rep), rad^1(rep), ... ## in descending order. The last term in the list is the empty list. ## reps is a list of the representations on the radical quotients ## rep/rad^1(rep), rad^1(rep)/rad^2(rep). ... ## all of which are semisimple. The last term is the last nonzero ## representation, and so the list is one shorter than bases. ## Written by Peter Webb July 2016. ## ######################################################### RadicalSeries:=function(rep) local rad, i, submod, submodrad, layer; rad:=[];layer:=[]; rad[1]:=SafeIdentityMat(rep.dimension,rep.field); i:=1; while Length(rad[i])>0 do i:=i+1; submod:=SubmoduleRep(rep,rad[i-1]); submodrad:=RadicalRep(submod); rad[i]:=SafeMatrixMult(submodrad,rad[i-1],submod.dimension); layer[i-1]:=QuotientRep(submod,submodrad); od; return([rad,layer]); end; ######################################################### ## ## SocleSeries(rep) returns a list with two entries [bases, reps] where ## bases is a list of bases of the higher socles ## rep = soc^t(rep), soc^(t-1)(rep), ... ## in DESCENDING order. The last term in the list is the empty list. ## reps is a list of the representations on the socle quotients ## rep/soc^(t-1)(rep), soc^(t-1)(rep)/soc^(t-2)(rep). ... ## all of which are semisimple. The last term is the last nonzero ## representation, and so the list is one shorter than bases. ## Written by Peter Webb July 2016. ## ######################################################### SocleSeries:=function(rep) local radseries, n, temp, socseries, i; radseries:=RadicalSeries(DualRep(rep)); socseries:=[];socseries[1]:=[];socseries[2]:=[];temp:=[]; temp[1]:=List(radseries[1],y->SocleNullspaceMat(TransposedMat(y),rep.dimension,rep.field)); temp[2]:=List(radseries[2],DualRep); n:=Length(radseries[2]); for i in [1..n+1] do socseries[1][i]:=temp[1][n+2-i]; od; for i in [1..n] do socseries[2][i]:=temp[2][n+1-i]; od; return(socseries); end; ######################################################### ## ButterflyFactors(rep, descending filtration, descending filtration) ## returns a matrix whose entries are the representations that appear as ## sections in Zassenhaus' Butterfly Lemma. ## Each descending filtration is a list of bases of submodules of rep, forming ## a descending chain. The representations in the output are the factors in ## a common refinement of the two filtrations, fand their position in the ## refinement is indicated by their position in the matrix. ## Written by Peter Webb July 2016 ######################################################### ButterflyFactors:=function(rep,L1,L2) local factors, i, j, vecsa, vecsb; factors:=[]; for i in [1..Length(L1)-1] do factors[i]:=[]; for j in [1..Length(L2)-1] do vecsa:=SumIntersectionMat(L1[i],L2[j])[2]; vecsb:=SumIntersectionMat(SumIntersectionMat(L1[i+1],L2[j])[2], SumIntersectionMat(L1[i],L2[j+1])[2])[1]; factors[i][j]:=SectionRep(rep,vecsa,vecsb); od; od; return(factors); end; DirectSumRep:=function(rep1,rep2) return rep1.operations.DirectSumRep(rep1,rep2); end; ############################################################################## ## ## DirectSumGroupRep(rep1,rep2) returns the representation that is the direct sum of ## representations rep1 and rep2 for the same group. Written by Peter Webb February 2020. ## ## DirectSumGroupRep is called by DirectSumRep(rep1,rep2) when rep1 and rep2 are ## group representations. ## ############################################################################# DirectSumGroupRep:=function(rep1,rep2) local i, gimages, x, zerovec1, zerovec2, padded1, padded2; if rep1.field<>rep2.field or rep1.group<>rep2.group then Error("Representations incompatible."); fi; zerovec1:=Zero(rep1.field)*[1..rep1.dimension]; zerovec2:=Zero(rep2.field)*[1..rep2.dimension]; gimages:=[]; for i in [1..Length(rep1.genimages)] do padded1:=List(rep1.genimages[i],x->Concatenation(x,zerovec2)); padded2:=List(rep2.genimages[i],x->Concatenation(zerovec1,x)); gimages[i]:=Concatenation(padded1,padded2); od; return rec(group:=rep1.group, genimages:=gimages, field:=rep1.field, dimension:=rep1.dimension+rep2.dimension,isRepresentation:=true,operations:=GroupRepOps); end; ############################################################################## ## ## ProjectiveFreeCore(rep) returns the representation that is the largest direct summand of ## rep with not projective summand. It is only guaranteed to work when the group is a p-group ## in characteristic p. In other cases it may give a correct answer, and if it does not then an error ## message is returned. Written by Peter Webb February 2020. There is another function ## ProjectiveFreeSummand which invokes Decompose, and because of this will be more limited ## ############################################################################## ProjectiveFreeCore:=function(rep) local n, resrep, vectors, sub; resrep:=RestrictedRep(rep.group, SylowSubgroup(rep.group,Characteristic(rep.field)),rep); n:=NormRep(resrep); if Length(n)=0 then return(rep); fi; vectors:=BaseSteinitzVectors(IdentityMat(rep.dimension,rep.field),NullspaceMat(n)); sub:=Spin(rep,vectors.factorspace); if IsProjectiveRep(SubmoduleRep(rep,sub))=false then Error("The routine tried to factor out a non-projective module. It only works for p-groups."); return; fi; return(QuotientRep(rep,sub)); end; ############################################################################## ## ## ProjectiveSummand(rep) returns a basis for a maximal projective direct summand of ## rep. It is only guaranteed to work when the group is a p-group in characteristic p. ## In other cases it may give a correct answer, and if it does not then an error ## message is returned. It does not use Decompose. Written by Peter Webb February 2020. ## ############################################################################## ProjectiveSummand:=function(rep) local n, resrep, vectors, sub; resrep:=RestrictedRep(rep.group, SylowSubgroup(rep.group,Characteristic(rep.field)),rep); n:=NormRep(resrep); if Length(n)=0 then return(rep); fi; vectors:=BaseSteinitzVectors(IdentityMat(rep.dimension,rep.field),NullspaceMat(n)); sub:=Spin(rep,vectors.factorspace); if IsProjectiveRep(SubmoduleRep(rep,sub))=false then Error("The routine produced a basis called sub, for a submodule that is too big and not projective. It is only guaranteed to work for p-groups."); return; fi; return(sub); end; ###################################### ## ## IsIsomorphicSummand(rep1,rep2) only works when rep1 is indecomposable of dimension prime to the field characteristic. ## It returns true if rep1 is isomorphic to a direct summand of rep2, false otherwise. It relies on a result of Benson ## and Carlson. Written by Peter Webb Feb 2020. ## ###################################### IsIsomorphicSummand:=function(rep1,rep2) local hom, vecs, d; if rep1.dimension mod Characteristic(rep1.field) =0 then Error("The dimension needs to be prime to the characteristic."); return; fi; if rep1.dimension <> rep2.dimension then return false; fi; hom:=TensorProductRep(DualRep(rep1),rep2); vecs:=FixedQuotient(hom); d:=Length(vecs); vecs:=SafeBaseMat(Concatenation(vecs,FixedPoints(hom))); return Length(vecs) > d; end; ############################################################################## ## ## KernelIntersection(rep,rep) . . returns a basis for the intersection of the kernels of all ## module homomorphisms A -> B ## Created by Peter Webb May 8, 2019. Corrected April 18, 2020. ## This uses a version of SafeNullspaceMat with two arguments, the second being the field. ## ############################################################################## KernelIntersection:=function(g,h) local transposedmats; transposedmats:=List(HomBasis(g,h), TransposedMat); if Length(transposedmats)=0 then return(SafeIdentityMat(g.dimension, g.field)); else return SafeNullspaceMat(TransposedMat(Concatenation(transposedmats)),g.field); fi; end; ################################################ # # PrincipalIdempotent(group,prime) returns a vector in the representation space of # RegularRep(group, GF(prime)) that is the block idempotent of the principal block. Thus if b is # this idempotent and e denotes the vector in the regular representation corresponding to the # identity elements, the vector b.e is returned. Spinning it gives a basis for the principal block. # This idempotent is constructed using a formula of B. Kulshammer Arch. Math 56 (1991) 313-319. # Code written by Peter Webb February 2020. # ################################################ PrincipalIdempotent:=function(group,prime) local els, primepart, coeffs, pels, qels, qelspos, x, y, position; els:=RightCosetReps(group, Group(Identity(group))); primepart:=prime^LogInt(Size(group),prime); coeffs:=List(els,x->0); pels:=ShallowCopy(els); for x in [1..Length(pels)] do if RemInt(primepart,Order(pels[x])) <>0 then Unbind(pels[x]); fi; od; #pels:=Compacted(pels); qels:=ShallowCopy(els); qelspos:=List(qels,x->1); for x in [1..Length(qels)] do if GcdInt(Order(qels[x]),prime)<>1 then Unbind(qels[x]); qelspos[x]:=0; fi; od; #qels:=Compacted(qels); for x in pels do for y in qels do position:=Position(els, x*y); coeffs[position]:=coeffs[position]+qelspos[position]; od; od; coeffs:=(Length(qels)*Z(prime)^0)^-1*coeffs; return(coeffs); end; #*************************************************************************** # Catreps # Copyright (C) 2008 Peter Webb # Copyright (C) 2011 Peter Webb, Fan Zhang # Copyright (C) 2020 Moriah Elkin # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ # # The overall structure of the catreps package was designed and most if it # written by Peter Webb , who is also the maintainer. # Contributions were made by Dan Christensen, # Fan Zhang and Moriah Elkin. #*************************************************************************** ############################################################################## ## ## SupportOfMorphism(m) returns the list of positions at which the ## list m is defined. ## ############################################################################## SupportOfMorphism:=function(m) local s, i; s:=[]; for i in [1..Length(m)] do if IsBound(m[i]) then Add(s,i); fi; od; return(s); end; ############################################################################## ## ## IdentityMorphism(l) returns the identity morphism on the set l. ## A morphism is stored as a list of the images of its values on a set ## of numbers, which form its domain of definition, and are taken to be ## an object in a concrete category. At elements of other objects the ## morphism will be undefined. ## ############################################################################## IdentityMorphism:=function(l) local m, i; m:=[]; for i in l do m[i]:=i; od; return(m); end; ############################################################################## ## ## Composition(f,g) returns the composition of the functions f and g, expressed ## as lists of their values. ## ############################################################################## Composition:=function(f,g) local i, h; h:=[]; for i in [1..Length(f)] do if IsBound(f[i]) then if IsBound(g[f[i]]) then h[i]:=g[f[i]]; else return(false); fi; fi; od; return(h); end; ############################################################################## ## ## IsComposable(f,g) returns true if the functions f and g, expressed ## as lists of their values, can be composed and false otherwise. ## ############################################################################## IsComposable:=function(f,g) local i; for i in [1..Length(f)] do if IsBound(f[i]) then if not IsBound(g[f[i]]) then return(false); fi; fi; od; return(true); end; ############################################################################## ## ## Objects(cat) returns the objects of the concrete category cat, as a list ## of sets. At the moment it will not work unless for every object there ## is at least one generator morphism whose support is that object. ## ############################################################################## Objects:=function(cat) local m; if IsBound(cat.objects) then return(cat.objects); fi; cat.objects:=[]; for m in cat.generators do Add(cat.objects,SupportOfMorphism(m)); od; cat.objects:=SSortedList(cat.objects); return(cat.objects); end; ############################################################################## ## ## Origin(cat,m) returns the position in cat.objects of the domain of the ## morphism m. ## ############################################################################## Origin:=function(cat,m) local k, x; k:=PositionBound(m); for x in [1..Length(cat.objects)] do if k in cat.objects[x] then return(x); fi; od; end; ############################################################################## ## ## Terminus(cat,m) returns the position in cat.objects of the domain of the ## morphism m. ## ############################################################################## Terminus:=function(cat,m) local k, x; k:=m[PositionBound(m)]; for x in [1..Length(cat.objects)] do if k in cat.objects[x] then return(x); fi; od; end; Domains:=function(C) Objects(C); C.domain:=List(C.generators,x->Origin(C,x)); C.codomain:=List(C.generators,x->Terminus(C,x)); end; ############################################################################## ConcreteCategoryOps:=rec(); ############################################################################## ## ## ConcreteCategory(list of functions, (list of sets)) ## There are optionally one or two arguments. The first is a list of generating ## functions of the category, the second is a list of the objects of the category. ## The function starts a record for a concrete category. ## If there is only one argument, the objects are taken to be the domains of the ## generator morphisms, so for every object there should be ## at least one generator morphism whose support is that object. ## It could be the identity morphisms, but doesn't have to be. ## ## Written by Peter Webb 2008, Moriah Elkin 2018. ## ############################################################################## ConcreteCategory:=function(arg) local output, domains, codomains, x, m, cod, dom, included, obj, nums; output:=rec(generators:=arg[1], operations:=ConcreteCategoryOps); if Length(arg)=2 then #Checks if object sets overlap or entries repeated (catches ([1,2],[2,3,4]) or ([1,2,2])) nums:=[]; for x in arg[2] do for m in x do if not (m in nums) then Add(nums,m); else Error("One or more entries is duplicated within one or more objects."); fi; od; od; #Computes domains/codomains of morphisms domains:=[]; for m in arg[1] do Add(domains,SupportOfMorphism(m)); od; domains:=SSortedList(domains); codomains:=[]; for x in domains do for m in output.generators do if SupportOfMorphism(m)=x then Add(codomains, List(x,a->m[a])); fi; od; od; codomains:=SSortedList(codomains); #Ensures domains/codomains of morphisms in provided objects list for dom in domains do included:=false; for obj in arg[2] do if IsSubset(obj,dom) then included:=true; break; fi; od; if included=false then Error("One or more morphisms have domains not included in objects list."); fi; od; for cod in codomains do included:=false; for obj in arg[2] do if IsSubset(obj,cod) then included:=true; break; fi; od; if included=false then Error("One or more morphisms have codomains not included in objects list."); fi; od; output.objects:=SSortedList(arg[2]); elif Length(arg)=1 then Objects(output); fi; Domains(output); return(output); end; ############################################################################## ## ## EmptyMat(r,s) returns an r x s matrix in which each entry is []. ## ############################################################################## EmptyMat:=function(r,s) local mat, i, j; mat:=[]; for i in [1..r] do mat[i]:=[]; for j in [1..s] do mat[i][j]:=[]; od; od; return(mat); end; ############################################################################## ## ## Morphisms(cat) returns an l x l matrix, where l is the number of objects ## in the category cat, and where the i,j entry is a list of the ## morphisms from object i to ## object j. ## ############################################################################## Morphisms:=function(cat) local n, genmat, g, mormat, oldlength, newlength, i, j, k, h, templist; if IsBound(cat.morphisms) then return(cat.morphisms); fi; if not IsBound(cat.objects) then Objects(cat); fi; n:=Length(cat.objects); genmat:=EmptyMat(n,n); mormat:=EmptyMat(n,n); for g in cat.generators do Add(genmat[Origin(cat,g)][Terminus(cat,g)],g); od; for i in [1..n] do Add(mormat[i][i],IdentityMorphism(cat.objects[i])); od; oldlength:=0; newlength:=Sum(List(mormat,x->Sum(List(x,Length)))); while oldlength < newlength do oldlength:=newlength; for i in [1..n] do for j in [1..n] do templist:=[]; for k in [1..n] do for g in genmat[k][j] do for h in mormat[i][k] do Add(templist, Composition(h,g)); od; od; od; Append(mormat[i][j],templist); mormat[i][j]:=SSortedList(mormat[i][j]); od; od; newlength:=Sum(List(mormat,x->Sum(List(x,Length)))); od; cat.morphisms:=mormat; return(mormat); end; ############################################################################## ## ## CatRep(category, matrices, field) ## This function creates a representation of a category where the generators ## are represented by the matrices in the list. ## ############################################################################## CatRep:=function(C,L,F) local dimvec, i; dimvec:=List(Objects(C),x->0); for i in [1..Length(C.generators)] do if IsBound(L[i]) then dimvec[C.domain[i]]:=Length(L[i]); fi; od; return rec( category:=C, genimages:=L, field:=F, dimension:=dimvec, operations:=CatRepOps ); end; ############################################################################## ## ## YonedaRep(category, object number, field) ## This returns the representation of the category on the subspace of the ## category algebra spanned by the morphisms whose domain is the specified ## object. The representation is projective, by Yoneda's lemma. ## ############################################################################## YonedaRep:=function(cat,object,F) local genmatrices, mor, dimvec, i, j, k, f, matrix; genmatrices:=[]; mor:=Morphisms(cat); dimvec:=List(mor[object],Length); for i in [1..Length(cat.generators)] do if dimvec[cat.domain[i]]>0 then matrix:=List([1..dimvec[cat.domain[i]]],x->List([1..dimvec[cat.codomain[i]]],y->Zero(F))); for j in [1..Length(mor[object][cat.domain[i]])] do f:=Composition(mor[object][cat.domain[i]][j],cat.generators[i]); k:=Position(mor[object][cat.codomain[i]],f); matrix[j][k]:=One(F); od; genmatrices[i]:=matrix; else genmatrices[i]:=[]; fi; od; return rec( category:=cat, genimages:=genmatrices, field:=F, dimension:=dimvec, operations:=CatRepOps ); end; ############################################################################## ## ## YonedaDualRep(category, object number, field) ## This returns the representation of the category on the dual of the subspace of the ## category algebra spanned by the morphisms whose codomain is the specified ## object. The representation is injective, because its dual is projective, by Yoneda's lemma. ## ############################################################################## YonedaDualRep:=function(cat,object,F) local genmatrices, mor, dimvec, i, j, k, f, matrix; genmatrices:=[]; mor:=Morphisms(cat); dimvec:=List(mor, x->Length(x[object])); for i in [1..Length(cat.generators)] do if dimvec[cat.domain[i]]>0 then matrix:=List([1..dimvec[cat.domain[i]]],x->List([1..dimvec[cat.codomain[i]]],y->Zero(F))); for j in [1..dimvec[cat.codomain[i]]] do f:=Composition(cat.generators[i],mor[cat.codomain[i]][object][j]); k:=Position(mor[cat.domain[i]][object],f); matrix[k][j]:=One(F); od; genmatrices[i]:=matrix; else genmatrices[i]:=[]; fi; od; return rec( category:=cat, genimages:=genmatrices, field:=F, dimension:=dimvec, operations:=CatRepOps ); end; ############################################################################# ## ## ZeroCatRep(cat,field) returns the zero representation of the category. ## ############################################################################# ZeroCatRep:=function(cat,F) local dimvec; dimvec:=List(Objects(cat),x->0); return rec( category:=cat, genimages:=List(cat.generators,x->[]), field:=F, dimension:=dimvec, operations:=CatRepOps ); end; ############################################################################# ## ## ConstantRep(cat,field) returns the constant (or trivial) representation of the category. ## ############################################################################# ConstantRep:=function(cat,F) local dimvec; dimvec:=List(Objects(cat),x->1); return rec( category:=cat, genimages:=List(cat.generators,x->[[One(F)]]), field:=F, dimension:=dimvec, operations:=CatRepOps ); end; ############################################################################## ## ## TensorProductMatrix(mat,mat) . . . Tensor product of two matrices ## ## The GAP command KroneckerProduct seems inexplicably slow and in tests on ## two 60 x 60 matrices takes about twice as long as the following code. ## ############################################################################## TensorProductMatrix:=function(A,B) local u, v, matrix; matrix:=[]; for u in A do for v in B do Add(matrix,Flat(List(u,x->x*v))); od; od; return(matrix); end; ############################################################################## ## ## TensorProductCatRep(rep,rep) . . . Kronecker product of two representations ## Called by TensorProductRep(rep,rep) if rep is a category representation ## ############################################################################## TensorProductCatRep:=function(g,h) local mgens, i; mgens:=[]; for i in [1..Length(g.genimages)] do if IsBound(g.genimages[i]) and IsBound(h.genimages[i]) then mgens[i]:=TensorProductMatrix(g.genimages[i],h.genimages[i]); fi; od; return CatRep(g.category,mgens, g.field); end; ############################################################################## ## ## ExtractHom(vec, dimension vector 1, dimension vector 2) ## takes a vector and returns it repackaged as a list of dimvec1[i] by dimvec2[i] matrices. ## ############################################################################## ExtractHom:=function(vec,dimvec1,dimvec2) local n, hom, l, i, j, mat; n:=0; hom:=[]; for l in [1..Length(dimvec1)] do mat:=[]; for i in [1..dimvec1[l]] do mat[i]:=[]; for j in [1..dimvec2[l]] do n:=n+1; mat[i][j]:=vec[n]; od; od; Add(hom,mat); od; return(hom); end; ############################################################################## ## ## HomBasis(M, N) returns a basis for the space of ## kC-module homomorphisms M -> N. Each element of the output list is a ## list of matrices, which the ith matrix is a map M[i] -> N[i]. ## ## The algorithm used finds homomorphisms X so that Xg-gX=0 for all category generators ## g. The code is an elaboration by Peter Webb (October 2008) of code written ## for group representations ## by Dan Christensen in August 2007. ## ## CatHomBasis is called by HomBasis(M, N) when M is a ## category representation. ## ############################################################################## CatHomBasis:=function(M,N) local dimM, dimN, dM, dN, dMN, dimsumM, dimsumN, dimsumMN, r, s, i, j, k, l, v, f, domain, codomain; # dimM := M.dimension; # dimN := N.dimension; dimsumM:=[]; dimsumM[1]:=0; dimsumN:=[]; dimsumN[1]:=0; dimsumMN:=[]; dimsumMN[1]:=0; domain:=M.category.domain; codomain:=M.category.codomain; r := Length(M.genimages); dM:=0; dN:=0; dMN:=0; for i in [1..Length(M.dimension)] do dM:=dM+M.dimension[i]; dN:=dN+N.dimension[i]; dMN:=dMN+M.dimension[i]*N.dimension[i]; Add(dimsumM,dM); Add(dimsumN,dN); Add(dimsumMN,dMN); od; dimM:=dimsumM[Length(M.dimension)+1]; dimN:=dimsumN[Length(M.dimension)+1]; v:=NullMat(dimsumMN[Length(M.dimension)+1], dimM*dimN*r, M.field); for l in [1..r] do for s in [1..N.dimension[codomain[l]]] do for j in [1..N.dimension[domain[l]]] do for i in [1..M.dimension[domain[l]]] do v[dimsumMN[domain[l]]+(i-1)*N.dimension[domain[l]]+j] [(l-1)*dimM*dimN+dimsumM[domain[l]]*dimN+M.dimension[domain[l]]*dimsumN[codomain[l]]+(i-1)*N.dimension[codomain[l]]+s] :=v[dimsumMN[domain[l]]+(i-1)*N.dimension[domain[l]]+j] [(l-1)*dimM*dimN+dimsumM[domain[l]]*dimN+M.dimension[domain[l]]*dimsumN[codomain[l]]+(i-1)*N.dimension[codomain[l]]+s] - N.genimages[l][j][s]; od; od; od; for r in [1..M.dimension[domain[l]]] do for j in [1..N.dimension[codomain[l]]] do for i in [1..M.dimension[codomain[l]]] do v[dimsumMN[codomain[l]]+(i-1)*N.dimension[codomain[l]]+j] [(l-1)*dimM*dimN+dimsumM[domain[l]]*dimN+M.dimension[domain[l]]*dimsumN[codomain[l]]+(r-1)*N.dimension[codomain[l]]+j] :=v[dimsumMN[codomain[l]]+(i-1)*N.dimension[codomain[l]]+j] [(l-1)*dimM*dimN+dimsumM[domain[l]]*dimN+M.dimension[domain[l]]*dimsumN[codomain[l]]+(r-1)*N.dimension[codomain[l]]+j] + M.genimages[l][r][i]; od; od; od; od; f := SafeNullspaceMat(v, M.field); return(List(f,x->ExtractHom(x,M.dimension,N.dimension))); end; ############################################################################## ## ## SumOfImages(rep,rep) . . returns a list of bases which give the sum of images of all ## module homomorphisms A -> B. Term i in the list is a basis for the subspace of the ## value of representation B at object i which is part of the sum of images. ## ## CatSumOfImages is called by SumOfImages(rep,rep) when rep is a ## category representation. ## ############################################################################## CatSumOfImages:=function(M,N) local homs, basis, l, h; homs:=HomBasis(M,N); basis:=[]; for l in [1..Length(M.dimension)] do basis[l]:=[]; for h in homs do Append(basis[l],h[l]); od; if not(basis[l]=[]) then basis[l]:=List(SafeBaseMat(basis[l]),x->x); fi; od; return(basis); end; ############################################################################# ## ## SubmoduleRep(rep, list of lists of vecs) . . returns the representation which gives ## the action on the submodule spanned at each object by the corresponding ## list of vectors. Each list of vectors must be a basis. This is not checked. ## ## SubmoduleCatRep is called by SubmoduleRep(rep, list of lists of vecs) when rep is a ## category representation. ## ############################################################################# SubmoduleCatRep:=function(rep,v) local dimvec, vs, base, i, newimages, mat, domain, codomain; domain:=rep.category.domain; codomain:=rep.category.codomain; dimvec:=List(v,Length); vs:=[]; base:=[]; for i in [1..Length(v)] do if not(v[i]=[]) then vs[i]:=VectorSpace(rep.field,v[i]); base[i]:=Basis(vs[i],v[i]); fi; od; newimages:=[]; for i in [1..Length(rep.genimages)] do mat:=List(v[domain[i]],x->[]); if not(v[codomain[i]]=[] or v[domain[i]]=[]) then mat:=List(base[domain[i]], b->Coefficients(base[codomain[i]], b*rep.genimages[i])); fi; Add(newimages, mat); od; return rec( category:=rep.category, genimages:=newimages, field:=rep.field, dimension:=dimvec, isRepresentation:=true, operations:=CatRepOps ); end; ############################################################################# ## ## QuotientRep(rep, basis structure) . . . returns the representation giving the ## action on the quotient by an invariant subspace. ## ## At the moment this does not work if the basis structure is for the zero subspace. ## ## QuotientCatRep is called by QuotientRep(rep, basis structure) when rep is a ## category representation. ## ############################################################################# QuotientCatRep:=function(rep,v) local basestructure, d, zero,onemat,i,j,positions,b,p,g, mat,newb,newimages,baseinverse; if Length(v)=0 then return rep; fi; basestructure:=List(v,x->ShallowCopy(SafeBaseMat(x))); for g in basestructure do TriangulizeMat(g); od; d:=List(basestructure,Length); if d=rep.dimension then return ZeroCatRep(rep.category,rep.field); fi; zero:=Zero(rep.field); positions:=[]; baseinverse:=[]; for j in [1..Length(rep.dimension)] do onemat:=IdentityMat(rep.dimension[j],rep.field); i:=1; positions[j]:=[]; for b in basestructure[j] do while b[i]=zero do Add(positions[j],i); i:=i+1; od; i:=i+1; od; Append(positions[j],[i..rep.dimension[j]]); for p in positions[j] do Add(basestructure[j], onemat[p]); od; if basestructure[j]=[] then baseinverse[j]:=[]; else baseinverse[j]:=basestructure[j]^-1; fi; od; newimages:=[]; for g in [1..Length(rep.genimages)] do mat:=[]; for p in positions[rep.category.domain[g]] do if baseinverse[rep.category.codomain[g]] <> [] then b:=rep.genimages[g][p]*baseinverse[rep.category.codomain[g]]; fi; newb:=[]; for i in [d[rep.category.codomain[g]]+1..rep.dimension[rep.category.codomain[g]]] do Add(newb,b[i]); od; Add(mat,newb); od; Add(newimages, mat); od; return rec( category:=rep.category, genimages:=newimages, field:=rep.field, dimension:=rep.dimension-d, isRepresentation:=true, operations:=CatRepOps ); end; ############################################################################## ## ## DecomposeSubmodule(repn, basis structure) . . probably returns a list of two basis ## structures for summands of the submodule of repn spanned by ## the given basis structure, if the module is decomposable, and ## if the module is indecomposable it returns a list whose only element is the ## given basis. ## ## CatDecomposeSubmodule is called by DecomposeSubmodule(repn, basis structure) when repn is a ## category representation. ## ## This code was developed by Peter Webb from code for group representations ## written by Bryan Simpkins and Robert Hank, University of ## Minnesota, April 2006, related to an approach taken by Michael Smith in ## code written in 1993, and tidied up by Dan Christensen, University of Western Ontario, Aug 2007. ## ############################################################################## CatDecomposeSubmodule:= function(M,basisstructure) local newrep, c, d, initlist, b, x, a, n, z, kernel, kdim, image ; newrep := SubmoduleRep(M, basisstructure); d:=Maximum(newrep.dimension); initlist := HomBasis(newrep,newrep); Add(initlist, List(initlist[1], u->u*0)); b := Length(initlist); while b > 0 do; c := b - 1; while c > 0 do; a:=initlist[b]+initlist[c]; n:=1; while n < d do for z in [1..Length(a)] do if not(a[z]=[]) then a[z]:=a[z]*a[z]; fi; od; n:=2*n; od; kernel:=List(a,u->SafeNullspaceMat(u,M.field)); kdim:=Sum(List(kernel,Length)); if not(kdim=0 or kdim=Sum(newrep.dimension)) then image:=List(a,SafeBaseMat); for z in [1..Length(a)] do if image[z] <> [] then image[z]:=image[z]*basisstructure[z]; fi; if kernel[z]<>[] then kernel[z]:=kernel[z]*basisstructure[z]; fi; od; return [kernel,image]; fi; c := c - 1; od; b := b - 1; od; return [basisstructure]; end; ############################################################################## ## ## Decompose(rep) . . returns a list of basis structures of direct summands of rep which ## are probably indecomposable. ## ## DecomposeCatRep is called by Decompose(rep) when rep is a category representation. ## ## This code was developed by Peter Webb from code for group representations ## written by Bryan Simpkins and Robert Hank, University of ## Minnesota, April 2006, related to an approach taken by Michael Smith in ## code written in 1993, and tidied up by Dan Christensen, University of Western Ontario, Aug 2007. ## ############################################################################## DecomposeCatRep:=function(rep) local summands, result, q; if IsBound(rep.summands) then return(rep.summands); fi; summands := [List(rep.dimension, x->SafeIdentityMat(x,rep.field))]; q := 1; # We maintain the following invariants: # - summands is a list of basis structures; the 'union' of these # lists forms a basis structure for rep. # - the summands at positions < q appear to be indecomposable; # those at positions >= q haven't been investigated completely. while IsBound(summands[q]) do; result := DecomposeSubmodule(rep, summands[q]); if Length(result) = 2 then summands[q] := result[1]; Add(summands, result[2]); else q := q + 1; fi; od; rep.summands:=summands; return summands; end; ############################################################################## ## ## Spin(rep, list of lists of vectors) ## returns a basis for the subrepresentation generated by the vectors in the lists. ## There is one entry in the list (of lists of vectors) for each object in the category, ## and it is a list of vectors which all belong to the representation space at that object. ## ## CatSpin is called by Spin(rep, list of lists of vectors) when rep is a ## category representation. ## ## This is code which was developed from code written by ## Fan Zhang (University of Minnesota), March 2011. ## ############################################################################## CatSpin:=function(rep,veclistlist) local basis, olddim, dim, newlist, g, n, v; basis:=List(veclistlist,SafeBaseMat); dim:=Sum(List(basis,Length)); olddim:=dim-1; while dim>olddim do olddim:=dim; newlist:=List(basis,x->List(x,y->y)); for n in [1..Length(rep.genimages)] do g:=rep.genimages[n]; for v in basis[rep.category.domain[n]] do Add(newlist[rep.category.codomain[n]],v*g); od; od; basis:=List(newlist,SafeBaseMat); dim:=Sum(List(basis,Length)); od; return basis; end; ############################################################################## ## ## OrthogonalComplement(list of vectors, dim, field) ## returns a basis for the orthgonal complement of the space spanned by the ## list of vectors, in a space of dimension dim (put there in case the list ## of vectors is empty). ## ############################################################################## OrthogonalComplement:=function(veclist,n,field) if veclist=[] then return(IdentityMat(n,field)); else return NullspaceMat(TransposedMat(veclist)); fi; end; ############################################################################## ## ## CoSpin(rep, list of lists of vectors) ## returns a basis for the largest subrepresentation contained in the ## subspaces spanned by the vectors in the lists. ## There is one entry in the list (of lists of vectors) for each object in the category, ## and it is a list of vectors which all belong to the representation space at that object. ## ## CatCoSpin is called by CoSpin(rep, list of lists of vectors) when rep is a ## category representation. ## ############################################################################## CatCoSpin:=function(rep,veclistlist) local basis, olddim, dim, newlist, g, n, v, output, i, transposedimages; transposedimages:=List(rep.genimages,TransposedMat); basis:=[]; for i in [1..Length(rep.dimension)] do basis[i]:=OrthogonalComplement(veclistlist[i],rep.dimension[i],rep.field); od; dim:=Sum(List(basis,Length)); olddim:=dim-1; while dim>olddim do olddim:=dim; newlist:=List(basis,x->List(x,y->y)); for n in [1..Length(rep.genimages)] do g:=transposedimages[n]; for v in basis[rep.category.codomain[n]] do Add(newlist[rep.category.domain[n]],v*g); od; od; basis:=List(newlist,SafeBaseMat); dim:=Sum(List(basis,Length)); od; output:=[]; for i in [1..Length(rep.dimension)] do output[i]:=OrthogonalComplement(basis[i],rep.dimension[i],rep.field); od; return output; end; ############################################################################## ## ## EndomorphismGroup(cat, obj) returns the group of the endomorphisms of obj in ## cat, in permutation form. It assumes every endomorphism is invertible and that the generators of the ## endomorphism group appear among the generators of the category. ## ## Written by Moriah Elkin July 2018. ## ############################################################################## EndomorphismGroup:=function(cat,obj) local i, g, generators, permutations; permutations:=[]; generators:=StructuralCopy(cat.generators); for g in generators do if Origin(cat,g)=obj and Terminus(cat,g)=obj then #add identity i:=1; for i in [1..Length(g)] do if not IsBound(g[i]) then g[i]:=i; fi; i:=i+1; od; #convert to permutation and add to list Add(permutations,PermList(g)); fi; od; if Length(permutations)>0 then return Group(permutations); fi; return Group([],()); end; ############################################################################## ## ## EndomorphismGroups(cat) returns a list containing the endomorphism group for ## each object in the category cat. ## ## Written by Moriah Elkin July 2018. ## ############################################################################## EndomorphismGroups:=function(cat) cat.endomorphismgroups:=List(cat.objects,x->EndomorphismGroup(cat,x)); end; ############################################################################## ## ## FI(n) and FI2(n) interchangeably return a record for the category FI with ## objects 0...n. O is represented by the first object ( [1] ), and its morphisms ## correspond to the first element in every object, which is otherwise ignored ## (first elements only map to first elements). The category FI is the category of finite sets with ## injective maps that has featured in the theory of representation stability. ## ## Written by Moriah Elkin July 2018. ## ############################################################################## FI:=function(n) local objectlist, morphismlist, i, j, x, m; morphismlist:=[]; objectlist:=[]; j:=0; for i in [1..n+1] do Add(objectlist, [j+1..j+i]); j:=j+i; od; for x in objectlist do if Length(x)<=n then m:=[]; for i in x do m[i]:=i+Length(x); od; Add(morphismlist,m); fi; if Length(x)>=3 then m:=[]; for i in x do m[i]:=i; od; m[x[2]]:=x[2]+1; m[x[3]]:=x[3]-1; Add(morphismlist,m); fi; if Length(x)>=4 then m:=[]; m[x[1]]:=x[1]; m[x[Length(x)]]:=x[2]; for i in [x[2]..x[Length(x)-1]] do m[i]:=i+1; od; Add(morphismlist,m); fi; od; return ConcreteCategory(morphismlist, objectlist); end; FI2:=function(n) local objectlist, morphismlist, i, j, k, m; morphismlist:=[]; objectlist:=[]; j:=0; for i in [1..n+1] do Add(objectlist, [j+1..j+i]); if i<=n then m:=[]; for k in [j+1..j+i] do m[k]:=k+i; od; Add(morphismlist,m); fi; if i>=3 then m:=[]; for k in [j+1..j+i] do m[k]:=k; od; m[j+2]:=j+3; m[j+3]:=j+2; Add(morphismlist,m); fi; if i>=4 then m:=[]; m[j+1]:=j+1; m[j+i]:=j+2; for k in [j+2..j+i-1] do m[k]:=k+1; od; Add(morphismlist,m); fi; j:=j+i; od; return ConcreteCategory(morphismlist, objectlist); end; ############################################################################## ## ## DirectSumCatRep(rep1, rep2) returns the representation that is the direct ## sum of the representations rep1 and rep2 of the category rep1.category. ## ## Written by Moriah Elkin July 2018. ## ## DirectSumCatRep is called by DirectSumRep(rep1,rep2) when rep1 and rep2 are ## group representations. ## ############################################################################## DirectSumCatRep:=function(rep1,rep2) local i, row, col, newmat, gimages, dDim1, dDim2, cDim1, cDim2, cat; if rep1.field<>rep2.field or rep1.category<>rep2.category then Error("Representations incompatible."); fi; cat:=rep1.category; gimages:=[]; for i in [1..Length(cat.generators)] do dDim1:=rep1.dimension[cat.domain[i]]; dDim2:=rep2.dimension[cat.domain[i]]; cDim1:=rep1.dimension[cat.codomain[i]]; cDim2:=rep2.dimension[cat.codomain[i]]; newmat:=EmptyMat(dDim1+dDim2,cDim1+cDim2); if newmat<>[] and newmat[1]<>[] then for row in [1..Length(newmat)] do for col in [1..Length(newmat[1])] do if row in [1..dDim1] and col in [1..cDim1] then newmat[row][col]:=rep1.genimages[i][row][col]; elif row in [dDim1+1..dDim1+dDim2] and col in [cDim1+1..cDim1+cDim2] then newmat[row][col]:=rep2.genimages[i][row-dDim1][col-cDim1]; else newmat[row][col]:=Zero(rep1.field); fi; od; od; fi; Add(gimages,newmat); od; return rec(category:=cat,genimages:=gimages,field:=rep1.field,dimension:=rep1.dimension+rep2.dimension, operations:=CatRepOps); end; ############################################################################## ## ## GeneratorDomains(cat) returns a l x l matrix, where l is the number of objects ## in the category cat, and where the i,j entry is a list of the indices of morphisms ## from object i to object j. ## ## Written by Moriah Elkin August 2018. ## ############################################################################## GeneratorDomains:=function(cat) local M, i; if IsBound(cat.generatordomains) then return cat.generatordomains; fi; M:=EmptyMat(Length(cat.objects),Length(cat.objects)); for i in [1..Length(cat.generators)] do Add(M[cat.domain[i]][cat.codomain[i]],i); od; cat.generatordomains:=M; return M; end; ############################################################################## ## ## MorphismsRep(rep) returns a l x l matrix, where l is the number of objects ## in the category of rep, and where the i,j entry is a list of the matrices of ## morphisms from object i to object j. ## ## Written by Moriah Elkin (August 2018), based on code for categories written ## by Peter Webb. ## ############################################################################## MorphismsRep:=function(rep) local cat, n, genmat, g, mormat, oldlength, newlength, i, j, k, h, templist; cat:=rep.category; if IsBound(rep.morphimgs) then return(rep.morphimgs); fi; if not IsBound(cat.objects) then Objects(cat); fi; n:=Length(cat.objects); genmat:=EmptyMat(n,n); mormat:=EmptyMat(n,n); for g in [1..Length(rep.genimages)] do Add(genmat[Origin(cat,cat.generators[g])][Terminus(cat,cat.generators[g])],rep.genimages[g]); od; for i in [1..n] do Add(mormat[i][i],SafeIdentityMat(rep.dimension[i],rep.field)); od; oldlength:=0; newlength:=Sum(List(mormat,x->Sum(List(x,Length)))); while oldlength < newlength do oldlength:=newlength; for i in [1..n] do for j in [1..n] do templist:=[]; for k in [1..n] do for g in genmat[k][j] do for h in mormat[i][k] do if h<>[] and g<>[] then Add(templist, h*g); fi; od; od; od; Append(mormat[i][j],templist); mormat[i][j]:=SSortedList(mormat[i][j]); od; od; newlength:=Sum(List(mormat,x->Sum(List(x,Length)))); od; rep.morphimgs:=mormat; return(mormat); end; ############################################################################## ## ## SubConstant(rep) returns a list of bases for the largest subconstant ## representation of rep. The algorithm finds the common kernel of all differences ## of morphisms from a domain to all codomains. ## ## Written by Moriah Elkin August 2018. ## ############################################################################## SubConstant:=function(rep) local morphisms, vecListList, obj1, obj2, m, m1, m2, perpMat, perpSum, vec; morphisms:=MorphismsRep(rep); vecListList:=[]; if Length(morphisms)>0 then for obj1 in [1..Length(morphisms)] do perpSum:=[]; for obj2 in [1..Length(morphisms)] do perpMat:=[]; if obj1<>obj2 and Length(morphisms[obj1][obj2])>1 then for m1 in morphisms[obj1][obj2] do for m2 in morphisms[obj1][obj2] do if m1<>m2 then for vec in TransposedMat(m1-m2) do Add(perpMat,vec); od; fi; od; od; Append(perpSum, SafeBaseMat(perpMat)); elif obj1=obj2 then for m in morphisms[obj1][obj1] do if rep.dimension[obj1]<>0 then for vec in TransposedMat(m-SafeIdentityMat(rep.dimension[obj1],rep.field)) do Add(perpMat,vec); od; fi; od; Append(perpSum, SafeBaseMat(perpMat)); fi; od; if perpSum<>[] then vecListList[obj1]:=SafeNullspaceMat(TransposedMat(perpSum),rep.field); else vecListList[obj1]:=SafeIdentityMat(rep.dimension[obj1],rep.field); fi; od; fi; return(vecListList); end; ############################################################################## ## ## Evaluation(rep, obj) returns the representation of the endomorphism ## group of object obj on the value of the representation rep at obj. (In FI, obj is ## not the mathematical object in FI, but rather the object number in the category). ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## Evaluation:=function(rep, obj) local g, genMats; genMats:=[]; for g in [1..Length(rep.genimages)] do if Origin(rep.category,rep.category.generators[g])=obj and Terminus(rep.category,rep.category.generators[g])=obj then Add(genMats, rep.genimages[g]); fi; od; return Rep(EndomorphismGroup(rep.category,obj),genMats,rep.field); end; ############################################################################## ## ## SpinFixedPts(rep, obj) returns a list of lists of bases (lists of vectors), ## where list of bases i is the spin of the fixed points of the group representation ## that is the i'th summand of the evaluation of rep at object obj; item i in the list ## is an empty list when there are no generators or no fixed points in that summand of ## the evaluation. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## SpinFixedPts:=function(rep,obj) local pt, e, replist, toSpin, i, output, bases; output:=[]; e:=Evaluation(rep,obj); bases:=Decompose(e); replist:=List(bases,x->SubmoduleRep(e,x)); for i in [1..Length(replist)] do if IsEmpty(Flat(replist[i].genimages)) then output[i]:=[]; else pt:=FixedPoints(replist[i]); if pt=[] then output[i]:=[]; else toSpin:=EmptyMat(1,Length(rep.dimension))[1]; toSpin[obj]:=pt*bases[i]; output[i]:=Spin(rep,toSpin); fi; fi; od; return output; end; ############################################################################## ## ## SpinBasisVec(rep, obj) goes through each summand in the evaluation of rep at obj, ## takes the first vector in its basis, and returns a basis for the subfunctor generated ## by this vector (an empty list if the basis is empty). It returns a list of lists of ## bases, where the i'th list of bases corresponds to the i'th summand of the evaluation. ## It does not check that the summand does not have fixed points. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## SpinBasisVec:=function(rep,obj) local v, e, basislist, i, toSpin, output; output:=[]; e:=Evaluation(rep,obj); basislist:=Decompose(e); for i in [1..Length(basislist)] do if IsZero(basislist) then output[i]:=[]; else v:=basislist[i][1]; toSpin:=EmptyMat(1,Length(rep.dimension))[1]; toSpin[obj]:=[v]; output[i]:=Spin(rep,toSpin); fi; od; return output; end; ############################################################################## ## ## IsDirectSum(summands,sum) takes in a list of bases (lists of vectors), summands, and a ## basis (list of vectors), sum, and returns true if the direct sum of summands is sum. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## IsDirectSum:=function(summands,sum) local i, summandMat, bigMat; summandMat:=[]; for i in [1..Length(summands)] do Append(summandMat,summands[i]); od; bigMat:=Concatenation(summandMat,sum); return RankMat(bigMat)=RankMat(summandMat) and RankMat(summandMat)=Length(summandMat) and RankMat(sum)=Length(sum) and Length(summandMat)=Length(sum); end; ############################################################################## ## ## TestOneFixedPt(rep) tests whether there is at most one fixed point in the summands ## of the evaluations of rep at each object. It returns true if there is, false if ## there is not. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## TestOneFixedPt:=function(rep) local i, j, e, replist; for i in [1..Length(rep.dimension)] do e:=Evaluation(rep,i); replist:=List(Decompose(e),x->SubmoduleRep(e,x)); for j in [1..Length(replist)] do if not IsEmpty(Flat(replist[j].genimages)) and Length(FixedPoints(replist[j]))>1 then return false; fi; od; od; return true; end; ############################################################################## ## ## DisplayButterflyDims(sn,subGens) takes in the symmetric group of a certain dimension ## and the generators for a subgroup corresponding to a partition. It displays the ## ButterflyFactors matrix (without decomposing), and returns the ButterflyFactors. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## DisplayButterflyDims:=function(sn,subGens) local m, b; m:=PermutationRepOnCosets(sn,Subgroup(sn,subGens),GF(2)); b:=ButterflyFactors(m,SocleSeries(m)[1],RadicalSeries(m)[1]); DisplayMatrix(List(b,x->List(x,y->y.dimension))); return b; end; ############################################################################## ## ## ButterflyDimsRep(rep) takes in a representation, displays the ButterflyFactors matrix ## (without decomposing), and returns the ButterflyFactors. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## ButterflyDimsRep:=function(rep) local b; b:=ButterflyFactors(rep,SocleSeries(rep)[1],RadicalSeries(rep)[1]); DisplayMatrix(List(b,x->List(x,y->y.dimension))); return b; end; ############################################################################## ## ## npButterflyDimsRep(rep) takes in a representation and returns the ButterflyFactors ## (without printing anything). ## ## Written by Moriah Elkin Spring 2020. ## ############################################################################## npButterflyDimsRep:=function(rep) return ButterflyFactors(rep,SocleSeries(rep)[1],RadicalSeries(rep)[1]); end; ############################################################################## ## ## SafeFixedPoints(rep) finds the fixed points of a representation rep; if rep ## has dimension 0, it returns an empty list. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## SafeFixedPoints:=function(rep) if rep.dimension=0 then return []; else return FixedPoints(rep); fi; end; ############################################################################## ## ## SafeDimHom(rep) returns the dimension of the space of module homomorphisms ## rep1 -> rep2. If rep has dimension 0, it returns 0. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## SafeDimHom:=function(d,rep) if rep.dimension=0 then return 0; else return DimHom(d,rep); fi; end; ############################################################################## ## ## ExamineButterflyFactors(b,dRec) takes in a ButterflyFactors matrix and a record of ## possible factors. It displays the original dimension matrix, and then an ordered list of ## matrices, where the dimensions in each matrix correspond to the dimensions of the ## homomorphisms between that element in the ButterflyFactors matrix and the factor in the ## list, or the number of fixed points in that element in the ButterflyFactors matrix. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## ExamineButterflyFactors:=function(b,dRec) local name; Print("Original matrix:\n"); DisplayMatrix(List(b,x->List(x,y->y.dimension))); Print("\n\nFixed points:\n"); DisplayMatrix(List(b,x->List(x,y->Length(SafeFixedPoints(y))))); Print("\n\nFactors:\n"); for name in RecNames(dRec) do Print(name); Print("\n"); DisplayMatrix(List(b,x->List(x,y->SafeDimHom(dRec.(name),y)))); Print("\n"); od; end; ############################################################################## ## ## RemoveFromBottom(rep,d) takes representations rep and d. ## It returns a representation with all images of d removed from the bottom ## of rep. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## RemoveFromBottom:=function(rep,d) local newrep; newrep:=QuotientRep(rep,SumOfImages(d,rep)); return newrep; end; ############################################################################## ## ## RemoveFromTop(rep,d) returns the representation that is the common kernel ## of all homomorphisms from rep to d. ## ## Written by Peter Webb Spring 2020 ## ############################################################################## RemoveFromTop:=function ( rep, d ) local newrep; newrep := SubmoduleRep( rep, KernelIntersection( rep, d ) ); return newrep; end; ############################################################################## ## ## FISummandEvalReps(n,obj) returns a list of the representations of the summands of the ## evaluations of the summands of the Yoneda representation over GF(2) of FI(n) at the ## mathematical object obj. There will be 3 levels of lists: the overall list will contain ## a list for each submodule of the Yoneda representation, each of which will contain a list ## of submodule representations for each object at which it has been evaluated. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## FISummandEvalReps:=function(n,obj) local catreplist, yr, i, e, j, output; output:=[]; yr:=YonedaRep(FI(n),obj+1,GF(2)); catreplist:=List(Decompose(yr),x-> SubmoduleRep(yr,x)); for i in [1..Length(catreplist)] do output[i]:=[]; for j in [1..n+1] do e:=Evaluation(catreplist[i],j); output[i][j]:=List(Decompose(e),x-> SubmoduleRep(e,x)); od; od; return output; end; ############################################################################## ## ## ProjSummands(n,obj) returns whether the summands in FISummandEvalReps(n,obj,GF(2)) ## are projective: each column of the output is the evaluation at a different mathematical ## object, each row is a different summand of the YonedaRep of FI(n) at obj, and each ## element in the matrix is a list with whether the summands of the evaluation are ## projective, in order. Representations with no generators display "fail." ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## ProjSummands:=function(n, obj) local summands, output, i, j, k; summands:=FISummandEvalReps(n,obj,GF(2)); output:=[]; for i in [1..Length(summands)] do output[i]:=[]; for j in [1..Length(summands[i])] do output[i][j]:=[]; for k in [1..Length(summands[i][j])] do if IsEmpty(Flat(summands[i][j][k].genimages)) then output[i][j][k]:=fail; else output[i][j][k]:=IsProjectiveRep(summands[i][j][k]); fi; od; od; od; return output; end; ############################################################################## ## ## DimSummands(n,obj) returns the dimensions of the summands in ## FISummandEvalReps(n,obj,GF(2)): each column of the output is the evaluation at a ## different mathematical object, each row is a different summand of the YonedaRep of FI(n) ## at obj, and each element in the matrix is a list with the dimensions of the summands of ## the evaluation in order. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## DimSummands:=function(n, obj) local summands, output, i, j, k; summands:=FISummandEvalReps(n,obj,GF(2)); output:=[]; for i in [1..Length(summands)] do output[i]:=[]; for j in [1..Length(summands[i])] do output[i][j]:=[]; for k in [1..Length(summands[i][j])] do output[i][j][k]:=summands[i][j][k].dimension; od; od; od; return output; end; ############################################################################## ## ## FixedPtDims(n) returns a list of lists of lists of dimensions. The outer list contains a ## list for SpinFixedPts of the Yoneda Rep of FI(n) at mathematical object 2, at each object ## in FI(n); and each of those lists contains the dimensions of the corresponding list of ## bases at each object (an empty list if that summand has no fixed points). ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## FixedPtDims:=function(n) local yr, i, j, bases, output; output:=[]; if n>1 then yr:=YonedaRep(FI(n),3,GF(2)); for i in [1..n+1] do bases:=SpinFixedPts(yr,i); output[i]:=[]; for j in [1..Length(bases)] do if bases[j]=[] then output[i][j]:=[]; else output[i][j]:=List(bases[j],Length); fi; od; od; fi; return output; end; ############################################################################## ## ## FixedPtBases(n) returns a list of lists of bases. The outer list contains a list for ## SpinFixedPts of the Yoneda Rep of FI(n) at mathematical object 2, at each object in ## FI(n); and each of those lists contains the corresponding list of bases at each object ## (taken at the summand that has fixed points). ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## FixedPtBases:=function(n) local yr, i, j, bases, output; output:=[]; if n>1 then yr:=YonedaRep(FI(n),3,GF(2)); for i in [1..n+1] do bases:=SpinFixedPts(yr,i); output[i]:=[]; for j in [1..Length(bases)] do if not bases[j]=[] then output[i]:=bases[j]; break; fi; od; od; fi; return output; end; ############################################################################## ## ## BasisVecDims(n) returns a list of lists of lists of dimensions. The outer list contains a ## list for SpinBasisVec of the Yoneda Rep of FI(n) at mathematical object 2, at each object ## in FI(n); and each of those lists contains the dimensions of the corresponding list of ## bases at each object (where dimension list i contains the dimensions of ## SpinBasisVec(rep,i)) (an empty list if that summand's basis is empty). I.e., ## BasisVecDims[i][j] contains the lengths of the bases generated by spinning the first ## vector in the basis for the jth summand of the evaluation of the Yoneda rep at object i. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## BasisVecDims:=function(n) local yr, i, j, bases, output; output:=[]; if n>1 then yr:=YonedaRep(FI(n),3,GF(2)); for i in [1..n+1] do bases:=SpinBasisVec(yr,i); output[i]:=[]; for j in [1..Length(bases)] do output[i][j]:=List(bases[j],Length); od; od; fi; return output; end; ############################################################################## ## ## BasisVecBases(n) returns a list of lists of lists of bases. The outer list contains a ## list for SpinBasisVec of the Yoneda Rep of FI(n) at mathematical object 2, at each object ## in FI(n); and each of those lists contains the corresponding list of bases at each object ## (where list i contains SpinBasisVec(rep,i)) (an empty list if that summand's basis is ## empty). I.e., BasisVecBases[i][j] contains the list of bases generated by spinning the ## first vector in the basis for the jth summand of the evaluation of the Yoneda rep at ## object i. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## BasisVecBases:=function(n) local yr, i, j, bases, output; output:=[]; if n>1 then yr:=YonedaRep(FI(n),3,GF(2)); for i in [1..n+1] do output[i]:=SpinBasisVec(yr,i); od; fi; return output; end; ############################################################################## ## ## TestYRSummand(basis,eval,summandi) takes in a basis, an evaluation of a Yoneda Rep over ## GF(2), and the index of the summand of that evaluation that the basis is thought to be ## equivalent to; it returns whether it is in fact equivalent. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## TestYRSummand:=function(basis,eval,summandi) local summands; summands:=Decompose(eval); summands[summandi]:=basis; return IsDirectSum(summands,BasisVectors(Basis(GF(2)^Length(basis[1])))); end; ############################################################################## ## ## AllSpinDims(n, evalObj,outputRec) spins all vectors in the evaluation at math object ## evalObj of the Yoneda representation of FI(n) at math object 2 with respect to that ## Yoneda representation. If outputRec is false, returns a sorted list of the dimensions of ## the bases; if it is true, returns a record with each dimension list corresponding to the ## list of vectors that generated it. ## ## Written by Moriah Elkin Spring 2019. ## ############################################################################## AllSpinDims:=function(n,evalObj,outputRec) local yr, dim, i, v, output, spunDims, toSpin; yr:=YonedaRep(FI(n),3,GF(2)); dim:=Evaluation(yr,evalObj+1).dimension; if outputRec then output:=rec(); for v in GF(2)^dim do toSpin:=EmptyMat(1,n+1)[1]; toSpin[evalObj+1]:=[v]; spunDims:=String(List(Spin(yr,toSpin),Length)); if IsBound(output.(spunDims)) then Append(output.(spunDims),[v]); else output.(spunDims):=[v]; fi; od; return output; else output:=[]; i:=0; for v in GF(2)^dim do i:=i+1; toSpin:=EmptyMat(1,n+1)[1]; toSpin[evalObj+1]:=[v]; output[i]:=List(Spin(yr,toSpin),Length); od; return SSortedList(output); fi; end; GroupRepOps:=rec(Decompose:=DecomposeGroupRep, SubmoduleRep:=SubmoduleGroupRep, QuotientRep:=QuotientGroupRep, Spin:=GroupSpin, CoSpin:=GroupCoSpin, HomBasis:=GroupHomBasis, DecomposeSubmodule:=GroupDecomposeSubmodule, SumOfImages:=GroupSumOfImages, TensorProductRep:=TensorProductGroupRep, DirectSumRep:=DirectSumGroupRep ); CatRepOps:=rec(Decompose:=DecomposeCatRep, SubmoduleRep:=SubmoduleCatRep, QuotientRep:=QuotientCatRep, Spin:=CatSpin, CoSpin:=CatCoSpin, HomBasis:=CatHomBasis, DecomposeSubmodule:=CatDecomposeSubmodule, SumOfImages:=CatSumOfImages, TensorProductRep:=TensorProductCatRep, DirectSumRep:=DirectSumCatRep );