Theory and Applications of Categories, Vol. 30, No. 24, 2015, pp. 836–881.

CATEGORIES IN CONTROL

JOHN C. BAEZ AND JASON ERBELE

Abstract. Control theory uses ‘signal-flow diagrams’ to describe processes where realvalued functions of time are added, multiplied by scalars, differentiated and integrated, duplicated and deleted. These diagrams can be seen as string diagrams for the symmetric monoidal category FinVect_{k} of finite-dimensional vector spaces over the field of rational functions k = ℝ(s), where the variable s acts as differentiation and the monoidal structure is direct sum rather than the usual tensor product of vector spaces. For any field k we give a presentation of FinVect_{k} in terms of the generators used in signalflow diagrams. A broader class of signal-flow diagrams also includes ‘caps’ and ‘cups’ to model feedback. We show these diagrams can be seen as string diagrams for the symmetric monoidal category FinRel_{k}, where objects are still finite-dimensional vector spaces but the morphisms are linear relations. We also give a presentation for FinRel_{k}. The relations say, among other things, that the 1-dimensional vector space k has two special commutative †-Frobenius structures, such that the multiplication and unit of either one and the comultiplication and counit of the other fit together to form a bimonoid. This sort of structure, but with tensor product replacing direct sum, is familiar from the ‘ZX-calculus’ obeyed by a finite-dimensional Hilbert space with two mutually unbiased bases.

1. Introduction

Control theory is the branch of engineering that focuses on manipulating ‘open systems’— systems with inputs and outputs—to achieve desired goals. In control theory, ‘signal-flow diagrams’ are used to describe linear ways of manipulating signals, which we will take here to be smooth real-valued functions of time [10]. For a category theorist, at least, it is natural to treat signal-flow diagrams as string diagrams in a symmetric monoidal category [11, 12]. This forces some small changes of perspective, which we discuss below, but more important is the question: which symmetric monoidal category?

We shall argue that the answer is: the category FinRel_{k} of finite-dimensional vector spaces over a certain field k, but with linear relations rather than linear maps as morphisms, and direct sum rather than tensor product providing the symmetric monoidal structure. We use the field k = ℝ(s) consisting of rational functions in one real variable s. This variable has the meaning of differentiation. A linear relation from k^{m} to k^{n} is thus a system of linear constant-coefficient ordinary differential equations relating m ‘input’ signals and n ‘output’ signals.

Received by the editors 2014-12-17 and, in revised form, 2015-06-21. Transmitted by Tom Leinster. Published on 2015-06-26. 2010 Mathematics Subject Classification: 18D10, 16T10. Key words and phrases: control theory, graphical calculus, Frobenius algebra, bialgebra, dagger-

compact category, signal-flow diagram.

\begin{matrix}c \\ ◯ \end{matrix} John C. Baez and Jason Erbele, 2015. Permission to copy for private use granted.

Our main goal is to provide a complete ‘generators and relations’ picture of this symmetric monoidal category, with the generators being familiar components of signal-flow diagrams. It turns out that the answer has an intriguing but mysterious connection to ideas that are familiar in the diagrammatic approach to quantum theory. Quantum theory also involves linear algebra, but it uses linear maps between Hilbert spaces as morphisms, and the tensor product of Hilbert spaces provides the symmetric monoidal structure.

We hope that the category-theoretic viewpoint on signal-flow diagrams will shed new light on control theory. However, in this paper we only lay the groundwork. In Section 2 we introduce signal-flow diagrams and summarize our main results. In Section 3 we use signal-flow diagrams to give a presentation of FinVect_{k}, the symmetric monoidal category of finite-dimensional vector spaces and linear maps. In Section 4 we use them to give a presentation of FinRel_{k}. In Section 5 we discuss a well-known example from control theory: an inverted pendulum on a cart. Finally, in Section 6 we compare our results to subsequent work of Bonchi–Sobociński–Zanasi [4, 5] and Wadsley–Woods [22].

2. Signal-flow diagrams

There are several basic operations that one wants to perform when manipulating signals. The simplest is multiplying a signal by a scalar. A signal can be amplified by a constant factor:

f ↦ cf

where c ∈ ℝ. We can write this as a string diagram:

\begin{matrix}f \\ c \\ cf \end{matrix}

Here the labels f and cf on top and bottom are just for explanatory purposes and not really part of the diagram. Control theorists often draw arrows on the wires, but this is unnecessary from the string diagram perspective. Arrows on wires are useful to distinguish objects from their duals, but ultimately we will obtain a compact closed category where each object is its own dual, so the arrows can be dropped. What we really need is for the box denoting scalar multiplication to have a clearly defined input and output. This is why we draw it as a triangle. Control theorists often use a rectangle or circle, using arrows on wires to indicate which carries the input f and which the output cf.

A signal can also be integrated with respect to the time variable:

f ↦ ∫ f.

Mathematicians typically take differentiation as fundamental, but engineers sometimes prefer integration, because it is more robust against small perturbations. In the end it will not matter much here. We can again draw integration as a string diagram:

f∫∫ f

Since this looks like the diagram for scalar multiplication, it is natural to extend ℝ to ℝ(s), the field of rational functions of a variable s which stands for differentiation. Then differentiation becomes a special case of scalar multiplication, namely multiplication by s, and integration becomes multiplication by 1/s. Engineers accomplish the same effect with Laplace transforms, since differentiating a signal f is equivalent to multiplying its Laplace transform

(Lf)(s) = ∫_{0}^{∞} f(t)e^{−st} dt

by the variable s. Another option is to use the Fourier transform: differentiating f is equivalent to multiplying its Fourier transform

(Ff)(ω) = ∫_{−∞}^{∞} f(t)e^{−iωt} dt

by −iω. Of course, the function f needs to be sufficiently well-behaved to justify calculations involving its Laplace or Fourier transform. At a more basic level, it also requires some work to treat integration as the two-sided inverse of differentiation. Engineers do this by considering signals that vanish for t < 0, and choosing the antiderivative that vanishes under the same condition. Luckily all these issues can be side-stepped in a formal treatment of signal-flow diagrams: we can simply treat signals as living in an unspecified vector space over the field ℝ(s). The field ℂ(s) would work just as well, and control theory relies heavily on complex analysis. In most of this paper we work over an arbitrary field k.

The simplest possible signal processor is a rock, which takes the ‘input’ given by the force F on the rock and produces as ‘output’ the rock’s position q. Thanks to Newton’s second law F = ma, we can describe this using a signal-flow diagram:

q∫v∫a\frac{1}{m} F

Here composition of morphisms is drawn in the usual way, by attaching the output wire of one morphism to the input wire of the next.

To build more interesting machines we need more building blocks, such as addition:

+: (f, g) ↦ f + g

and duplication:

Δ: f ↦ (f, f)

When these linear maps are written as matrices, their matrices are transposes of each other. This is reflected in the string diagrams for addition and duplication:

\begin{matrix}f \\ g \\ f + g \end{matrix}  \begin{matrix}f \\ f \\ f \end{matrix}

The second is essentially an upside-down version of the first. However, we draw addition as a dark triangle and duplication as a light one because we will later want another way to ‘turn addition upside-down’ that does not give duplication. As an added bonus, a light upside-down triangle resembles the Greek letter Δ, the usual symbol for duplication.

While they are typically not considered worthy of mention in control theory, for completeness we must include two other building blocks. One is the zero map from {0} to our field k, which we denote as 0 and draw as follows:

The other is the zero map from k to {0}, sometimes called ‘deletion’, which we denote as ! and draw thus:

f

Just as the matrices for addition and duplication are transposes of each other, so are the matrices for zero and deletion, though they are rather degenerate, being 1×0 and 0×1 matrices, respectively. Addition and zero make k into a commutative monoid, meaning that the following relations hold:

=  =  =

The equation at right is the commutative law, and the crossing of strands is the ‘braiding’

B: (f, g) ↦ (g, f)

by which we switch two signals. In fact this braiding is a ‘symmetry’, so it does not matter which strand goes over which:

\begin{matrix}f \\ f \\ g \\ g \end{matrix}  =  \begin{matrix}f \\ f \\ g \\ g \end{matrix}

Dually, duplication and deletion make k into a cocommutative comonoid. This means that if we reflect the equations obeyed by addition and zero across the horizontal axis and turn dark operations into light ones, we obtain another set of valid equations:

=  =  =

There are also relations between the monoid and comonoid operations. For example, adding two signals and then duplicating the result gives the same output as duplicating each signal and then adding the results:

\begin{matrix}f \\ g \\ f + g \\ f + g \end{matrix} =  \begin{matrix}f \\ g \\ f + g \\ f + g \end{matrix}

This diagram is familiar in the theory of Hopf algebras, or more generally bialgebras. Here it is an example of the fact that the monoid operations on k are comonoid homomorphisms– or equivalently, the comonoid operations are monoid homomorphisms. We summarize this situation by saying that k is a bimonoid.

So far all our string diagrams denote linear maps. We can treat these as morphisms in the category FinVect_{k}, where objects are finite-dimensional vector spaces over a field k and morphisms are linear maps. This category is equivalent to a skeleton where the only objects are vector spaces k^{n} for n ≥ 0, and then morphisms can be seen as n×m matrices. The space of signals is a vector space V over k which may not be finite-dimensional, but this does not cause a problem: an n × m matrix with entries in k still defines a linear map from V^{n} to V^{m} in a functorial way.

