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 calculate 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. Thus every $h: c \to c$ is $\sim$-equivalent to a permutation $\sigma: d \to d$.

Furthermore, given two permutations $\sigma: c \to c$ and $\tau: d \to d$ such that $\sigma \sim \tau$ is witnessed by a chain of function equalities

$\sigma = g_1 f_1, \; f_1 g_1 = h_1 = g_2 f_2, \; \ldots, \; f_{n-1} g_{n-1} = h_{n-1} = g_n f_n, \; f_n g_n = \tau$

one may show (using $g_k h_k^j f_k = g_k (f_k g_k)^j f_k = (g_k f_k)^{j+1} = h_{k-1}^{j+1}$ and similarly $f_k h_{k-1}^j g_k = h_k^{j+1}$) that

$g_1 g_2 \ldots g_{n-1} g_n f_n f_{n-1} \ldots f_2 f_1 = \sigma^n, \qquad f_n f_{n-1} \ldots f_2 f_1 g_1 g_2 \ldots g_{n-1} g_n = \tau^n$

which implies that $f = f_n \ldots f_1$ is invertible and $\tau f = f \sigma$, or $\tau = f \sigma f^{-1}$. Conversely, if $\tau = f \sigma f^{-1}$, then for $g = \sigma f^{-1}$ we have $\sigma = g f$ and $f g = \tau$, so $\sigma \sim \tau$.

In other words, the trace of the category of finite sets is isomorphic to the trace of the underlying groupoid of finite sets and bijections, where the equivalence classes with respect to $\sim$ are the conjugacy classes of permutations, given by cycle types. In this way, the trace of $FinSet$ is naturally identified with the class of finite Young diagrams.

Furthermore, the functorial operations $\hom(x, x) \times \hom(y, y) \to \hom(x \times x, y \times y)$ and $\hom(x, x) \times \hom(y, y) \to \hom(x + y, x + y)$ induce operations $\cdot: Tr(FinSet) \times Tr(FinSet) \to Tr(FinSet)$ and $+: Tr(FinSet) \times Tr(FinSet) \to Tr(FinSet)$. Since $\times$ distributes over $+$ in $FinSet$, we obtain a rig structure on $Tr(FinSet)$, namely the Burnside rig of $\mathbb{Z}$.

Revised on September 27, 2016 10:03:52
by Todd Trimble
(67.81.95.215)