Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For a natural number $n\in\mathbb{N}$, let $\underline{n}$ denote the finite set $$\underline{n}:=\{1,2,\ldots,n\}.$$ A permutation $\sigma\in Aut(\underline{n})$ can be uniquely written (up to order) as a product of disjoint cycles. To set an example we'll use $n^~_0=8$ and $$\sigma_0^~=(1247)(358)(6).$$

I'm looking for a categorical interpretation of this notion of maximal cycle decomposition. A bit more precisely, let $\mathcal{Bij}$ denote the symmetric monoidal category of finite ordinals $\underline{n}$ as objects, automorphisms as morphisms, and disjoint union as the monoidal structure. That is, $\mathcal{Bij}$ is a skeleton of $FinSet$. I'm looking for to understand maximal cycle decomposition category-theoretically in terms of $\mathcal{Bij}$.

My motivation comes from the fact that there is a trace on $\mathcal{Bij}$ whose definition is quite simply expressed in terms of the "disjoint cycle notation". Namely, suppose given a bijection $\sigma:X\sqcup U\to Y\sqcup U$ for which you want the trace $Tr^U_{X,Y}(\sigma):X\to Y$. To obtain it, simply write $\sigma$ in maximal cycle notation, and remove every element of $U$ you see.

The above formula is not precisely stated, which is exactly the problem---how can I state this formula precisely?---but it is quite easy to think about. An example will help.

Let $X=Y=\underline{5}$ and $U=\underline{3}$, and let $\sigma_0^~: X\sqcup U\to Y\sqcup U$ be $(1247)(358)(6)$ as above, where the elements of $X$ and $Y$ are denoted $1,2,3,4,5$ and the elements of $U$ are denoted $6,7,8$. Then the trace is given by $$Tr^U_{X,Y}(\sigma^~_0)=(124)(35).$$ We simply removed the elements of $U$ from the cycle notation and dropped of the now-empty cycle where $(6)$ was. (There is another traced monoidal category $\mathcal{Bij}'$ with the same objects, but which keeps track of the number of empty cycles.)

Category theoretically, we are just performing a trace. But this trick with disjoint cycle notation appears to be the simplest way to write the operation. How do we think about this strange but simple description?

share|improve this question
1) This is an interesting, if not really well-posed, question, and I'd much prefer an answer which gives a formal underpinning to the intuitive observation that disjoint cycle decomposition is a kind of $\mathbb{F}_1$-analogue of the Jordan canonical form. –  darij grinberg May 30 at 17:41
2) I think you need $X = Y$ for your definition of the cycle map. How do you decompose a bijection between two different sets into cycles? One way to define your trace map without referring to cycle notation is by saying that $Tr^{U}_{X,X}\left(\sigma\right)$ is the map which sends every $x \in X$ to $\sigma^i\left(x\right)$ where $i$ is the smallest positive integer such that $\sigma^i\left(x\right) \in X$. Not sure how categorical this is. –  darij grinberg May 30 at 17:42
The category of finite sets with a Z-action has a coproduct decomposition of each object into indecomposables. This is what gives cycle decomp. –  Benjamin Steinberg May 30 at 17:58
@BenjaminSteinberg, that's true. A permutation can be understood as a functor $\sigma:{\mathbb Z}\to{\bf Set}$, where ${\mathbb Z}$ is the free group on one generator, considered as a category with one object. If $F:{\mathbb Z}\to\{*\}$ is the unique functor to the terminal category, then the left Kan extension $F_!\sigma$ is the set of cycles, and the unit map $\sigma\to F^*F_!\sigma$ is in some sense the cycle decomposition of $\sigma$. However, this does not really help me because I don't know how to use it to compose elements of the group $S_n$, nor to see the trace map. –  David Spivak May 30 at 19:02
@DavidSpivak: oh, my apologies -- I forgot that you had taken the skeleton. Then it makes sense. These trace maps, for $U$ being $[1]$, occur in Okounkov/Vershik arXiv:math/0503040v3 p. 25, and I recall implementing them in sage (for general $U$) under the name retract_okounkov_vershik. Checking that the image is a permutation using my definition is not too hard: the inverse of the image of $\sigma$ is the image of $\sigma^{-1}$ (although the trace map is not a group morphism). –  darij grinberg May 30 at 19:19

1 Answer 1

up vote 7 down vote accepted

I'm not completely clear on what answer would be considered satisfactory, but here's one categorical way to think about tracing in $\mathbf{Bij}$.

The morphisms of the symmetric monoidal category with duals obtained by applying the Joyal-Street-Verity construction to $\mathbf{Bij}$ can be pictured in terms of string diagrams that are essentially 1-cobordisms, i.e, curves bounded by compact 0-manifolds that are built from string diagrams for permutations and from cups and caps (which are counits and units of dual pairs) by applying the usual composition and juxtaposition operations. Now cobordisms generally are certain types of cospans in the category of manifolds. Thus, what we can do is consider $\mathbf{Bij}$ (or more generally $\mathbf{Set}$) as embedded in the bicategory of cospans between sets, where a bijection or function $\sigma: A \to B$ is mapped to the cospan

$$A \stackrel{\sigma}{\to} B \stackrel{1_B}{\leftarrow} B.$$

Composition of cospans (i.e., of 1-cells)

$$(A \stackrel{f}{\to} B \stackrel{g}{\leftarrow} C) \; ; \; (C \stackrel{h}{\to} D \stackrel{k}{\leftarrow} E)$$

