nLab
trace of a category

The trace of a category

Idea

The trace of a category (or more generally of an endobimodule or endoprofunctor) is a categorification of the trace of a linear endomorphism on a finite dimensional vector space (that is a matrix).

A notion of trace is generally definable for maps in a compact closed category (even more generally in a traced monoidal category), and here the idea is to categorify this to the context of compact closed bicategories, in particular the bicategory of bimodules between small categories.

Definition

Let CC be a compact closed symmetric monoidal category, with monoidal product \otimes and monoidal unit 11. The trace of an endomorphism f:ccf: c \to c is the composite

1ηc *c1 c *fc *cε11 \overset{\eta}{\to} c^* \otimes c \overset{1_{c^*} \otimes f}{\to} c^* \otimes c \overset{\varepsilon}{\to} 1

where η\eta is a unit and ε\varepsilon is a counit of appropriate adjunctions (note that the symmetry makes the dual c *c^* both a right and left adjoint of cc: the adjunctions are ambidextrous). In the classical case where CC is the category of finite-dimensional vector spaces with its usual monoidal structure, this gives the usual trace of an endomorphism; in particular, for f=1 cf = 1_c, this defines dim(c)hom(1,1)dim(c) \in hom(1, 1).

The same idea applies to compact closed symmetric monoidal bicategories. In particular, it applies to the bicategory Prof whose objects are small categories, whose 1-morphisms are profunctors CDC \to D, i.e., functors

R:D op×CSetR: D^{op} \times C \to Set

and whose 2-morphisms are natural transformations between profunctors. The bicategory ProfProf is a cartesian bicategory and hence symmetric monoidal under ×\times, and is also compact closed: the dual of a category CC in this case is just the opposite category C opC^{op}, and the unit and counit profunctors

η:1C op×C,ε:C op×C1\eta: 1 \to C^{op} \times C, \, \varepsilon: C^{op} \times C \to 1

are given by hom C ophom_{C^{op}} and hom Chom_C. Composing these (according to the coend formula for profunctor composition) yields

c,cOb(C)hom(c,c)×hom(c,c) chom(c,c)\int^{c, c' \in Ob(C)} hom(c, c') \times hom(c', c) \cong \int^c hom(c, c)

and this is the trace of the identity 1 C1_C in ProfProf (which as a functor is also given by hom Chom_C); this coend is called the trace of the category CC. It could also reasonably be called, by analogy with the vector space case, the dimension of the category CC. The trace of a general endoprofunctor FF on CC is the coend

cOb(C)F(c,c)\int^{c \in Ob(C)} F(c, c)

which generalizes the trace of linear functions:

Tr(f)= if iiTr(f) = \sum_i f_{i i}

(where the matrix entries f ijf_{i j} are computed with respect to any basis).

The foregoing discussion can be generalized to the case of bimodules between small categories enriched in a cocomplete symmetric monoidal closed category VV, where the dimension of a small VV-category CC is the object of VV given by the enriched coend

chom(c,c)\int^c hom(c, c)

Example

We sketch the calculation of the trace or dimension of FinSet, the category of finite sets. The calculation is quite down-to-earth: the relevant coend is just the quotient of the set of all endofunctions h:cch: c \to c between finite sets, modulo the equivalence relation \sim generated by the stipulation fggff \circ g \sim g \circ f whenever f:cdf: c \to d and g:dcg: d \to c are functions between finite sets.

Let h:cch: c \to c be a finite endofunction, and let

cpdicc \overset{p}{\to} d \overset{i}{\to} c

be its epi-mono factorization. Then h=(ip)(pi)h = (i \circ p) \sim (p \circ i); if we think of dd as the image h(c)h(c), then pip \circ i can be viewed as the restriction

h:h(c)h(c){h|}\colon h(c) \to h(c)

and this process iterates. The sequence of epis

h(c)hh (2)(c)hh(c) \overset{h|}{\to} h^{(2)}(c) \overset{h|}{\to} \ldots

eventually stabilizes (after finitely many steps) to a finite set h ()(c)h^{(\infty)}(c) on which hh restricts to a surjective endofunction, which is a bijection since we are dealing with finite sets.

This argument shows that the trace of the category of finite sets is isomorphic to the trace of the underlying groupoid of finite sets and bijections. Here the equivalence classes with respect to \sim are the conjugacy classes of permutations; in this way, the trace can be identified with the class of finite Young diagrams.

Revised on October 12, 2013 22:08:35 by Toby Bartels (98.19.41.253)