trace of a category

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.

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

$1 \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^*$ both a right and left adjoint of $c$: the adjunctions are ambidextrous). In the classical case where $C$ 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_c$, this defines $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 $C \to D$, i.e., functors

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

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

$\eta: 1 \to C^{op} \times C, \, \varepsilon: C^{op} \times C \to 1$

are given by $hom_{C^{op}}$ and $hom_C$. Composing these (according to the coend formula for profunctor composition) yields

$\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_C$ in $Prof$ (which as a functor is also given by $hom_C$); this coend is called the **trace** of the category $C$. It could also reasonably be called, by analogy with the vector space case, the **dimension** of the category $C$. The trace of a general endoprofunctor $F$ on $C$ is the coend

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

which generalizes the trace of linear functions:

$Tr(f) = \sum_i f_{i i}$

(where the matrix entries $f_{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 $V$, where the dimension of a small $V$-category $C$ is the object of $V$ given by the enriched coend

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

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: c \to c$ between finite sets, modulo the equivalence relation $\sim$ generated by the stipulation $f \circ g \sim g \circ f$ whenever $f: c \to d$ and $g: d \to c$ are functions between finite sets.

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

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

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

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

and this process iterates. The sequence of epis

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

eventually stabilizes (after finitely many steps) to a finite set $h^{(\infty)}(c)$ on which $h$ 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)