In applications of string diagrams to quantum theory [3, 8], we make FinVect_{k} into a symmetric monoidal category using the tensor product of vector spaces. In control theory, we instead make FinVect_{k} into a symmetric monoidal category using the direct sum of vector spaces. In Lemma 3.1 we prove that for any field k, FinVect_{k} with direct sum is generated as a symmetric monoidal category by the one object k together with these morphisms:

c

where c ∈ k is arbitrary.

However, these generating morphisms obey some unexpected relations! For example, we have:

\begin{matrix}= \\ −1 \\ −1 \end{matrix}

Thus, it is important to find a complete set of relations obeyed by these generating morphisms, thus obtaining a presentation of FinVect_{k} as a symmetric monoidal category. We do this in Theorem 3.2. In brief, these relations say:

1. (k, +, 0, Δ,!) is a bicommutative bimonoid;

2. the rig operations of k can be recovered from the generating morphisms;

3. all the generating morphisms commute with scalar multiplication.

Here item (2) means that +, ·, 0 and 1 in the field k can be expressed in terms of signal-flow diagrams as follows:

\begin{matrix}b+c \\ = \\ b \\ c \end{matrix}  \begin{matrix}c \\ b \\ = \\ bc \end{matrix}  1=  0=

Multiplicative inverses cannot be so expressed, so our signal-flow diagrams so far do not know that k is a field. Additive inverses also cannot be expressed in this way. And indeed, a version of Theorem 3.2 holds whenever k is a commutative rig: that is, a commutative ‘ring without negatives’, such as ℕ. See Section 6 for details.

While Theorem 3.2 is a step towards understanding the category-theoretic underpinnings of control theory, it does not treat signal-flow diagrams that include ‘feedback’. Feedback is one of the most fundamental concepts in control theory because a control system without feedback may be highly sensitive to disturbances or unmodeled behavior. Feedback allows these uncontrolled behaviors to be mollified. As a string diagram, a basic feedback system might look schematically like this:

reference a controller measured error system input bsystem system output c sensor measured output

−1

The user inputs a ‘reference’ signal, which is fed into a controller, whose output is fed into a system, or ‘plant’, which in turn produces its own output. But then the system’s output is duplicated, and one copy is fed into a sensor, whose output is added (or if we prefer, subtracted) from the reference signal.

In string diagrams—unlike in the usual thinking on control theory—it is essential to be able to read any diagram from top to bottom as a composite of tensor products of generating morphisms. Thus, to incorporate the idea of feedback, we need two more generating morphisms. These are the ‘cup’:

\begin{matrix}f = g \\ f \\ g \end{matrix}

and ‘cap’:

\begin{matrix}f = g \\ f \\ g \end{matrix}

These are not maps: they are relations. The cup imposes the relation that its two inputs be equal, while the cap does the same for its two outputs. This is a way of describing how a signal flows around a bend in a wire.

To make this precise, we use a category called FinRel_{k}. An object of this category is a finite-dimensional vector space over k, while a morphism from U to V, denoted L: U ↛ V, is a linear relation, meaning a linear subspace

L ⊆ U ⊕ V.

In particular, when k = ℝ(s), a linear relation L: k^{m} → k^{n} is just an arbitrary system of constant-coefficient linear ordinary differential equations relating m input variables and n output variables.

Since the direct sum U ⊕ V is also the cartesian product of U and V, a linear relation is indeed a relation in the usual sense, but with the property that if u ∈ U is related to v ∈ V and u′ ∈ U is related to v′ ∈ V then cu + c′u′ is related to cv + c′v′ whenever c, c′ ∈ k. We compose linear relations L: U ↛ V and L′: V ↛ W as follows:

L′L = {(u, w): ∃ v ∈ V (u, v) ∈ L and (v, w) ∈ L′}.

Any linear map f: U → V gives a linear relation F: U ↛ V, namely the graph of that map:

F = {(u, f(u)) : u ∈ U}.

Composing linear maps thus becomes a special case of composing linear relations, so FinVect_{k} becomes a subcategory of FinRel_{k}. Furthermore, we can make FinRel_{k} into a monoidal category using direct sums, and it becomes symmetric monoidal using the braiding already present in FinVect_{k}.

In these terms, the cup is the linear relation

∪: k^{2} ↛ {0}

given by

∪ = {(x, x, 0) : x ∈ k} ⊆ k^{2} ⊕ {0},

while the cap is the linear relation

∩: {0} ↛ k^{2}

given by

∩ = {(0, x, x) : x ∈ k} ⊆ {0} ⊕ k^{2}.

These obey the zigzag relations:

=

Thus, they make FinRel_{k} into a compact closed category where k, and thus every object, is its own dual.

Besides feedback, one of the things that make the cap and cup useful is that they allow any morphism L: U ↛ V to be ‘plugged in backwards’ and thus ‘turned around’. For instance, turning around integration:

∫:= ∫

we obtain differentiation. In general, using caps and cups we can turn around any linear relation L: U ↛ V and obtain a linear relation L^{†}: V ↛ U, called the adjoint of L, which turns out to given by

L^{†} = {(v, u) : (u, v) ∈ L}.

For example, if c ∈ k is nonzero, the adjoint of scalar multiplication by c is multiplication by c^{−1}:

c= c^{−1} := c

Thus, caps and cups allow us to express multiplicative inverses in terms of signal-flow diagrams! One might think that a problem arises when c = 0, but no: the adjoint of scalar multiplication by 0 is

{(0, x) : x ∈ k} ⊆ k ⊕ k.

In Lemma 4.1 we show that FinRel_{k} is generated, as a symmetric monoidal category, by these morphisms:

c

where c ∈ k is arbitrary.

In Theorem 4.2 we find a complete set of relations obeyed by these generating morphisms, thus giving a presentation of FinRel_{k} as a symmetric monoidal category. To describe these relations, it is useful to work with adjoints of the generating morphisms. We have already seen that the adjoint of scalar multiplication by c is scalar multiplication by c^{−1}, except when c = 0. Taking adjoints of the other four generating morphisms of FinVect_{k}, we obtain four important but perhaps unfamiliar linear relations. We draw these as ‘turned around’ versions of the original generating morphisms:

• Coaddition is a linear relation from k to k^{2} that holds when the two outputs sum

to the input:

+^{†}: k ↛ k^{2}
+^{†} = {(x, y, z) : x = y + z} ⊆ k ⊕ k^{2}

:=

• Cozero is a linear relation from k to {0} that holds when the input is zero:

0^{†}: k ↛ {0}
0^{†} = {(0, 0)} ⊆ k ⊕ {0}

:=

• Coduplication is a linear relation from k^{2} to k that holds when the two inputs

both equal the output:

Δ^{†}: k^{2} ↛ k
Δ^{†} = {(x, y, z) : x = y = z} ⊆ k^{2} ⊕ k

:=

• Codeletion is a linear relation from {0} to k that holds always:

!^{†}: {0} ↛ k
!^{†} = {(0, x)} ⊆ {0} ⊕ k

:=

Since +^{†}, 0^{†}, Δ^{†} and !^{†} automatically obey turned-around versions of the relations obeyed by +, 0, Δ and !, we see that k acquires a second bicommutative bimonoid structure when considered as an object in FinRel_{k}.

Moreover, the four dark operations make k into a Frobenius monoid. This means that (k, +, 0) is a monoid, (k, +^{†}, 0^{†}) is a comonoid, and the Frobenius relation holds:

=

All three expressions in this equation are linear relations saying that the sum of the two inputs equal the sum of the two outputs.

The operation sending each linear relation to its adjoint extends to a contravariant functor

†: FinRel_{k} → FinRel_{k},

which obeys a list of properties that are summarized by saying that FinRel_{k} is a ‘†- compact’ category [1, 20]. Because two of the operations in the Frobenius monoid (k, +, 0, +^{†}, 0^{†}) are adjoints of the other two, it is a †-Frobenius monoid. This Frobenius monoid is also special, meaning that comultiplication (in this case +^{†}) followed by multiplication (in this case +) equals the identity:

=

This Frobenius monoid is also commutative—and cocommutative, but for Frobenius monoids this follows from commutativity.

Starting around 2008, commutative special †-Frobenius monoids have become important in the categorical foundations of quantum theory, where they can be understood as ‘classical structures’ for quantum systems [9, 21]. The category FinHilb of finitedimensional Hilbert spaces and linear maps is a †-compact category, where any linear map f: H → K has an adjoint f^{†}: K → H given by

⟨f^{†}ϕ, ψ⟩ = ⟨ϕ, fψ⟩

for all ψ ∈ H, ϕ ∈ K. A commutative special †-Frobenius monoid in FinHilb is then the same as a Hilbert space with a chosen orthonormal basis. The reason is that given an orthonormal basis ψ_{i} for a finite-dimensional Hilbert space H, we can make H into a commutative special †-Frobenius monoid with multiplication m: H ⊗ H → H given by

