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 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: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)h|h (2)(c)h|h(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. Thus every h:cch: c \to c is \sim-equivalent to a permutation σ:dd\sigma: d \to d.

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

σ=g 1f 1,f 1g 1=h 1=g 2f 2,,f n1g n1=h n1=g nf n,f ng n=τ\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 kh k jf k=g k(f kg k) jf k=(g kf k) j+1=h k1 j+1g_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 kh k1 jg k=h k j+1f_k h_{k-1}^j g_k = h_k^{j+1}) that

g 1g 2g n1g nf nf n1f 2f 1=σ n,f nf n1f 2f 1g 1g 2g n1g n=τ ng_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 nf 1f = f_n \ldots f_1 is invertible and τf=fσ\tau f = f \sigma, or τ=fσf 1\tau = f \sigma f^{-1}. Conversely, if τ=fσf 1\tau = f \sigma f^{-1}, then for g=σf 1g = \sigma f^{-1} we have σ=gf\sigma = g f and fg=τ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 FinSetFinSet is naturally identified with the class of finite Young diagrams.

Remark

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

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