Tutorial on the GAP package 'catreps' for handling representations of categories.

March 2011

The package has been designed and is maintained by
Peter Webb
School of Mathematics
University of Minnesota
Minneapolis MN 55455

webb@math.umn.edu
http://www.math.umn.edu/~webb
The GAP code is available at: http://www.math.umn.edu/~webb/

The code has been written by Peter Webb, with a contribution from Fan Zhang.

Overview of the package catreps

Read P.J. Webb, An introduction to the representations and cohomology of categories, to learn the basics of representations of categories. A representation of a category over a ring is a functor from the category to the category of modules over that ring. This package assumes the ring is a field. Thus a representation consists of a vector space associated to each object of the category, and for each morphism in the category a linear map between the vector spaces associated to its domain and codomain.

In this package a category is stored as a concrete category (i.e. a category where the objects are sets and morphisms are maps of sets) in the same way as for the package 'categories' which computes the homology of nerves of categories. A category is stored as a record (cat, say) with fields cat.objects, cat.generators, cat.domain, cat.codomain. Each object in the list cat.objects is a set, and each morphism in the list of generator morphisms cat.generators is stored as a mapping of sets, which we notate as the list of its values. The numbers of the objects which are the domain and codomain of each generator morphism are listed in cat.domain and cat.codomain.

A representation of a category is stored as a record with a name such as rep, and fields which include rep.category, rep.genimages, rep.field and rep.dimension. The first of these is the category being represented. The second is a list of matrices over rep.field which represent the action of the generator morphisms in the list rep.category.generators.

We need to work with elements of the 'representation space' of the representation, which we take to be the direct sum of the vector spaces associated to the objects of the category, taken in the fixed order in which the objects are always listed. Some of the commands below take as arguments or return a list of lists of vectors. In such a list the nth entry is a list of vectors in the vector space associated to object n and it is frequently a basis for the space it spans.

Commands currently available

Commands for categories:
SupportOfMorphism(mapping) returns the list of positions at which the list 'mapping' is defined.
IdentityMorphism(l) returns the identity morphism on the set l.
Composition(f,g) returns the composition of the functions f and g, expressed as lists of their values.
IsComposable(f,g) returns true if the functions f and g, expressed as lists of their values, can be composed and false otherwise.
Objects(cat) returns the objects of the concrete category cat, as a list of sets.
Origin(cat,m) returns the position in cat.objects of the domain of the morphism m.
Terminus(cat,m) returns the position in cat.objects of the domain of the morphism m.
ConcreteCategory(list of mappings). . sets up the record of the category which has the list of mappings as its generator morphisms.
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.

Commands which return a representation:
CatRep(category, list of matrices, field) returns a representation of the category over the field, where the generators are represented by the matrices in the list.
YonedaRep(category, object number, field) 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.
YonedaDualRep(category, object number, field) 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 (for the opposite algebra), by Yoneda's lemma.
TensorProductRep(rep, rep). . returns a representation which is the tensor product of the two representations.
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.
QuotientRep(rep, list of lists vecs). . returns the representation on the quotient module by the submodule spanned by the vectors. Each list of vectors in the list is a basis for the subspace they span of the representation space for the corresponding object.
ZeroRep(cat,field) returns the zero representation of the category.
ConstantRep(cat,field) returns the constant (or trivial) representation of the category.

Commands which return lists of vectors:
Spin(rep, list of lists of vectors) . . returns a list of bases for the subrepresentation generated by the vectors in the lists.
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.
Decompose(rep) . . returns a list of lists of bases. Each list of bases determines a direct summand of the representation, which is their direct sum. The summands are probably indecomposable.
DecomposeSubmodule(repn, list of bases) . . returns a list of two lists of bases for summands of the submodule of repn spanned by the given list of bases, if this submodule is decomposable, and if the module is indecomposable it returns a list whose only element is the given list of bases. A probabilistic algorithm is used, and it is possible that that a representation which the computer fails to decompose is in fact decomposable. The routine is called by Decompose.