m(ψ_{i} ⊗ ψ_{j}) = \{ \begin{matrix}ψ_{i} & i = j \\ 0 & i ≠ j \end{matrix}

and unit i: ℂ → H given by

i(1) = ∑_{i} ψ_{i}.

The comultiplication m^{†} duplicates basis states:

m^{†}(ψ_{i}) = ψ_{i} ⊗ ψ_{i}.

Conversely, any commutative special †-Frobenius monoid in FinHilb arises this way.

Considerably earlier, around 1995, commutative Frobenius monoids were recognized as important in topological quantum field theory. The reason, ultimately, is that the free symmetric monoidal category on a commutative Frobenius monoid is 2Cob, the category with 2-dimensional oriented cobordisms as morphisms: see Kock’s textbook [13] and the many references therein. But the free symmetric monoidal category on a commutative special Frobenius monoid was worked out even earlier [6, 14, 19]: it is the category with finite sets as objects, where a morphism f: X → Y is an isomorphism class of cospans

X ⟶ S ⟵ Y.

This category can be made into a †-compact category in an obvious way, and then the 1-element set becomes a commutative special †-Frobenius monoid.

For all these reasons, it is interesting to find a commutative special †-Frobenius monoid lurking at the heart of control theory! However, the Frobenius monoid here has yet another property, which is more unusual. Namely, the unit 0: {0} ↛ k followed by the counit 0^{†}: k ↛ {0} is the identity:

=

We call a special Frobenius monoid that also obeys this extra law extra-special. One can check that the free symmetric monoidal category on a commutative extra-special Frobenius monoid is the category with finite sets as objects, where a morphism f: X → Y is an equivalence relation on the disjoint union X ⊔ Y, and we compose f: X → Y and g: Y → Z by letting f and g generate an equivalence relation on X ⊔ Y ⊔ Z and then restricting this to X ⊔ Z.

As if this were not enough, the light operations share many properties with the dark ones. In particular, these operations make k into a commutative extra-special †-Frobenius monoid in a second way. In summary:

• (k, +, 0, Δ,!) is a bicommutative bimonoid;

• (k, Δ^{†},!^{†}, +^{†}, 0^{†}) is a bicommutative bimonoid;

• (k, +, 0, +^{†}, 0^{†}) is a commutative extra-special †-Frobenius monoid;

• (k, Δ^{†},!^{†}, Δ,!) is a commutative extra-special †-Frobenius monoid.

It should be no surprise that with all these structures built in, signal-flow diagrams are a powerful method of designing processes. However, it is surprising that most of these structures are present in a seemingly very different context: the so-called ‘ZX calculus’, a diagrammatic formalism for working with complementary observables in quantum theory [7]. This arises naturally when one has an n-dimensional Hilbert space H with two orthonormal bases ψ_{i}, ϕ_{i} that are ‘mutually unbiased’, meaning that

|⟨ψ_{i}, ϕ_{j}⟩|^{2} = \frac{1}{n}

for all 1 ≤ i, j ≤ n. Each orthonormal basis makes H into commutative special †- Frobenius monoid in FinHilb. Moreover, the multiplication and unit of either one of these Frobenius monoids fits together with the comultiplication and counit of the other to form a bicommutative bimonoid. So, we have all the structure present in the list above—except that these Frobenius monoids are only extra-special if H is 1-dimensional.

The field k is also a 1-dimensional vector space, but this is a red herring: in FinRel_{k} every finite-dimensional vector space naturally acquires all four structures listed above, since addition, zero, duplication and deletion are well-defined and obey all the relations we have discussed. We focus on k in this paper simply because it generates all the objects FinRel_{k} via direct sum.

Finally, in FinRel_{k} the cap and cup are related to the light and dark operations as follows:

=  =^{−1}

CATEGORIES IN CONTROL  849

Note the curious factor of −1 in the second equation, which breaks some of the symmetry we have seen so far. This equation says that two elements x, y ∈ k sum to zero if and only if −x = y. Using the zigzag relations, the two equations above give

=_{−1}

We thus see that in FinRel_{k}, both additive and multiplicative inverses can be expressed in terms of the generating morphisms used in signal-flow diagrams.

Theorem 4.2 gives a presentation of FinRel_{k} based on the ideas just discussed. Briefly, it says that FinRel_{k} is equivalent to the symmetric monoidal category generated by an object k and these morphisms:

1. addition +: k^{2} ↛ k

2. zero 0: {0} ↛ k

3. duplication Δ: k ↛ k^{2}

4. deletion !: k ↛ 0

5. scalar multiplication c: k ↛ k for any c ∈ k

6. cup ∪: k^{2} ↛ {0}

7. cap ∩: {0} ↛ k^{2} obeying these relations:

1. (k, +, 0, Δ,!) is a bicommutative bimonoid;

2. ∩ and ∪ obey the zigzag equations;

3. (k, +, 0, +^{†}, 0^{†}) is a commutative extra-special †-Frobenius monoid;

4. (k, Δ^{†},!^{†}, Δ,!) is a commutative extra-special †-Frobenius monoid;

5. the field operations of k can be recovered from the generating morphisms;

6. the generating morphisms (1)-(4) commute with scalar multiplication. Note that item (2) makes FinRel_{k} into a †-compact category, allowing us to mention the adjoints of generating morphisms in the subsequent relations. Item (5) means that +, ·, 0, 1 and also additive and multiplicative inverses in the field k can be expressed in terms of signal-flow diagrams in the manner we have explained.

3. A presentation of FinVect_{k}

Our goal in this section is to find a presentation for the symmetric monoidal category FinVect_{k}. To simplify some technicalities, we shall use Mac Lane’s coherence theorem [17] to choose a symmetric monoidal equivalence F: FinVect′_{k} → FinVect_{k} where FinVect′_{k} is strict. This allows us to avoid mentioning associators and unitors, since in FinVect′_{k} these are identity morphisms. In what follows, we call FinVect′_{k} simply FinVect_{k}, and call objects and morphisms in FinVect_{k} by the names of their images under F. Colloquially speaking, we ‘work in a strict version’ of FinVect_{k}, and do not bother to indicate that this is a different (though equivalent) symmetric monoidal category.

We say a strict symmetric monoidal category C is generated by a set O of objects and a set M of morphisms going between tensor products of objects in O if the smallest subcategory C_{0} of C containing:

• the objects in O,

• the morphisms in M,

• the tensor products of any objects or morphisms in C_{0}

• the braiding for any pair of objects in C_{0}

has the property that the inclusion i: C_{0} → C is an equivalence of categories. It follows that i extends to an equivalence of symmetric monoidal categories. In this situation we call the elements of O generating objects for C, and call the elements of M generating morphisms.

3.1. Lemma. For any field k, the object k together with the morphisms:

1. scalar multiplication c: k → k for any c ∈ k

2. addition +: k ⊕ k → k

3. zero 0: {0} → k

4. duplication Δ: k → k ⊕ k

5. deletion !: k → {0}

generate FinVect_{k}, the category of finite-dimensional vector spaces over k and linear maps, as a symmetric monoidal category.

Proof. It suffices to show that k together with the morphisms in (1)–(5) generate the full subcategory of FinVect_{k} containing only the iterated direct sums k^{n} = k ⊕ ⋯ ⊕ k, since this is equivalent to FinVect_{k}.

A linear map in FinVect_{k}, T: k^{m} → k^{n} can be expressed as n k-linear combinations of m elements of k. That is, T (k_{1}, …, k_{m}) = (∑_{j} a_{1j}k_{j}, …, ∑_{j} a_{nj}k_{j}), a_{ij} ∈ k. Any k-linear combination of r elements can be constructed with only addition, multiplication, and zero, with zero only necessary when providing the unique k-linear combination for r = 0. When r = 1, a_{1}(k_{1}) is an arbitrary k-linear combination. For r > 1, +(S_{r−1}, a_{r}(k_{r})) yields an arbitrary k-linear combination on r elements, where S_{r−1} is an arbitrary k-linear combination of r − 1 elements. The inclusion of duplication allows process of forming klinear combinations to be repeated an arbitrary (finite) positive number of times, and deletion allows the process to be repeated zero times. When n k-linear combinations are needed, each input may be duplicated n−1 times. Because FinVect_{k} is being generated as a symmetric monoidal category, the mn outputs can then be permuted into n collections of m outputs: one output from each input for each collection. Each collection can then form a k-linear combination, as above. The following diagrams illustrate the pieces that form this inductive argument.

\begin{matrix}k_{1} \\ a_{1} \\ a_{1}k_{1} \end{matrix}  ^{∑_{j=1}^{r−1} a_{j}k_{j} a_{r} k_{r} ∑_{j=1}^{r} a_{j}k_{j}}  \begin{matrix}k_{1} \\ a_{i1} \\ a_{i1}k_{1} \\ k_{1} \end{matrix}  ^{∑_{j=1}^{r−1} a_{ij}k_{j} k_{r} ∑_{j=1}^{r} a_{ij}k_{j} a_{ir} k_{r}}

Since multiplication provides the map k_{1} ↦ a_{1}k_{1}, as in the far left diagram, the middle-left diagram can be used inductively to form a k-linear combination of any number of inputs. In particular, we have any linear map S_{r}: k^{m} → k given by (k_{1}, …, k_{m}) ↦ (∑_{j} a_{rj}k_{j}). Using duplication as in the middle-right diagram, one can produce the map k_{1} ↦ (k_{1}, a_{i1}k_{1}), to which the right diagram can be inductively applied. Thus we can build any linear map, T_{j} ∈ FinVect_{k}, T_{j}: k^{m} → k^{m+1} given by (k_{1}, …, k_{m}) ↦ (k_{1}, …, k_{m}, ∑_{j} a_{ij}k_{j}). If we represent the identity map on k^{r} as 1^{r}, the r-fold tensor product of the identity map on k, any linear map T: k^{m} → k^{n} can be given by (k_{1}, …, k_{m}) ↦ (∑_{j} a_{1j}k_{j}, …, ∑_{j} a_{nj}k_{j}), which can be expressed as T = (S_{1} ⊕ 1^{n−1})(T_{2} ⊕ 1^{n−2}) ⋯ (T_{n−1} ⊕ 1^{1})T_{n}. The above works as long as the vector spaces are not 0-dimensional. f: k^{m} → {0} can be written as an m-fold tensor product of deletion, !^{m}, and f: {0} → k^{n} can be written as an n-fold tensor product of zero, 0^{n}. f: {0} → {0} is the empty morphism, which has an empty diagram for its string diagram.

It is easy to see that the morphisms given in Lemma 3.1 obey the following 18 relations: (1)–(3) Addition and zero make k into a commutative monoid:

=  =  =

(4)–(6) Duplication and deletion make k into a cocommutative comonoid:

=  =  =

(7)–(10) The monoid and comonoid structures on k fit together to form a bimonoid:

=  =  =  =

(11)–(14) The rig structure of k can be recovered from the generating morphisms:

\begin{matrix}c \\ b \\ = \\ bc \end{matrix}  \begin{matrix}b+c \\ = \\ b \\ c \end{matrix}  1=  0=

(15)–(16) Scalar multiplication commutes with addition and zero:

\begin{matrix}c \\ c \end{matrix}  = c  \begin{matrix}c \\ = \end{matrix}

(17)–(18) Scalar multiplication commutes with duplication and deletion:

\begin{matrix}c \\ c \end{matrix}  = c  \begin{matrix}c \\ = \end{matrix}

In fact, these relations are enough. That is, together with the generating objects and morphisms, they give a ‘presentation’ of FinVect_{k} as a symmetric monoidal category. However, we need to make this concept precise.

Suppose C is generated by a set O of objects and a set M of morphisms going between tensor products of objects in O. Define a formal morphism to be a formal expression built from symbols for morphisms in M via composition, identity morphisms, tensor product, the unit object and the braiding. Any formal morphism f can be evaluated to obtain a morphism ev(f) in C, which actually lies in C_{0}.

Define a relation to be a pair f, g of formal morphisms. We say the relation holds in C if ev(f) = ev(g). Suppose R is a set of relations that hold in C. We say (O, M, R) is a presentation of C if given any two formal morphisms j, k that evaluate to the same morphism, then we can go from j to k via a finite sequence of moves of these kinds:

1. replacing an instance of a generating morphism f in a formal morphism by the generating morphism g, where (f, g) ∈ R,

2. applying an equational law in the definition of strict symmetric monoidal category to a formal morphism.

In intuitive terms, this means that there are enough relations to prove all the equations that hold in C—or more precisely, in the equivalent category C_{0}.

3.2. Theorem. The symmetric monoidal category FinVect_{k} is presented by the object k, the morphisms given in Lemma 3.1, and relations (1)–(18) as listed above.

Proof. To prove this, we show that these relations suffice to rewrite any formal morphism into a standard form, with all formal morphisms that evaluate to the same morphism T: k^{m} → k^{n} in FinVect_{k} having the same standard form. To deal with moves of type (2), we draw formal morphisms as string diagrams built from generating morphisms and the braiding. Two formal morphisms that differ only by equational laws in the definition of strict symmetric monoidal category will have topologically equivalent string diagrams. It suffices, then, to show that any string diagram built from generating morphisms and the braiding can be put into a standard form using topological equivalences and relations (1)–(18).

A qualitative description of this standard form will be helpful for understanding how an arbitrary string diagram can be rewritten in this form. By way of example, consider the linear transformation T: ℝ^{3} → ℝ^{2} given by

(x_{1}, x_{2}, x_{3}) ↦ (y_{1}, y_{2}) = (3x_{1} + 7x_{2} + 2x_{3}, 9x_{1} + x_{2}).

Its standard form looks like this:

\begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ 3 \\ 9 \\ 7 \\ 1 \\ 2 \\ 0 \\ y_{1} \\ y_{2} \end{matrix}

This is a string diagram picture of the following equation:

T x = ( \begin{matrix}3 & 7 & 2 \\ 9 & 1 & 0 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}y_{1} \\ y_{2} \end{matrix} )