is obtained by taking the pushout of $g$ and $h$, and composing $f$ and $k$ with the pushout coprojections. The disjoint sum induces an obvious tensor product on cospans.

The category obtained by taking isomorphism classes of 1-cells is a symmetric monoidal category $\mathbf{Cospan}$ with duals, in which each object is dual to itself. This works in a manner dual to the situation for $\mathbf{Span}$, where the unit and counit are given by "equality predicates"; thus for each object $U$, the unit and counit of $U \dashv U$ are given by coequality cospans

$$\eta_U = (0 \to U \stackrel{\nabla_U}{\leftarrow} U + U), \qquad \epsilon_U = (U + U \stackrel{\nabla_U}{\to} U \leftarrow 0).$$

Thus, given a bijection $\sigma: A + U \to B + U$, the tracing $Tr_{A, B}^U(\sigma)$, given by a composite of cospans

$$A \cong A + 0 \stackrel{1_A + \eta_U}{\to} A + U + U \stackrel{\sigma + U}{\to} B + U + U \stackrel{1_B + \epsilon_U}{\to} B +0 \cong B,$$

can be read off by taking a pushout in $\mathbf{Set}$ of the diagram

$$A + U \stackrel{1_A + \nabla}{\leftarrow} (A + U + U \stackrel{\sigma + U}{\to} B + U + U \stackrel{1_B + \nabla_U}{\to} B + U) \qquad (1)$$

and then composing the pushout coprojections with the canonical inclusions $A \hookrightarrow A + U$, $B \hookrightarrow B + U$.

This gives a precise categorical description of the trace operation in terms of pushouts in $\mathbf{Set}$, but: it's the trace operation that pertains to the traced monoidal category denoted $\mathbf{Bij}'$ in the original post (where one keeps track of loops formed in the tracing process). If one wants to ignore loops that are formed by composing cospans, i.e., work with the traced monoidal category $\mathbf{Bij}$, one ought to work with co-relations instead of cospans.

By definition, a co-relation is a cospan $A \stackrel{f}{\to} C \stackrel{g}{\leftarrow} B$ such that the induced map $(f, g): A + B \to C$ is epic. In other words, a co-relation is a relation in the category $\mathbf{Set}^{op}$. One should pause to note that the power set functor $P: \mathbf{Set}^{op} \to \mathbf{Set}$ is monadic, and since a monadic category over $\mathbf{Set}$ is Barr exact and in particular a regular category, the usual calculus of relations goes through. In particular, to compose co-relations in $\mathbf{Set}$, one composes them as cospans but then one applies the epi-mono factorization to the composition cospan $(f, g): A + B \to C$; the epi part $q: A + B \to C'$ gives the composition co-relation. All the relevant structural features one had from $\mathbf{Cospan}$ carry over: $\mathbf{Corel}$ is a symmetric monoidal category in which each object is dual to itself, using the same formulas for the unit and counit of $U \dashv U$.

So, in summary, the result of the pushout (1) above induces a cospan from $A$ to $B$, and after applying the appropriate epi-mono factorization to get a co-relation, one can check that the result is a bijection from $A$ to $B$ (i.e., a cospan obtained by applying the inclusion functor $\mathbf{Bij} \hookrightarrow \mathbf{Corel}$ to a suitable bijection). This is the trace in $\mathbf{Bij}$.

It's not hard to see what is really going on. Tracing is basically the introduction of a feedback loop where outputs of $\sigma$ in $U$ are fed back in as inputs in $U$ living in $A + U$, and iterating through cycles until you exit $U$. That's exactly what the string diagram picture suggests (with the proviso that we are dealing with co-relation composition, which elides over free-floating loops where one never exits $U$). The meaning in terms of the cycle decomposition is hopefully clear. For instance, to take the example of the OP, we have in one of the cycles of $\sigma$ a path $5 \to 8$; this output $8 \in U$ is reinterpreted as an input where the next step in the cycle is $8 \to 3$, at which point we have exited out of $U$.

share|improve this answer
Can you point me to a reference for all this? In what context were you thinking about these ideas? –  David Spivak Jun 2 at 13:33
Actually your answer is not quite right, namely this part: "A priori, the result is a cospan from $A$ to $B$, but a little reflection shows that it's actually a bijection from $A$ to $B$ (i.e., a cospan obtained by applying the inclusion functor $\mathbf{Bij}\to \mathbf{Cospan}$ to a suitable bijection)." Consider the unique case in which $A=B=\emptyset$ and $U=\{1\}$. Then the cospan that results from applying your trace formula is $\emptyset\to\{1\}\leftarrow\emptyset$, which is not in the image of your inclusion functor. –  David Spivak Jun 2 at 13:44
My primary context is that I was around Street and Verity in Australia during the time the paper with Joyal was being written, and so I was exposed to the string diagram calculations that were being hashed out to get the results of the paper. I thought your specific example of $Bij$ was one of the examples mentioned in the Macquarie University Report that the final paper was based on. But let me try to get back to you later on this and your last comment. –  Todd Trimble Jun 2 at 13:50
Thanks. By the way, you're working in what I briefly referred to as $\mathbf{Bij'}$ above. –  David Spivak Jun 2 at 14:03
Yes, absolutely right. I fell into a very common trap. I have to go right now, but let me fix my answer later (and please feel free to unaccept it until it gets fixed). –  Todd Trimble Jun 2 at 14:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.