Commands for homomorphisms:
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, in which the ith matrix is a map M[i] -> N[i].

Worked Examples

Example 1:

gap> Read("catreps");
We first set up a category with 2 objects and 9 morphisms:
gap> c3c3:=ConcreteCategory([[2,3,1],[4,5,6],[,,,5,6,4]]);
rec( generators := [ [ 2, 3, 1 ], [ 4, 5, 6 ], [ ,,, 5, 6, 4 ] ],
operations := rec( ), objects := [ [ 1, 2, 3 ], [ 4, 5, 6 ] ],
domain := [ 1, 1, 2 ], codomain := [ 1, 2, 2 ] )
The following constructs a representation:
gap> one:=One(GF(3));;
gap> d:=[[1,1,0,0,0],[0,1,1,0,0],[0,0,1,0,0],[0,0,0,1,1],[0,0,0,0,1]]*one;;
gap> e:=[[0,1,0,0],[0,0,1,0],[0,0,0,0],[0,1,0,1],[0,0,1,0]]*one;;
gap> f:=[[1,1,0,0],[0,1,1,0],[0,0,1,0],[0,0,0,1]]*one;;
gap> nine:=CatRep(c3c3,[d,e,f],GF(3));
rec(
category := rec( generators := [ [ 2, 3, 1 ], [ 4, 5, 6 ], [ ,,, 5, 6, 4 ] ]
, operations := rec( ), objects := [ [ 1, 2, 3 ], [ 4, 5, 6 ] ],
domain := [ 1, 1, 2 ], codomain := [ 1, 2, 2 ] ),
genimages := [ [ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],
[ 0*Z(3), Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ],
[ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],
[ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, Z(3)^0 ],
[ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] ],
[ [ 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3) ]
, [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],
[ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ],
[ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3) ] ],
[ [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0, Z(3)^0, 0*Z(3) ]
, [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3) ],
[ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] ] ], field := GF(3),
dimension := [ 5, 4 ] )
The dimension vector shows that the space associated to object 1 is 5-dimensional, and the space associated to object 2 is 4-dimensional. The representation is indecomposable:
gap> Length(Decompose(nine));
1
gap> fortyone:=TensorProductRep(nine,nine);;
The output from the last command was suppressed, but the representation it produces has a space of dimension 25 at object 1, and a space of dimension 16 at object 2. We start to examine it by finding its indecomposable summands.
gap> d:=Decompose(fortyone);;
gap> List(d,x->List(x,Length));
[ [ 3, 0 ], [ 3, 1 ], [ 3, 3 ], [ 3, 3 ], [ 0, 3 ], [ 3, 0 ], [ 3, 0 ],
[ 3, 0 ], [ 1, 3 ], [ 3, 3 ] ]
Thus fortyone has 10 indecomposable summands, with dimension lists as above. We examine the structure of the third summand.
gap> six:=SubmoduleRep(fortyone,d[3]);
rec(
category := rec( generators := [ [ 2, 3, 1 ], [ 4, 5, 6 ], [ ,,, 5, 6, 4 ] ]
, operations := rec( ), objects := [ [ 1, 2, 3 ], [ 4, 5, 6 ] ],
domain := [ 1, 1, 2 ], codomain := [ 1, 2, 2 ] ),
genimages := [ [ [ Z(3)^0, Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0, Z(3)^0 ],
[ 0*Z(3), 0*Z(3), Z(3)^0 ] ],
[ [ 0*Z(3), Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3), Z(3) ],
[ 0*Z(3), 0*Z(3), 0*Z(3) ] ],
[ [ Z(3)^0, Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0, Z(3)^0 ],
[ 0*Z(3), 0*Z(3), Z(3)^0 ] ] ], field := GF(3),
dimension := [ 3, 3 ], isRepresentation := true )
gap> SumOfImages(ConstantRep(c3c3,GF(3)),six);
[ [ [ 0*Z(3), 0*Z(3), Z(3)^0 ] ], [ ] ]
The representation six consists of a module homomorphism for a group of order 3 acting on two spaces of dimension 3. The last calculation shows that it is not an isomorphism between two modules. We do the same test to the Yoneda representation (= representable functor) associated to object 1.
gap> y:=YonedaRep(c3c3,1,GF(3));;
gap> SumOfImages(ConstantRep(c3c3,GF(3)),y);
[ [ [ Z(3)^0, Z(3)^0, Z(3)^0 ] ], [ [ Z(3)^0, Z(3)^0, Z(3)^0 ] ] ]
This shows that six is not isomorphic to the Yoneda representation. We take the opportunity to construct the simple representation associated to object 1.
gap> s1:=SubmoduleRep(six,[ [ [ 0*Z(3), 0*Z(3), Z(3)^0 ] ], [ ] ]);
rec(
category := rec( generators := [ [ 2, 3, 1 ], [ 4, 5, 6 ], [ ,,, 5, 6, 4 ] ]
, operations := rec( ), objects := [ [ 1, 2, 3 ], [ 4, 5, 6 ] ],
domain := [ 1, 1, 2 ], codomain := [ 1, 2, 2 ],
morphisms := [ [ [ [ 1, 2, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ] ],
[ [ 4, 5, 6 ], [ 5, 6, 4 ], [ 6, 4, 5 ] ] ],
[ [ ], [ [ ,,, 4, 5, 6 ], [ ,,, 5, 6, 4 ], [ ,,, 6, 4, 5 ] ] ] ] ),
genimages := [ [ [ Z(3)^0 ] ], [ [ ] ], [ ] ], field := GF(3),
dimension := [ 1, 0 ], isRepresentation := true )
gap> five:=QuotientRep(six,[ [ [ 0*Z(3), 0*Z(3), Z(3)^0 ] ], [ ] ]);
rec(
category := rec( generators := [ [ 2, 3, 1 ], [ 4, 5, 6 ], [ ,,, 5, 6, 4 ] ]
, operations := rec( ), objects := [ [ 1, 2, 3 ], [ 4, 5, 6 ] ],
domain := [ 1, 1, 2 ], codomain := [ 1, 2, 2 ],
morphisms := [ [ [ [ 1, 2, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ] ],
[ [ 4, 5, 6 ], [ 5, 6, 4 ], [ 6, 4, 5 ] ] ],
[ [ ], [ [ ,,, 4, 5, 6 ], [ ,,, 5, 6, 4 ], [ ,,, 6, 4, 5 ] ] ] ] ),
genimages := [ [ [ Z(3)^0, Z(3)^0 ], [ 0*Z(3), Z(3)^0 ] ],
[ [ 0*Z(3), Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3), Z(3) ] ],
[ [ Z(3)^0, Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0, Z(3)^0 ],
[ 0*Z(3), 0*Z(3), Z(3)^0 ] ] ], field := GF(3),
dimension := [ 2, 3 ], isRepresentation := true )
The next calculation shows that the 3-dimensional representation of C_3 associated to object 1 is a single copy of the regular representation of C_3.
gap> SumOfImages(s1,six);
[ [ [ 0*Z(3), 0*Z(3), Z(3)^0 ] ], [ ] ]
The next calculation shows that the quotient representation five maps its module at object 1 monomorphically to the module at object 2, which must either be indecomposable of dimension 3, or else the direct sum of indecomposables of dimension 2 and 1.
gap> SumOfImages(s1,five);
[ [ ], [ ] ]
gap> SumOfImages(ConstantRep(c3c3,GF(3)),five);
[ [ [ 0*Z(3), Z(3)^0 ] ], [ [ 0*Z(3), 0*Z(3), Z(3)^0 ] ] ]
The final calculation shows that the module at object 2 for six is indecomposable of dimension 3. We now have sufficient information to describe six completely.

gap> SumOfImages(six,ConstantRep(c3c3,GF(3)));
[ [ ], [ [ Z(3)^0 ] ] ]