In general, given a k-linear transformation T: k^{m} → k^{n}, we can describe it using an n × m matrix with entries in k. The case where m and/or n is zero gives a matrix with no entries, so their standard form will be treated separately. For positive values of m and n, the standard form has three distinct layers. The top layer consists of m clusters of n − 1 instances of Δ. The middle layer is mn multiplications. The n outputs of the jth cluster connect to the inputs of the multiplications {a_{1j}, …, a_{nj}}, where a_{ij} is the ij entry of A, the matrix for T. The bottom layer consists of n clusters of m − 1 instances of +. There will generally be braiding in this layer as well, but since the category is being generated as symmetric monoidal, the locations of the braidings doesn’t matter so long as the topology of the string diagram is preserved. The topology of the sum layer is that the ith sum cluster gets its m inputs from the outputs of the multiplications {a_{i1}, …, a_{im}}. The arrangement of the instances of Δ and + within their respective clusters does not matter, due to the associativity of + via relation (2) and coassociativity of Δ via relation (5). For the sake of making the standard form explicit with respect to these relations, we may assume the right output of a Δ is always connected to a multiplication input, and the right input of a + is always connected to a multiplication output. This gives a prescription for drawing the standard form of a string diagram with a corresponding matrix A.

The standard form for T: k^{0} → k^{n} is n zeros (0 ⊕ ⋯ ⊕ 0), and the standard form for T: k^{m} → k^{0} is m deletions (! ⊕ ⋯ ⊕!).

Each of the generating morphisms can easily be put into standard form: the string diagrams for zero, deletion, and multiplication are already in standard form. The string diagram for duplication (resp. addition) can be put into standard form by attaching a multiplication by 1, relation (13), to each of the outputs (resp. inputs).

1 1 =  1 1 =

The braiding morphism is just as basic to our argument as the generating morphisms, so we will need to write the string diagram for B in standard form as well. The matrix corresponding to braiding is

( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ,

so its standard form is as follows:

= 0 1 1 0

For n > 1, any morphism built from n copies of the basic morphisms—that is, generating morphisms and the braiding—can be built up from a morphism built from n − 1 copies by composing or tensoring with one more basic morphism. Thus, to prove that any string diagram built from basic morphisms can be put into its standard form, we can proceed by induction on the number of basic morphisms.

Furthermore, because strings can be extended using the identity morphism, relation (13) can be used to show tensoring with any generating morphism is equivalent to tensoring with 1, followed by a composition: Δ = Δ ∘ 1, + = 1 ∘ +, c = 1 ∘ c, ! = ! ∘ 1, 0 = 1 ∘ 0. In the case of braiding, the step of tensoring with 1 is repeated once before making the composition: B = (1 ⊕ 1) ∘ B.

\begin{matrix}⊕ \\ G \\ = \\ ⊕ \\ G \\ = \\ ⊕ \\ G \\ 1 \\ 1 \end{matrix}

Thus there are 11 cases to consider for this induction: ⊕1, +∘, ∘Δ, Δ∘, ∘+, ∘c, c∘, ∘0, !∘, B∘, ∘B. Without loss of generality, the string diagram S to which a generating morphism is added will be assumed to be in standard form already. Labels ij on diagrams illustrating these cases correspond to strings incident to the multiplications a_{ij}.

• ⊕1 When tensoring morphisms together, the matrix corresponding to C ⊕ D is the block diagonal matrix

( \begin{matrix}C & 0 \\ 0 & D \end{matrix} ) ,

where, by abuse of notation, the block C is the matrix corresponding to morphism C, and respectively D with D. Thus, when tensoring S by 1, we write the matrix for S with one extra row and one extra column. Each of these new entries will be 0 with the exception of a 1 at the bottom of the extra column. The string diagram corresponding to the new matrix can be drawn in standard form as prescribed above. Using relations (14), (4), and (1), the standard form reduces to S ⊕ 1. The process is reversible (ev(f) = ev(g) implies ev(g) = ev(f)), so if the string diagram S can be drawn in standard form, the string diagram S ⊕ 1 can be drawn in standard form, too. The diagrams below show the relevant strings before they are reduced.

0 n+1,j nj 2j 1j  ^{1  n+1,m+1 0  n,m+1 0 2,m+1 0 1,m+1}  ^{\begin{aligned}& i,m+1 \\ im \\ i2 \\ i1 \end{aligned}}

Note that for i = n + 1 the multiplications a_{i2}, …, a_{im} going to the sum cluster will be multiplication by zero, and a_{i,m+1} = 1. Otherwise a_{i,m+1} = 0, and the rest depend on the matrix corresponding to S. When S = (!⊕⋯ ⊕!), the matrix corresponding to S⊕1 has a single row, (0 ⋯ 0 1), and the standard form generated is just the middle diagram above. When the same simplifications are applied, no sum cluster exists to eliminate the zeros, so the standard form still simplifies to S ⊕ 1. Dually, when S = (0 ⊕ ⋯ ⊕ 0), the matrix representation of S ⊕ 1 is a column matrix. No duplication cluster exists in the standard form for this matrix, so the same simplifications again reduce to S ⊕ 1.

• +∘ If we compose the string diagram for addition with S, first consider only the affected clusters of additions: two clusters are combined into a larger cluster. Without loss of generality we can assume these are the first two clusters, or formally, (+⊕1^{n−2})(S). We can rearrange the sums using the associative law, relation (2), and permute the inputs of this large cluster using the commutative law, relation (3). After several iterations of these two relations, the desired result is obtained:

\begin{matrix}1m \\ 12 \\ 11 \\ 2m \\ 22 \\ 21 \\ = \\ 1m \\ 2m \\ 12 \\ 22 \\ 11 \\ 21 \end{matrix}

Now the right side of relation (12) appears in the diagram m times with a_{1j} and a_{2j} in place of b and c. Relation (12) can therefore be used to simplify to the multiplications a_{1j} + a_{2j}.

a_{1j} a_{2j} =^{a_{1j}+a_{2j}}

The simplification removes one instance of Δ from each of the m clusters of Δ and m instances of + from the large addition cluster. There will remain (m − 1) + (m − 1) + (1) − (m) = m − 1 instances of +, which is the correct number for the cluster. I.e. the composition has been reduced to standard form. The argument is vastly simpler if S = (0 ⊕ ⋯ ⊕ 0). In that case relation (1) deletes the addition and one of the 0 morphisms, and S is still in the same form.

=

• ∘Δ The argument for S ∘(Δ⊕1^{m−2}) is dual to the above argument, using the light relations (4), (5) and (6) instead of the dark relations (1), (2) and (3).

• Δ∘ For (Δ ⊕ 1^{n−1}) ∘ S, relation (7) can be used iteratively to “float” the Δ layer above each of the two + clusters formed by the first iteration.

\begin{matrix}1m \\ 11 \\ 12 \\ = \\ 11 \\ 12 \\ 1m \\ = \\ 11 \\ 12 \\ 1m \\ ⋯ \end{matrix}

Each of these instances of Δ can pass through the multiplication layer to Δ clusters using relation (17). As before, we consider the subcase S = (0 ⊕ ⋯ ⊕ 0) separately. Relation (8) removes the duplication and creates a new zero, so S remains in the same form.

• ∘+ For S(+⊕1^{m−1}), the argument is dual to the previous one: relation (7) is used to “float” the additions down, relation (15) sends the additions through the multiplications, and relation (9) removes the addition and creates a new deletion in the subcase S = (! ⊕ ⋯ ⊕!).

• ∘c We can iterate relation (17) when a multiplication is composed on top, as in S(c⊕1^{m−1}).

\begin{matrix}c \\ 11 \\ 21 \\ n1 \\ = \\ c \\ c \\ c \\ 11 \\ 21 \\ ⋯ \\ n1 \end{matrix}

The double multiplications in the multiplication layer reduce to a single multiplication via relation (11), c ∘ a_{ij} = ca_{ij}, which leaves the diagram in standard form. The composition does nothing when S = (! ⊕ ⋯ ⊕!), due to relation (18).

• c∘ A dual argument can be made for (c ⊕ 1^{n−1}) ∘ S using relations (15), (11) and (16).

• ∘0 For S(0 ⊕ 1^{m−1}), relations (8) and (16) eradicate the first Δ cluster and all the multiplications incident to it, leaving behind n zeros. Relation (1) erases each of these zeros along with one addition per addition cluster, leaving a diagram that is in standard form.

\begin{matrix}11 \\ 21 \\ n1 \\ = \\ ⋯ \\ 11 \\ 21 \\ n1 \end{matrix}  =^{a_{i1}}  \begin{matrix}i2 \\ i3 \\ im \\ = \\ i2 \\ i3 \\ im \end{matrix}

When S = (! ⊕ ⋯ ⊕!), the zero annihilates one of the deletions via relation (10).

• !∘ A dual argument erases the indicated output for the composition (! ⊕ 1^{n−1}) ∘ S using relations (9), (18), and (4). Again, relation (10) annihilates the deletion and one of the zeros if S = (0 ⊕ ⋯ ⊕ 0).

• B∘ Since this category of string diagrams is symmetric monoidal, an appended braiding will naturally commute with the addition cluster morphisms. The principle that only the topology matters means the composition (B ⊕ 1^{n−2}) ∘ S is in standard form. Braiding will similarly commute with deletion morphisms.

=

• ∘B Composing with B on the top, braiding commutes with duplication, multiplication and zero, so S ∘ (B ⊕ 1^{m−2}) almost trivially comes into standard form.

An interesting exercise is to use these relations to derive a relation that expresses the braiding in terms of other basic morphisms. One example of such a relation appeared in Section 2. Here is another:

\begin{matrix}−1 \\ −1 \\ = \end{matrix}

With a few more relations, FinVect_{k} can be presented as merely a monoidal category. Lafont [16] explained how, and gave a full proof in the special case where k is the field with two elements.

4. A presentation of FinRel_{k}

Now we give a presentation for the symmetric monoidal category FinRel_{k}. As we did in the previous section for FinVect_{k}, we work in a strict version of the symmetric monoidal category FinRel_{k}.

4.1. Lemma. For any field k, the object k together with the morphisms:

• addition +: k ⊕ k ↛ k

• zero 0: {0} ↛ k

• duplication Δ: k ↛ k ⊕ k

• deletion !: k ↛ {0}

• multiplication c: k ↛ k for any c ∈ k

• cup ∪: k ⊕ k ↛ {0}

• cap ∩: {0} ↛ k ⊕ k

generate FinRel_{k}, the category of finite-dimensional vector spaces over k and linear relations, as a symmetric monoidal category.

Proof. A morphism of FinRel_{k}, R: k^{m} ↛ k^{n} is a subspace of k^{m} ⊕ k^{n} ≅ k^{m+n}. It can be expressed as a system of k-linear equations in k^{m+n}. Lemma 3.1 tells us any number of arbitrary k-linear combinations of the inputs may be generated. Any k-linear equation of those inputs can be formed by setting such a k-linear combination equal to zero. In particular, if caps are placed on each of the outputs to make them inputs and all the k-linear combinations are set equal to zero, any k-linear system of equations of the inputs and outputs can be formed. Expressed in terms of string diagrams,

\begin{matrix}k_{m+n} \\ … \\ k_{m+1} \end{matrix}  f^{i}

The left diagram turns the n outputs into inputs by placing caps on all of them. The morphism zero gives the k-linear combination zero, so an arbitrary k-linear combination in k^{m+n} is set equal to zero (f_{i} = 0) via the cozero morphism. These elements can be combined with Lemma 3.1 to express any system of k-linear equations in k^{m+n}.

Putting these elements together, taking the FinVect_{k} portion as a black box and drawing a single string to denote zero or more copies of k, the picture is fairly simple:

To obtain a presentation of FinRel_{k} as a symmetric monoidal category, we need to find enough relations obeyed by the generating morphisms listed in Lemma 4.1. Relations (1)–(18) from Theorem 3.2 still apply, but we need more.

For convenience, in the list below we draw the adjoint of any generating morphism by rotating it by 180^{∘}. It will follow from relations (19) and (20) that the cap is the adjoint of the cup, so this convenient trick is consistent even in that case, where a priori there might have been an ambiguity.

(19)–(20) ∩ and ∪ obey the zigzag relations, and thus give a †-compact category:

=

(21)–(22) (k, +, 0, +^{†}, 0^{†}) is a Frobenius monoid:

=

(23)–(24) (k, Δ^{†},!^{†}, Δ,!) is a Frobenius monoid:

=

(25)–(26) The Frobenius monoid (k, +, 0, +^{†}, 0^{†}) is extra-special:

=  =

(27)–(28) The Frobenius monoid (k, Δ^{†},!^{†}, Δ,!) is extra-special:

=  =

(29) ∪ with a factor of −1 inserted can be expressed in terms of + and 0:

=^{−1}

(30) ∩ can be expressed in terms of Δ and !:

=

(31) For any c ∈ k with c ≠ 0, scalar multiplication by c^{−1} is the adjoint of scalar multiplication by c:

c= c^{−1}

Some curious identities can be derived from relations (1)–(31), beyond those already arising from (1)–(18). For example:

(D1)–(D2) Deletion and zero can be expressed in terms of other generating morphisms:

= (27) = (30)^{†}  ^{= (28) = (14) 0= (D1)^{†} 0}

This does not diminish the role of deletion and zero. Indeed, regarding these generating morphisms as superfluous buries some of the structure of FinRel_{k}.

(D3) Addition can be expressed in terms of coaddition and scalar multiplication by −1, and the cup:

−1 = (29) = (21) = (1)^{†}

(D4) Duplication can be expressed in terms of coduplication and the cap:

=

where the proof is similar to that of (D3).

(D5)–(D7) We can reformulate the bimonoid relations (7)–(9) using adjoints:

=

=  =

(D8)–(D9) When c ≠ 1, we have:

\begin{matrix}c \\ = \end{matrix}  \begin{matrix}c \\ = \end{matrix}

We leave the derivation of (D5)–(D9) as exercises for the reader.

Next we show that relations (1)–(31) are enough to give a presentation of FinRel_{k} as a symmetric monoidal category. As before, we do this by giving a standard form that any morphism can be written in and use induction to show that an arbitrary diagram can be rewritten in its standard form using the given relations.

4.2. Theorem. The symmetric monoidal category FinRel_{k} is presented by the object k, the morphisms given in Lemma 4.1, and relations (1)–(31) as listed above.

Proof. We prove this theorem by using the relations (1)–(31) to put any string diagram built from the generating morphisms and braiding into a standard form, so that any two string diagrams corresponding to the same morphism in FinRel_{k} have the same standard form.

As before, we induct on the number of basic morphisms involved in a string diagram, where the basic morphisms are the generating morphisms together with the braiding. If we let R: k^{m} ↛ k^{n} be a morphism in FinRel_{k}, we can build a string diagram S for R as in Lemma 4.1. Each output of S is capped, and, together with the inputs of S, form inputs for a FinVect_{k} block, T. For some r ≤ m + n, there are r outputs of T –linear combinations of the m + n inputs–each set equal to zero via (0^{†})^{r}. When T is in standard form for FinVect_{k}, we say S is in prestandard form, and can be depicted as follows:

While the linear subspace of k^{m+n} defined by R is determined by a system of r linear equations, the converse is not true, meaning there may be multiple prestandard string diagrams for a single morphism R. The second stage of this proof collapses all the prestandard forms into a standard form using some basic linear algebra. The standard form will correspond to when the matrix representation of T is written in row-reduced echelon form. For this stage it will suffice to show all the elementary row operations correspond to relations that hold between diagrams. By Theorem 3.2, an arbitrary FinVect_{k} block can be rewritten in its standard form, so the FinVect_{k} blocks here need not be demonstrated in their standard form. When there is one basic morphism, there are eight cases to consider, one per basic morphism. In each of these basic cases, the block of the diagram equivalent to a morphism in FinVect_{k} is denoted by a dashed rectangle. We first consider ∪.

(D10)

\begin{matrix}= \\ (13) \\ (11) \\ −1 \\ −1 \\ = \\ (29) \\ −1 \end{matrix}

Capping each of the inputs turns this into the standard form of ∩. Aside from deletion, the remaining generating morphisms can be formed by introducing a zigzag at each output and rewriting the resulting cups as above. The standard forms for 0 and ! have simpler expressions.

=_{−1}  =_{−c}^{c}  =_{−1}

=  =_{−1}  {= \atop (26)}

Braiding is two copies of multiplication by 1 that have been braided together.

=^{−1} −1

Assuming any string diagram with j basic morphisms can be written in prestandard form, we show an arbitrary diagram with j + 1 basic morphisms can be written in prestandard form as well. Let S be a string diagram on j basic morphisms, rewritten into prestandard form, with a maximal FinVect_{k} subdiagram T. Several cases are considered: those putting a basic morphism above S, beside S, and below S.

• S ∘ G for a basic morphism G ≠ ∩ If a diagram G is composed above S, G can combine with T to make a larger FinVect_{k} subdiagram if G is c, Δ, +, B, or 0, as these are morphisms in FinVect_{k}. The generating morphisms ∩, ∪ and ! are not on this list, though a composition with ∪ (resp. !) would be equivalent to tensoring by ∪ (resp. !).

\begin{matrix}= \\ G \end{matrix}

for \begin{matrix}G \\ = \end{matrix}  ^{c} ,  ,  ,  , or .

Putting these morphisms on top of S reduces to performing those compositions on T. The maximal FinVect_{k} subdiagram now includes T and G, with S unchanged outside the FinVect_{k} block.

• B ∘ S B commutes with caps because the category is symmetric monoidal, so capping the braiding is equivalent to putting the braiding on top of T. B is “absorbed” into T, just as in the S ∘ G case.

• S ⊕ G for any basic morphism G If any two prestandard string diagrams S and S′ are tensored together, the result combines into one prestandard diagram. This is evident because the category of string diagrams is symmetric monoidal, and the FinVect_{k} blocks can be placed next to each other as the tensor of two FinVect_{k} blocks. These combine into a single FinVect_{k} block, and absorbing all the braidings into this block as above brings the diagram into prestandard form. Since each basic morphism can be written as a prestandard diagram, the tensor S ⊕ G is a special case of this.

⨁ =

• c ∘ S for c ≠ 0 Because the outputs of S are capped, putting any morphism on the bottom of S is equivalent (via relations (19) and (20)) to putting its adjoint on top of T. Putting c ≠ 0 below S reduces to putting c^{−1} on top of T by relation (31). The case of c = 0 will be considered below. The other cases of adjoints of generating morphisms that need to be considered more carefully are the ones that put Δ^{†}, +^{†} and ∩ = ∪^{†} on top of T.

c= c^{−1}

• Δ ∘ S When putting Δ^{†} on top of T, the idea is to make it “trickle down.” If there is a nonzero multiplication incident to the Δ cluster, Δ^{†} can slide through the Δs using relation (23) to the first nonzero multiplication, switching to relation (24). When it encounters this c, relation (31) turns c into (c^{−1})^{†}, relation (17)^{†} allows Δ^{†} to pass through (c^{−1})^{†}. Both copies of (c^{−1})^{†} can return to being c by another application of relation (31), and the Δ^{†} moves on to the next layer.

0 = (23) 0  \begin{matrix}c \\ = \\ (24) \\ c \end{matrix}  ^{c= (31)^{†} c^{−1} = (17)^{†} c^{−1} c^{−1} = (31)^{†} cc}

When the codelta gets to a + cluster, derived relation (D5) has a net effect of bringing it to the bottom of the subdiagram, as the other morphisms involved all belong to FinVect_{k}. This allows the process to be repeated on the next addition until Δ^{†} reaches the bottom of the + cluster. Once there, codelta interacts with the cozero layer below T; relation (8)^{†} reduces it to a pair of cozeros.

{= \atop (D5)}  ^{= (8)^{†}}

If all the multiplications incident to the Δ cluster are by 0, rather than trickling down, Δ^{†} composes with ! (due to relation (14)), which gives ∪ by relation (30)^{†}. By the zigzag identities, this cup becomes a cap that is tensored with a subdiagram of S that is in prestandard form.

000= (14) (4) ⋯ = (30)^{†} ⋯

• + ∘ S There is a similar trickle down argument for +^{†}. First rewriting all multiplications by zero via relation (14), the two Δ clusters incident to the coaddition can either reduce to Δ clusters that are incident only to nonzero multiplications or reduce to a single deletion, as above, if none of the incident multiplications were nonzero. There are three cases of what can happen from here.

– Both Δ clusters were incident to only zero-multiplications In the first case, as above, the Δ clusters will reduce to ! incident to the outputs of +^{†}. Relations (D7) and (28) delete the coaddition.

– One Δ cluster was incident to only zero-multiplications Without loss of generality, the ! incident to +^{†} is on the left. Relation (D7) replaces ! and +^{†} with !^{†}∘!, and relation (30) replaces Δ and !^{†} with a cap. The Δ was – and the cap is – incident to some multiplication by c ≠ 0. Without loss of generality, c is incident to the bottom addition in the cluster. Relation (29) replaces the addition and cozero with a cup and multiplication by −1, which combines with c by relation (11). The cup and cap turn −c around to its adjoint, which is −c^{−1} by relation (31).

c= (D7)^{†} (30) c  ^{c= (29) (11) −c = (31) −c^{−1}}

An addition cluster is above −c^{−1} and a duplication cluster is below, but because those clusters are not otherwise connected to each other, there is a vertical arrangement of the morphisms in the FinVect_{k} block of the string diagram such that no cups or caps are present.

– Both Δ clusters are incident to at least one nonzero multiplication Using relation (D5)^{†}, a +^{†} will pass through one Δ at a time. A new Δ^{†} is created each time, but this can trickle down as before.

=

Once the Δ^{†} trickles down, there are two possibilities for what is directly beneath each +^{†}: either the same scenario will recur with a Δ connected to one or both outputs, which can only happen finitely many times, or two nonzero multiplications will be below the +^{†}. A multiplication by any unit in k, c ≠ 0, can move through a coaddition by inserting cc^{−1} on the top branch and applying relation (15)^{†}:

c= cc^{−1}

This allows one of the outputs of the coaddition to connect directly to a + cluster.

∗ If both branches go to different + clusters, Frobenius relations (21)–(22) slide the +^{†} down the + cluster on one side until it gets to the end of that cluster.

\begin{matrix}c \\ = \\ (21) \\ (22) \\ c \end{matrix}

The only morphisms added to the FinVect_{k} block that are not from FinVect_{k} were the coaddition and the cozero. Since these reduce to an identity morphism string by relation (1)^{†}, the FinVect_{k} block is truly a FinVect_{k} block again.

∗ If both branches go to the same + cluster, relation (3) and the Frobenius relation (21) take both branches to the same addition.

\begin{matrix}c \\ = \\ (3) \\ (21) \\ c \end{matrix}

Depending on whether the remaining multiplication is by 1, either relation (25) reduces the coaddition and the given addition to an identity string or relation (D8) applies. In the former case we are done, and in the latter case relations (D7) and (10)^{†} remove the !^{†} introduced by applying relation (D8).

{= \atop (D7)}  ^{= (D7) = (10)^{†}}

• ∪ ∘ S and S ∘ ∩ Composing with a cup below S is equivalent to composing with cap above T, since ∩ = ∪^{†}. Using relation (D10)^{†}, this cap can be replaced by multiplication by −1, coaddition, and zero. By the arguments above, −1, +^{†}, and 0 can each be absorbed into the FinVect_{k} block.

= (D10)^{†} −1 =

The compositions with zero and multiplication by −1 expand the FinVect_{k} block, thus have no effect on whether the diagram can be written in prestandard form.

• ! ∘ S When composing !^{†} above T, two possibilities arise, depending on whether there is a layer of Δs in the FinVect_{k} block. If there is such a layer, relation (30) combines the !^{†} with a Δ, making a cap on top of T. As we have just seen, this can be rewritten in prestandard form.

= = (30)

If no layer of Δs exists, relations (31)^{†} and (18)^{†} pass the codeletion through a nonzero multiplication. Then relations (D7) and (10)^{†} can be used to remove !^{†}, as we have already seen. This leaves only the basic morphisms of FinVect_{k} within the FinVect_{k} block.

c= (31)^{†} c^{−1} = (18)^{†}

If the multiplication is c = 0, relation (14) converts c = 0 to 0∘!, allowing relation (28) to remove the !^{†}, with the same conclusion.

0 = (14) = (28)

• c ∘ S for c = 0 Composing with multiplication by c = 0 below S is equivalent to composing with codeletion, followed by tensoring with zero. Codeletion is the ! ∘ S case, and zero can be written in a prestandard form, so this reduces to tensoring two diagrams that are in prestandard form.

0 = (14)

Finally, we need to show the prestandard forms can be rewritten in standard form. We need to show what elementary row operations look like in terms of string diagrams. We also need to show for an arbitrary prestandard string diagram S with FinVect_{k} block T that if T is replaced with T′, the diagram where an elementary row operation has been performed on T, the resulting diagram S′ can be built from S using relations (1)–(31).

Because the ith output of a FinVect_{k} diagram is a linear combinations of the inputs, with the coefficients coming from the ith row of its matrix, rows of the matrix correspond to outputs of the FinVect_{k} block. Because of this, the row operation subdiagrams in S′ will have 0^{†}s immediately beneath them. Showing S′ can be built from S reduces to showing composition of row operations with 0^{†}s builds the same number of 0^{†}s.

• Add a multiple c of one row to another row: If we want to add a multiple of the β row to the α row, we need a map (y_{α}, y_{β}) ↦ (y_{α} + cy_{β}, y_{β}). By the naturality of the braiding in a symmetric monoidal category, we can ignore any intermediate outputs:

\begin{matrix}c \\ y_{α} \\ y_{β} \\ y_{α} + cy_{β} \\ y_{β} \end{matrix}

When two cozeros are composed on the bottom of this diagram, the result is two cozeros:

\begin{matrix}c \\ = \\ (D10) \\ c \\ −1 \\ = \\ (11) \\ −c \\ = \\ (D6) \\ −c \\ = \\ (16) \end{matrix}

• Swap rows:

If we want to swap the β row with the α row, we need a map (y_{α}, y_{β}) ↦ (y_{β}, y_{α}), which is the braiding of two outputs. Again, intermediate outputs may be ignored:

\begin{matrix}y_{α} \\ y_{α} \\ y_{β} \\ y_{β} \end{matrix}

When two cozeros are composed at the bottom of this diagram, the cut strings untwist by the naturality of the braiding:

=

• Multiply a row by c ≠ 0: The third row operation is multiplying an arbitrary row by a unit, but since k is a field, that means any c ≠ 0. This is just the multiplication map on one of the outputs:

\begin{matrix}c \\ y_{α} \\ cy_{α} \end{matrix}

Because c is a unit, c^{−1} ∈ k, so the multiplication by c can be replaced by the adjoint of multiplication by c^{−1}.

c= (31)^{†} c^{−1} = (16)^{†}

5. An example

A famous example in control theory is the ‘inverted pendulum’: an upside-down pendulum on a cart [10]. The pendulum naturally tends to fall over, but we can stabilize it by setting up a feedback loop where we observe its position and move the cart back and forth in a suitable way based on this observation. Without introducing this feedback loop, let us see how signal-flow diagrams can be used to describe the pendulum and the cart. We shall see that the diagram for a system made of parts is built from the diagrams for the parts, not merely by composing and tensoring, but also with the help of duplication and coduplication, which give additional ways to set variables equal to one another.

Suppose the cart has mass M and can only move back and forth in one direction, so its position is described by a function x(t). If it is acted on by a total force F_{net}(t) then Newton’s second law says

F_{net}(t) = Mẍ(t).

We can thus write a signal-flow diagram with the force as input and the cart’s position as output:

x ∫ẋ ∫ẍ\frac{1}{M} F_{net}

The inverted pendulum is a rod of length l with a mass m at its end, mounted on the cart and only able to swing back and forth in one direction, parallel to the cart’s movement. If its angle from vertical, θ(t), is small, then its equation of motion is approximately linear:

lθ̈(t) = gθ(t) − ẍ(t)

where g is the gravitational constant. We can turn this equation into a signal-flow diagram with ẍ as input and θ as output:

−\frac{1}{l} ∫\frac{g}{l}∫ẍ θ

Note that this already includes a kind of feedback loop, since the pendulum’s angle affects the force on the pendulum.

Finally, there is an equation describing the total force on the cart:

F_{net}(t) = F (t) − mgθ(t)

where F (t) is an externally applied force and −mgθ(t) is the force due to the pendulum. It will be useful to express this as follows:

\begin{matrix}−mg \\ F_{net} \\ θ \\ F \end{matrix}

Here we are treating θ as an output rather than an input, with the help of a cap. The three signal-flow diagrams above describe the following linear relations:

x = ∫ ∫ \frac{1}{M} F_{net}  (1)
θ = ∫ ∫ (\frac{g}{l} θ − \frac{1}{l} ẍ)  (2)
F_{net} + mgθ = F  (3)

where we treat (1) as a relation with F_{net} as input and x as output, (2) as a relation with ẍ as input and θ as output, and (3) as a relation with F as input and (F_{net}, θ) as output.

To understand how the external force affects the position of the cart and the angle of the pendulum, we wish to combine all three diagrams to form a signal-flow diagram that has the external force F as input and the pair (x, θ) as output. This is not just a simple matter of composing and tensoring the three diagrams. We can take F_{net}, which is an output of (3), and use it as an input for (1). But we also need to duplicate ẍ, which appears as an intermediate variable in (1) since ẍ = \frac{1}{M} F_{net}, and use it as an input for (2). Finally, we need to take the variable θ, which appears as an output of both (2) and (3), and identify the two copies of this variable using coduplication. Following traditional engineering practice, we shall write coduplication in terms of duplication and a cup, as follows:

=

The result is this signal-flow diagram:

−mg \frac{1}{M} F ∫∫x −\frac{1}{l} ∫\frac{g}{l}∫θ

This is not the signal-flow diagram for the inverted pendulum that one sees in Friedland’s textbook on control theory [10]. We leave it as an exercise to the reader to rewrite the above diagram using the rules given in this paper, obtaining Friedland’s diagram:

F \frac{1}{M} \frac{−1}{Ml} ∫∫x ∫∫\frac{mg}{M} \frac{(M+m)g}{Ml} θ

As a start, one can use Theorem 4.2 to prove that it is indeed possible to do this rewriting. To do this, simply check that both signal-flow diagrams define the same linear relation. The proof of the theorem gives a method to actually do the rewriting—but not necessarily the fastest method.

6. Conclusions

We conclude with some remarks aimed at setting our work in context. In particular, we would like to compare it to some other recent papers. On April 30th, 2014, after most of this paper was written, Sobociński told the first author about some closely related papers that he wrote with Bonchi and Zanasi [4, 5]. These provide interesting characterizations of symmetric monoidal categories equivalent to FinVect_{k} and FinRel_{k}. Later, while this paper was being refereed, Wadsley and Woods [22] generalized the first of these results to the case where k is any commutative rig. We discuss Wadsley and Woods’ work first, since doing so makes the exposition simpler.

A particularly tractable sort of symmetric monoidal category is a PROP: that is, a strict symmetric monoidal category where the objects are natural numbers and the tensor product of objects is given by ordinary addition. The symmetric monoidal category FinVect_{k} is equivalent to the PROP Mat(k), where a morphism f: m → n is an n × m matrix with entries in k, composition of morphisms is given by matrix multiplication, and the tensor product of morphisms is the direct sum of matrices.

Wadsley and Woods gave an elegant description of the algebras of Mat(k). Suppose C is a PROP and D is a strict symmetric monoidal category. Then the category of algebras of C in D is the category of strict symmetric monoidal functors F: C → D and natural transformations between these. If for every choice of D the category of algebras of C in D is equivalent to the category of algebraic structures of some kind in D, we say C is the PROP for structures of that kind.

In this language, Wadsley and Woods proved that Mat(k) is the PROP for ‘bicommutative bimonoids over k’. To understand this, first note that for any bicommutative bimonoid A in D, the bimonoid endomorphisms of A can be added and composed, giving a rig End(A). A bicommutative bimonoid over k in D is one equipped with a rig homomorphism Φ_{A}: k → End(A). Bicommutative bimonoids over k form a category where a morphism f: A → B is a bimonoid homomorphism compatible with this extra structure, meaning that for each c ∈ k the square

\xymatrix{A \ar[d]_{f} \ar[r]^{Φ_{A}(c)} & A \ar[d]^{f} \\ B \ar[r]_{Φ_{B}(c)} & B}

commutes. Wadsley and Woods proved that this category is equivalent to the category of algebras of Mat(k) in D.

This result amounts to a succinct restatement of Theorem 3.2, though technically the result is a bit different, and the style of proof much more so. The fact that an algebra of Mat(k) is a bicommutative bimonoid is equivalent to our relations (1)–(10). The fact that Φ_{A}(c) is a bimonoid homomorphism for all c ∈ k is equivalent to relations (15)–(18), and the fact that Φ is a rig homomorphism is equivalent to relations (11)–(14).

Even better, Wadsley and Woods showed that Mat(k) is the PROP for bicommutative bimonoids over k whenever k is a commutative rig. Subtraction and division are not required to define the PROP Mat(k), nor are they relevant to the definition of bicommutative bimonoids over k. Working with commutative rigs is not just generalization for the sake of generalization: it clarifies some interesting facts.

For example, the commutative rig of natural numbers gives a PROP Mat(ℕ). This is equivalent to the symmetric monoidal category where morphisms are isomorphism classes of spans of finite sets, with disjoint union as the tensor product. Lack [15, Ex. 5.4] had already shown that this is the PROP for bicommutative bimonoids. But this also follows from the result of Wadsley and Woods, since every bicommutative bimonoid A is automatically equipped with a unique rig homomorphism Φ_{A}: ℕ → End(A).

Similarly, the commutative rig of booleans 𝔹 = {F, T }, with ‘or’ as addition and ‘and’ as multiplication, gives a PROP Mat(𝔹). This is equivalent to the symmetric monoidal category where morphisms are relations between finite sets, with disjoint union as the tensor product. Mimram [18, Thm. 16] had already shown this is the PROP for special bicommutative bimonoids, meaning those where comultiplication followed by multiplication is the identity:

=

But again, this follows from the general result of Wadsley and Woods.

Finally, taking the commutative ring of integers ℤ, Wadsley and Woods showed that Mat(ℤ) is the PROP for bicommutative Hopf monoids. The key here is that scalar multiplication by −1 obeys the axioms for an antipode, namely:

\begin{matrix}−1 \\ = \\ = \\ −1 \end{matrix}

More generally, whenever k is a commutative ring, the presence of −1 ∈ k guarantees that a bimonoid over k is automatically a Hopf monoid over k. So, when k is a commutative ring, Wadsley and Woods’ result implies that Mat(k) is the PROP for Hopf monoids over k.

Earlier, Bonchi, Sobociński and Zanasi gave an elegant and very different proof that Mat(R) is the PROP for Hopf monoids over R when R is a principal ideal domain [4, Prop. 3.7]. The advantage of their argument is that they build up the PROP for Hopf monoids over R from smaller pieces, using some ideas developed by [15].

These authors also described a PROP that is equivalent to FinRel_{k} as a symmetric monoidal category whenever k is a field. In this PROP, which they call 𝕊𝕍_{k}, a morphism f: m → n is a linear relation from k^{m} to k^{n}. They proved that 𝕊𝕍_{k} is a pushout in the category of PROPs and strict symmetric monoidal functors:

\xymatrix{Mat(R) + Mat(R)^{op} \ar[d] \ar[r] & Span(Mat(R)) \ar[d] \\ Cospan(Mat(R)) \ar[r] & _{𝕊𝕍_{k}}}

This pushout square requires a bit of explanation. Here R is any principal ideal domain whose field of fractions is k. For example, we could take R = k, though Bonchi, Sobociński and Zanasi are more interested in the example where R = ℝ[s] and k = ℝ(s). A morphism in Span(Mat(R)) is an isomorphism class of spans in Mat(R). There is a covariant functor

Mat(R) → Span(Mat(R))
m →^{f} n ↦ m ←^{1} m →^{f} n

and also a contravariant functor

Mat(R) → Span(Mat(R))
m →^{f} n ↦ n ←^{f} m →^{1} m.

Putting these together we get the functor from Mat(R) + Mat(R)^{op} to Span(Mat(R)) that gives the top edge of the square. Similarly, a morphism in Cospan(Mat(R)) is an isomorphism class of cospans in Mat(R), and we have both a covariant functor

Mat(R) → Cospan(Mat(R))
m →^{f} n ↦ m →^{f} n ←^{1} n

and a contravariant functor

Mat(R) → Cospan(Mat(R))
m →^{f} n ↦ n →^{1} n ←^{f} m.

Putting these together we get the functor from Mat(R) + Mat(R)^{op} to Cospan(Mat(R)) that gives the left edge of the square.

Bonchi, Sobociński and Zanasi analyze this pushout square in detail, giving explicit presentations for each of the PROPs involved, all based on their presentation of Mat(R). The upshot is a presentation of 𝕊𝕍_{k} which is very similar to our presentation of the equivalent symmetric monoidal category FinRel_{k}. Their methods allow them to avoid many, though not all, of the lengthy arguments that involve putting morphisms in ‘normal form’.

Acknowledgements. We thank Jamie Vicary for pointing out the relevance of the ZX calculus when the first author gave a talk on this material at Oxford in February 2014 [2]. Discussions with Brendan Fong have also been very useful.

References

[1] Samson Abramsky and Bob Coecke, A categorical semantics of quantum protocols, Proceedings of the 19th IEEE Conference on Logic in Computer Science (LiCS’04), IEEE Computer Science Press, 2004, pp. 415–425. Also available as arXiv:quant-ph/0402130.

[2] John Baez, Network theory I: electrical circuits and signal-flow graphs, lecture at the Department of Computer Science, University of Oxford, February 25, 2014. Slides and video available at http://math.ucr.edu/home/baez/networks oxford/.

880  JOHN C. BAEZ AND JASON ERBELE

[3] John Baez and Mike Stay, Physics, topology, logic and computation: a Rosetta Stone, in New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95–172. Also available as arXiv:0903.0340.

[4] Filippo Bonchi, Paweł Sobociński and Fabio Zanasi, Interacting Hopf algebras. Available as arXiv:1403.7048.

[5] Filippo Bonchi, Paweł Sobociński and Fabio Zanasi, A categorical semantics of signal flow graphs, in CONCUR 2014–Concurrency Theory, eds. P. Baldan and D. Gorla, Lecture Notes in Computer Science vol. 8704, Springer, Berlin, 2014, pp. 435–450. Also available at http://users.ecs.soton.ac.uk/ps/papers/sfg.pdf.

[6] Aurelio Carboni and Robert F. C. Walters, Cartesian bicategories I, J. Pure Appl. Alg. 49 (1987), 11–32.

[7] Bob Coecke and Ross Duncan, Interacting quantum observables: categorical algebra and diagrammatics, New J. Phys. 13 (2011), 043016. Also available as arXiv:0906.4725.

[8] Bob Coecke and Eric Oliver Paquette, Categories for the practising physicist, in New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 173–286. Also available as arXiv:0905.3010.

[9] Bob Coecke, Dusko Pavlovic and Jamie Vicary, A new description of orthogonal bases, Math. Str. Comp. Sci. 23 (2013), 555–567. Also available as arXiv:0810.0812.

[10] Bernard Friedland, Control System Design: An Introduction to State-Space Methods, Courier Dover Publications, 2012.

[11] André Joyal and Ross Street, The geometry of tensor calculus I, Adv. Math. 88 (1991), 55-113.

[12] André Joyal and Ross Street, The geometry of tensor calculus II. Draft available at http://maths.mq.edu.au/∼street/GTCII.pdf.

[13] Joachim Kock, Frobenius Algebras and 2D Topological Quantum Field Theories, Cambridge U. Press, Cambridge, 2003. Short version available at http://mat.uab.es/∼kock/TQFT/FS.pdf.

[14] Joachim Kock, Remarks on the origin of the Frobenius equation, available at http://mat.uab.es/∼kock/TQFT.html#history.

[15] Stephen Lack, Composing PROPs, Th. Appl. Cat. 13 (2004), 147–163. Available at http://www.tac.mta.ca/tac/volumes/13/9/13-09abs.html.

[16] Yves Lafont, Towards an algebraic theory of Boolean circuits, J. Pure Appl. Alg. 184 (2003), 257–310. Also available at http://iml.univ-mrs.fr/∼lafont/pub/circuits.pdf.

[17] Saunders Mac Lane, Natural associativity and commutativity, Rice U. Studies 49 (1963), 28—46.

[18] Samuel Mimram, Presentation of a game semantics for first-order propositional logic. Available as arXiv:0805.0845.

[19] Robert Rosebrugh, Nicoletta Sabadini and Robert F. C. Walters, Generic commutative separable algebras and cospans of graphs, Th. Appl. Cat. 15 (2005), 264–277. Available at http://www.tac.mta.ca/tac/volumes/15/6/15-06abs.html.

[20] Peter Selinger, Dagger compact closed categories and completely positive maps, Elec. Notes Theor. Comp. Sci. 170 (2007), 139–163.

[21] Jamie Vicary, Categorical formulations of finite-dimensional quantum algebras, Comm. Math. Phys. 304 (2011), 765–796. Also available as arXiv:0805.0432.

[22] Simon Wadsley and Nick Woods, PROPs for linear systems. Available as arXiv:1505.00048.

Department of Mathematics University of California Riverside CA 92521, USA and Centre for Quantum Technologies National University of Singapore Singapore 117543

Department of Mathematics University of California Riverside CA 92521, USA

Email: baez@math.ucr.edu
      erbele@math.ucr.edu
This article may be accessed at http://www.tac.mta.ca/tac/

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis: cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne: kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Edinburgh: Tom.Leinster@ed.ac.uk Ieke Moerdijk, Radboud University Nijmegen: i.moerdijk@math.ru.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Edinburgh: Alex.Simpson@ed.ac.uk James Stasheff, University of North Carolina: jds@math.upenn.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca