Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

April 28, 2015

Categories in Control

Posted by John Baez

To understand ecosystems, ultimately will be to understand networks. - B. C. Patten and M. Witkamp

A while back I decided one way to apply my math skills to help save the planet was to start pushing toward green mathematics: a kind of mathematics that can interact with biology and ecology just as fruitfully as traditional mathematics interacts with physics. As usual with math, the payoffs will come slowly, but they may be large. It’s not a substitute for doing other, more urgent things—but if mathematicians don’t do this, who will?

As a first step in this direction, I decided to study networks.

This May, a small group of mathematicians is meeting in Turin for a workshop on the categorical foundations of network theory, organized by Jacob Biamonte. I’m trying to get us mentally prepared for this. We all have different ideas, yet they should fit together somehow.

Tobias Fritz, Eugene Lerman and David Spivak have all written articles here about their work, though I suspect Eugene will have a lot of completely new things to say, too. Now I want to say a bit about what I’ve been doing with Jason Erbele.

Despite my ultimate aim of studying biological and ecological networks, I decided to start by clarifying the math of networks that appear in chemistry and engineering, since these are simpler, better understood, useful in their own right, and probably a good warmup for the grander goal. I’ve been working with Brendan Fong on electrical ciruits, and with Jason Erbele on control theory. Let me talk about this paper:

• John Baez and Jason Erbele, Categories in control.

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, for example smooth real-valued functions of time. Here’s a real-world example; click the picture for more details:

For a category theorist, at least, it is natural to treat signal-flow diagrams as string diagrams in a symmetric monoidal category. This forces some small changes of perspective, which I’ll explain, but more important is the question: which symmetric monoidal category?

We argue that the answer is: the category FinRel k\mathrm{FinRel}_k of finite-dimensional vector spaces over a certain field k,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)k = \mathbb{R}(s) consisting of rational functions in one real variable s.s. This variable has the meaning of differentation. A linear relation from k mk^m to k nk^n is thus a system of linear constant-coefficient ordinary differential equations relating mm ‘input’ signals and nn ‘output’ signals.

Our main goal in this paper 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.

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:

fcf f \mapsto cf

where c.c \in \mathbb{R}. We can write this as a string diagram:

Here the labels ff and cfc f 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 ff and which the output cf.c f.

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

ff f \mapsto \int 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:

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

(f)(s)= 0 f(t)e stdt\displaystyle{ (\mathcal{L}f)(s) = \int_0^\infty f(t) e^{-st} \,dt }

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

(f)(ω)= f(t)e iωtdt\displaystyle{ (\mathcal{F}f)(\omega) = \int_{-\infty}^\infty f(t) e^{-i\omega t}\, dt }

by iω.-i\omega. Of course, the function ff 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,t &lt; 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).\mathbb{R}(s). The field (s)\mathbb{C}(s) would work just as well, and control theory relies heavily on complex analysis. In our paper we work over an arbitrary field k.k.

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

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 + : (f,g) \mapsto f + g

and duplication:

Δ:f(f,f) \Delta : f \mapsto (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:

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 Δ,\Delta, 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 the zero-dimensional vector space {0}\{0\} to our field k,k, which we denote as 00 and draw as follows:

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

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×01 \times 0 and 0×10 \times 1 matrices, respectively. Addition and zero make kk 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) B : (f,g) \mapsto (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:

Dually, duplication and deletion make kk 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:

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 kk are comonoid homomorphisms—or equivalently, the comonoid operations are monoid homomorphisms.

We summarize this situation by saying that kk is a bimonoid. These are all the bimonoid laws, drawn as diagrams:

The last equation means we can actually make the diagram at left disappear, since it equals the identity morphism on the 0-dimensional vector space, which is drawn as nothing.

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

In applications of string diagrams to quantum theory, we make FinVect k\mathrm{FinVect}_k into a symmetric monoidal category using the tensor product of vector spaces. In control theory, we instead make FinVect k\mathrm{FinVect}_k into a symmetric monoidal category using the direct sum of vector spaces. In Lemma 1 of our paper we prove that for any field k,k, FinVect k\mathrm{FinVect}_k with direct sum is generated as a symmetric monoidal category by the one object kk together with these morphisms:

where ckc \in k is arbitrary.

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

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

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

(2) the rig operations of kk can be recovered from the generating morphisms;

(3) all the generating morphisms commute with scalar multiplication.

Here item (2) means that +,,0+, \cdot, 0 and 11 in the field kk can be expressed in terms of signal-flow diagrams as follows:

Multiplicative inverses cannot be so expressed, so our signal-flow diagrams so far do not know that kk is a field. Additive inverses also cannot be expressed in this way. So, we expect that a version of Theorem 2 will hold whenever kk is a mere rig: that is, a ‘ring without negatives’, like the natural numbers. The one change is that instead of working with vector spaces, we should work with finitely presented free kk-modules.

Item (3), the fact that all our generating morphisms commute with scalar multiplication, amounts to these diagrammatic equations:

While Theorem 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:

The user inputs a ‘reference’ signal, which is fed into a controller, whose output is fed into a system, which control theorists call a ‘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’:

and ‘cap’:

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.\mathrm{FinRel}_k. An object of this category is a finite-dimensional vector space over k,k, while a morphism from UU to V,V, denoted L:UV,L : U \rightharpoonup V, is a linear relation, meaning a linear subspace

LUV L \subseteq U \oplus V

In particular, when k=(s),k = \mathbb{R}(s), a linear relation L:k mk nL : k^m \to k^n is just an arbitrary system of constant-coefficient linear ordinary differential equations relating mm input variables and nn output variables.

Since the direct sum UVU \oplus V is also the cartesian product of UU and V,V, a linear relation is indeed a relation in the usual sense, but with the property that if uUu \in U is related to vVv \in V and uUu' \in U is related to vVv' \in V then cu+cuc u + c'u' is related to cv+cvc v + c'v' whenever c,ck.c,c' \in k.

We compose linear relations L:UVL : U \rightharpoonup V and L:VWL' : V \rightharpoonup W as follows:

LL={(u,w):vV(u,v)Land(v,w)L} L'L = \{(u,w) \colon \; \exists\; v \in V \;\; (u,v) \in L \; and \; (v,w) \in L'\}

Any linear map f:UVf : U \to V gives a linear relation F:UV,F : U \rightharpoonup V, namely the graph of that map:

F={(u,f(u)):uU} F = \{ (u,f(u)) : u \in U \}

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

In these terms, the cup is the linear relation

:k 2{0} \cup : k^2 \rightharpoonup \{0\}

given by

={(x,x,0):xk}k 2{0} \cup \; = \; \{ (x,x,0) : x \in k \} \; \subseteq \; k^2 \oplus \{0\}

while the cap is the linear relation

:{0}k 2 \cap : \{0\} \rightharpoonup k^2

given by

={(0,x,x):xk}{0}k 2 \cap \; = \; \{ (0,x,x) : x \in k \} \; \subseteq \; \{0\} \oplus k^2

These obey the zigzag relations:

Thus, they make FinRel k\mathrm{FinRel}_k into a compact closed category where k,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:UVL : U \rightharpoonup 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:UVL : U \rightharpoonup V and obtain a linear relation L :VU,L^\dagger : V \rightharpoonup U, called the adjoint of L,L, which turns out to given by

L ={(v,u):(u,v)L} L^\dagger = \{(v,u) : (u,v) \in L \}

For example, if ckc \in k is nonzero, the adjoint of scalar multiplication by cc is multiplication by c 1c^{-1}:

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

{(0,x):xk}kk \{(0,x) : x \in k \} \subseteq k \oplus k

In Lemma 3 we show that FinRel k\mathrm{FinRel}_k is generated, as a symmetric monoidal category, by these morphisms:

where ckc \in k is arbitrary.

In Theorem 4 we find a complete set of relations obeyed by these generating morphisms,thus giving a presentation of FinRel k\mathrm{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 cc is scalar multiplication by c 1,c^{-1}, except when c=0.c = 0. Taking adjoints of the other four generating morphisms of FinVect k,\mathrm{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 kk to k 2k^2 that holds when the two outputs sum to the input:

+ :kk 2 +^\dagger : k \rightharpoonup k^2

+ ={(x,y,z):x=y+z}kk 2+^\dagger = \{(x,y,z) : \; x = y + z \} \subseteq k \oplus k^2

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

0 :k{0} 0^\dagger : k \rightharpoonup \{0\}

0 ={(0,0)}k{0} 0^\dagger = \{ (0,0)\} \subseteq k \oplus \{0\}

Coduplication is a linear relation from k 2k^2 to kk that holds when the two inputs both equal the output:

Δ :k 2k \Delta^\dagger : k^2 \rightharpoonup k

Δ ={(x,y,z):x=y=z}k 2k \Delta^\dagger = \{(x,y,z) : \; x = y = z \} \subseteq k^2 \oplus k

Codeletion is a linear relation from {0}\{0\} to kk that holds always:

! :{0}k !^\dagger : \{0\} \rightharpoonup k

! ={(0,x)}{0}k !^\dagger = \{(0,x) \} \subseteq \{0\} \oplus k

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

Moreover, the four dark operations make kk into a Frobenius monoid. This means that (k,+,0)(k,+,0) is a monoid, (k,+ ,0 )(k,+^\dagger, 0^\dagger) 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 kFinRel k \dagger : \mathrm{FinRel}_k \to \mathrm{FinRel}_k

which obeys a list of properties that are summarized by saying that FinRel k\mathrm{FinRel}_k is a †-compact category. Because two of the operations in the Frobenius monoid (k,+,0,+ ,0 )(k, +,0,+^\dagger,0^\dagger) are adjoints of the other two, it is a †-Frobenius monoid.

This Frobenius monoid is also special, meaning that comultiplication (in this case + +^\dagger) 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. The category FinHilb\mathrm{FinHilb} of finite-dimensional Hilbert spaces and linear maps is a †-compact category, where any linear map f:HKf : H \to K has an adjoint f :KHf^\dagger : K \to H given by

f ϕ,ψ=ϕ,fψ \langle f^\dagger \phi, \psi \rangle = \langle \phi, f \psi \rangle

for all ψH,ϕK.\psi \in H, \phi \in K . A commutative special †-Frobenius monoid in FinHilb\mathrm{FinHilb} is then the same as a Hilbert space with a chosen orthonormal basis. The reason is that given an orthonormal basis ψ i \psi_i for a finite-dimensional Hilbert space H,H, we can make HH into a commutative special †-Frobenius monoid with multiplication m:HHHm : H \otimes H \to H given by

m(ψ iψ j)={ψ i i=j 0 ij m (\psi_i \otimes \psi_j ) = \left\{ \begin{array}{cl} \psi_i & i = j \\ 0 & i \ne j \end{array}\right.

and unit i:Hi : \mathbb{C} \to H given by

i(1)= iψ i i(1) = \sum_i \psi_i

The comultiplication m m^\dagger duplicates basis states:

m (ψ i)=ψ iψ i m^\dagger(\psi_i) = \psi_i \otimes \psi_i

Conversely, any commutative special †-Frobenius monoid in FinHilb\mathrm{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,2\mathrm{Cob}, the category with 2-dimensional oriented cobordisms as morphisms. But the free symmetric monoidal category on a commutative special Frobenius monoid was worked out even earlier: it is the category with finite sets as objects, where a morphism f:XYf : X \to Y is an isomorphism class of cospans

XSY X \longrightarrow S \longleftarrow 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}k0 : \{0\} \rightharpoonup k followed by the counit 0 :k{0}0^\dagger : k \rightharpoonup \{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:XYf : X \to Y is an equivalence relation on the disjoint union XY,X \sqcup Y, and we compose f:XYf : X \to Y and g:YZg : Y \to Z by letting ff and gg generate an equivalence relation on XYZX \sqcup Y \sqcup Z and then restricting this to XZ.X \sqcup Z.

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

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

(k,Δ ,! ,+ ,0 )(k, \Delta^\dagger, !^\dagger, +^\dagger, 0^\dagger) is a bicommutative bimonoid;

(k,+,0,+ ,0 )(k, +, 0, +^\dagger, 0^\dagger) is a commutative extra-special †-Frobenius monoid;

(k,Δ ,! ,Δ,!)(k, \Delta^\dagger, !^\dagger, \Delta, !) 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. This arises naturally when one has an nn-dimensional Hilbert space HH with two orthonormal bases ψ i,ϕ i\psi_i, \phi_i that are mutually unbiased, meaning that

|ψ i,ϕ j| 2=1n |\langle \psi_i, \phi_j \rangle|^2 = \displaystyle{\frac{1}{n}}

for all 1i,jn.1 \le i, j \le n. Each orthonormal basis makes HH into commutative special †-Frobenius monoid in FinHilb.\mathrm{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 HH is 1-dimensional.

The field kk is also a 1-dimensional vector space, but this is a red herring: in FinRel k\mathrm{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. Jason and I focus on kk in our paper simply because it generates all the objects FinRel k\mathrm{FinRel}_k via direct sum.

Finally, in FinRel k\mathrm{FinRel}_k the cap and cup are related to the light and dark operations as follows:

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

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

Theorem 4 of our paper gives a presentation of FinRel k\mathrm{FinRel}_k based on the ideas just discussed. Briefly, it says that FinRel k\mathrm{FinRel}_k is equivalent to the symmetric monoidal category generated by an object kk and these morphisms:

• addition +:k 2k+: k^2 \rightharpoonup k • zero 0:{0}k0 : \{0\} \rightharpoonup k • duplication Δ:kk 2\Delta: k\rightharpoonup k^2 • deletion !:k0! : k \rightharpoonup 0 • scalar multiplication c:kkc: k\rightharpoonup k for any ckc\in k • cup :k 2{0}\cup : k^2 \rightharpoonup \{0\} • cap :{0}k 2\cap : \{0\} \rightharpoonup k^2

obeying these relations:

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

(2) \cap and \cup obey the zigzag equations;

(3) (k,+,0,+ ,0 )(k, +, 0, +^\dagger, 0^\dagger) is a commutative extra-special †-Frobenius monoid;

(4) (k,Δ ,! ,Δ,!)(k, \Delta^\dagger, !^\dagger, \Delta, !) is a commutative extra-special †-Frobenius monoid;

(5) the field operations of kk can be recovered from the generating morphisms;

(6) the generating morphisms (1)-(4) commute with scalar multiplication.

Note that item (2) makes FinRel k\mathrm{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+, \cdot, 0, 1 and also additive and multiplicative inverses in the field kk can be expressed in terms of signal-flow diagrams in the manner we have explained.

So, we have a good categorical understanding of the linear algebra used in signal flow diagrams!

Now Jason is moving ahead to apply this to some interesting problems… but that’s another story, for later.

Posted at April 28, 2015 10:42 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2820

38 Comments & 0 Trackbacks

Re: Categories in Control

All these diagrams are enough to make my head spin!

It seems to me there’s probably a 2-categorical structure here, where a 2-cell would be an inclusion of one relation inside another. Is this something you’ve looked at?

Unrelatedly, is there a categorical characterization of when a network is “stable”?

Posted by: Tim Campion on April 30, 2015 2:46 PM | Permalink | Reply to this

Re: Categories in Control

Tim wrote:

All these diagrams are enough to make my head spin!

If your head doesn’t spin, you’re not doing enough math!

But it might help to say this. In diagrammatic algebra we love commutative monoids:

and we love their upside-down version, cocommutative comonoids:

In linear algebra addition gives us a (dark) commutative monoid, and duplication gives us a (light) cocommutative comonoid, so we are very happy.

But when we work with linear relations we can ‘reflect’ any morphism to get one pointing the other way, so we get another (light) commutative monoid and (dark) cocommutative monoid… so we are twice as happy!

There are two main ways a monoid and a comonoid can fit together. They can form a Frobenius monoid:

and indeed that’s what happens with the dark operations… and also with the light operations:

Or, they can form a bimonoid:

and that’s how the dark operations interact with the light ones… but it’s also how the light ones interact with the dark ones:

So, we’re really in a maximally pleasant context.

There’s a lot to say about why a Frobenius monoids and a bimonoid are the two main ways for a monoid and comonoid to fit together, but I’ll leave that as puzzle.

Posted by: John Baez on April 30, 2015 8:06 PM | Permalink | Reply to this

Re: Categories in Control

Tim wrote:

It seems to me there’s probably a 2-categorical structure here, where a 2-cell would be an inclusion of one relation inside another. Is this something you’ve looked at?

Indeed the category of linear relations is ‘poset-enriched’, which makes it a 2-category of a specially simple sort.

I haven’t thought much about this. Some people have looked at this idea much more generally: for any regular category you can define a category of relations, which poset-enriched, and indeed forms a pleasant sort of category called an ‘allegory’. But there should be extra beautiful features in the special case we’re considering, or maybe in any abelian category.

Unrelatedly, is there a categorical characterization of when a network is “stable”?

Jason Erbele is studying controllability, observability and stability for signal flow networks. We’ll get back to you on that!

Posted by: John Baez on April 30, 2015 8:49 PM | Permalink | Reply to this

Re: Categories in Control

One of the nicest papers at the POPL 2015 conference this year was Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi’s Full Abstraction for Signal Flow Graphs, in which they give an operational semantics for these diagrams (which turns out to be closely related to dataflow programming) and show that it is sound and complete with respect to the categorical semantics.

Posted by: Neel Krishnaswami on May 5, 2015 9:30 AM | Permalink | Reply to this

Re: Categories in Control

Yes, their work overlaps with ours. Right now I’m updating ‘Categories in control’, adding a section at the end where I explain how their descriptions of FinVect k\mathrm{FinVect}_k and FinRel k\mathrm{FinRel}_k are related to ours. I’m also adding a discussion of this new paper:

• Simon Wadsley and Nick Woods, PROPs for linear systems.

which grew out of the old Theorems into Coffee series here on the nn-Café. Nick is a student of mine, so the sudden revival of this old thread is no coincidence.

Posted by: John Baez on May 5, 2015 7:56 PM | Permalink | Reply to this

Re: Categories in Control

Neat! You have a typo in the display for composing linear relations.

Can you explain how your example of an “unexpected relation” follows from the basic relations in the presentation?

In string diagrams … it is essential to be able to read any diagram from top to bottom as a composite of tensor products of generating morphisms

Well, the theory of traced monoidal categories uses string diagrams that have “loops” that can’t be broken down into caps and cups. But maybe that wouldn’t capture the same information that you want?

Posted by: Mike Shulman on May 6, 2015 9:25 PM | Permalink | Reply to this

Re: Categories in Control

Thanks for catching the typo — fixed!

Can you explain how your example of an “unexpected relation” follows from the basic relations in the presentation?

Not offhand; I just know that it must. But you may get your wish. The referee for our paper wants to see some more examples where we use our relations to do stuff. Maybe we could do this one.

Well, the theory of traced monoidal categories uses string diagrams that have “loops” that can’t be broken down into caps and cups. But maybe that wouldn’t capture the same information that you want?

We want a category that contains FinVect kFinVect_k and is at least traced, and FinRel kFinRel_k turns out to be a very natural candidate, which is actually compact.

Alternatively we could consider the “free traced monoidal category on the symmetric monoidal category FinVect kFinVect_k”. But I don’t know what that category is like — or even exactly what it means, since I haven’t thought about “freely throwing in traces”.

So, it was easier to work with a category that I knew about already, namely FinRel kFinRel_k, especially since it has a good conceptual interpretation: a morphism in here is “the behavior of a linear machine”. A linear machine is one whose inputs and outputs are related by some set of linear equations. Its behavior, what it “accomplishes”, is that linear relation.

Brendan Fong and I have studied a category that shows up in electrical engineering, where a morphism is an electrical circuit made of linear resistors, inductors and capacitors. This category has a functor to FinRel kFinRel_k that provides the “semantics” for electrical circuits. In other words, if a circuit is a kind of a machine, we can hit it with this functor and get the behavior of this machine: the relation between its inputs and outputs.

For more, try:

• John Baez and Brendan Fong, A compositional framework for passive linear networks.

Posted by: John Baez on May 7, 2015 4:16 AM | Permalink | Reply to this

Re: Categories in Control

Alternatively we could consider the “free traced monoidal category on the symmetric monoidal category FinVect kFinVect_k”. But I don’t know what that category is like — or even exactly what it means, since I haven’t thought about “freely throwing in traces”.

I’ve been looking for a reference for freely throwing in traces to a symmetric monoidal category, but all that I’ve found is your comment! In case that anyone knows where this has been done, I’d be glad to hear.

Posted by: Tobias Fritz on June 29, 2015 5:46 PM | Permalink | Reply to this

Re: Categories in Control

My immediate reaction was “but isn’t FinVect kFinVect_k already traced, using the good old trace of a matrix?” I think the answer is that it’s traced with respect to the tensor product, but you want to use the direct sum as the monoidal structure. Is that right?

Posted by: Mike Shulman on May 7, 2015 6:16 PM | Permalink | Reply to this

Re: Categories in Control

Mike wrote:

I think the answer is that it’s traced with respect to the tensor product, but you want to use the direct sum as the monoidal structure. Is that right?

Right, exactly! There’s been a huge amount of work on diagrammatic methods for the symmetric monoidal category FinVect kFinVect_k with its usual tensor product, since that’s important in quantum mechanics, Feynman diagrams, quantum groups and knot theory, etc.

But we’re exploring a more fundamental and strangely less studied story: diagrammatic methods for the symmetric monoidal category FinVect kFinVect_k with its direct sum as tensor product. And this turns out to be important in electrical engineering, circuit diagrams, signal flow diagrams and other classical linear systems.

Posted by: John Baez on May 7, 2015 7:36 PM | Permalink | Reply to this

Re: Categories in Control

Thanks for putting this together. Maybe this will turn into the much needed “Categories for the working Electrical Engineer”. A fresh look at signals and systems will do us working engineers good.

I’m wondering if you have applied this line of thinking yet to digital circuits. I’ve always been baffled by the flip-flop. Take a seemingly simple Boolean circuit, feed the output back to input, and you get a system with memory, and one which has oscillating states. See for example the Wikipedia article on SR NOR latch.

Posted by: Rob MacDonald on May 6, 2015 9:35 PM | Permalink | Reply to this

Re: Categories in Control

Someday I hope category theory will be of use to (at least a nonempty set of) electrical engineers. So far the flow of information is going the other way: by trying to understand what electrical engineers are doing, we’re getting new ideas about category theory.

I haven’t thought much about digital circuits or even nonlinear analog circuits. A bunch of the abstract framework we’re developing is applicable to those kinds of circuits. But I find it frustrating to develop abstract frameworks without applying them to concrete examples, so I’ve chosen linear analog continuous-time circuits as my primary example to start with. Once I understand that example, I’ll be eager to work on other examples.

So, thanks for giving me something to learn about and think about: how a flip-flop can be used to store information! It should be tractable, since the math is “already understood” to the satisfaction of practitioners. Yet there should still be interesting things to learn, by studying it with the help of category theory and other mathematical power tools.

Posted by: John Baez on May 7, 2015 4:27 AM | Permalink | Reply to this

Re: Categories in Control

I work on biological control systems and in general these are non-linear. Have I mis-understood or does this only apply to linear control systems?

Posted by: idontgetoutmuch on May 19, 2015 3:38 PM | Permalink | Reply to this

Re: Categories in Control

This post is about linear systems. Many of the techniques used here also apply to nonlinear systems, but many don’t. My real goal is understanding biology, but it seemed wise to spend some time seeing how traditional linear control theory fits into the framework of modern mathematics before moving on to nonlinear systems.

What’s something good to read about biological control systems?

Posted by: John Baez on May 19, 2015 4:58 PM | Permalink | Reply to this

Re: Categories in Control

Caveat: I work on inference for the models and not the actual modelling side itself. I found looking at ecological models more accessible and a simple “foxes and rabbits” is non-linear (the interaction term).

You could try e.g. Elements of Mathematical Ecology by Mark Kot.

In my experience, pharmacokinetic / pharmacodynamic models require more background but they may be of interest. Here are some links:

http://www.amstat.org/sections/sbiop/webinars/2012/WebinarSlidesBW11-08-12.pdf

http://www4.stat.ncsu.edu/~davidian/webinar.pdf

I am sure there are plenty of other biological systems that I have neglected.

Posted by: idontgetoutmuch on May 22, 2015 7:07 AM | Permalink | Reply to this

Re: Categories in Control

idontgetoutmuch wrote:

a simple “foxes and rabbits” is non-linear (the interaction term).

You might like this book, which covers many models of this type:

Mathematically, a ‘Petri net’ is a presentation of a symmetric monoidal category that’s free on some objects and morphisms. Attaching ‘rate constants’ to the morphisms we get a model for the dynanmics of interacting entities. Here’s a Petri net for rabbits and wolves, that gives the model you’re probably talking about:

Here’s a model of an HIV infection, which I discussed here:

So, I’ve been thinking about nonlinear models and category theory from this other viewpoint for a while; connecting those thoughts to the thoughts in this blog article is a project I’d love to tackle soon, especially if I can get a student interested in it!

Posted by: John Baez on May 22, 2015 6:04 PM | Permalink | Reply to this

Re: Categories in Control

This way you develop applications of category theory looks very interesting and promising, but let me introduce another way, more direct and applicable in real engineering.

First, my definition of simple algebraic gadget, monoid. “Monoid” consists of alphabet A and equivalence eq on the set of all words of this alphabet, such that (stability) if xeqy and x is subword of z then zeqz[x\y], where by z[x\y] I understand replacements of x by y in z (arbitrary number of replacements).

In this way we don’t need to define any operations, everything is encoded in (1) basic free structure, words of alphabet and (2) stable equivalence. In this way we can redefine many other algebraic gadgets, including categories, strict monoidal categories, etc. And such definitions are quite enough to solve equations in such gadgets.

But actually we don’t need that. Instead, using this ideology, we can directly research real engineering systems as algebraic gadgets, because any experienced engineer already knows all practical stable equivalences in his area.

Consider javascript programs, for example (JavaScript is famous programming language). As software engineer I know many stable replacements in such programs. But as algebraist I can forget about semantics of execution of this program and consider the set of such programs, equipped with stable relations, as algebraic gadget. And using stable relations I can solve equations.

If this is interesting for you I could explain some real example, posted here: https://jsfiddle.net/j1p0wso0/1

Most obvious application of this is algebraic verification of engineering systems. It means that the set of requirements to such system can be expressed as equation and system can be certified by proof that this system is solution. In this way we can create non-logical, purely algebraic alternative to logical proof-assistants. The big advantage of this approach is that we don’t need to formalize (set-theoretic or other) semantics of system. All we need is a set of stable equivalences.

But also we can move forward, towards automated solving of such equations, and therefore automated synthesis of systems. “Proof assistance” approach cannot do such the step.

Posted by: Osman on May 20, 2015 10:57 AM | Permalink | Reply to this

Re: Categories in Control

Sorry, wrong typography.

Again, “Monoid” consists of alphabet AA and equivalence \simeq on the set of all words of this alphabet, such that (stability) if xyx\, \simeq\, y and xx is subword of zz then zz[x\y]z\, \simeq\, z[x\backslash y], where by z[x\y]z[x\backslash y] I understand replacements of xx by yy in zz (arbitrary number of replacements).

Posted by: Osman on May 20, 2015 11:08 AM | Permalink | Reply to this

Re: Categories in Control

In other words, not only networks (schemes), but any other representations of scientific or engineering information, if these representations are full, can be subjects of algebraic study (through stable equivalences). In fact we can extend category-theoretic notion of doctrine to them and characterize areas of knowledge by these doctrines. I think this is just rebirth of applied math.

Posted by: Osman on June 14, 2015 2:20 PM | Permalink | Reply to this

Re: Categories in Control

In other words. After 10 or 20 years of thinking “what is proper doctrine for ecosystems?” (electrical, mechanical, control systems… etc.) it can become warm enough in our world to stop theoretizing, because global warming never thinks and never stops.

For reducing this time I suggest another way: somehow ask engineers or scientists what are good equations for describing doctrines/internalizations in their areas. They know, I’m sure, but they don’t understand algebra. But instead of asking “about equations” we can ask “what equivalent replacements you use in your networks in practice?”.

Before that we should describe the notion of equivalence. For example, I did that for computer programs in following way:

Say pieces A and B of code are strongly equivalent iff user that have computer with unlimited memory and unlimited performance can tune these parameters so that he will be unable to observe differences between working programs A and B.

After that I have basis for seekeng for equivalent replacements in computer programs - and for solving equations over programs. And I don’t need to describe semantics and write tons of articles seeking for doctrine.

The same can be done for electricity, mechanics, etc.

Posted by: Osman on June 24, 2015 5:11 PM | Permalink | Reply to this

Re: Categories in Control

I’d suggest following algorithm of talking to somebody who can help us:

  1. Find some engineer/scientist with agile mind and wide experience in certain area (experience of designing something - networks, programs, etc.). For example, programer (if area of choice is software engineering) with 2-3 years of experience is not enough, because cannot make replacements in program with enough accuracy.

  2. Sit down together and show how do you solve some equation in string diagrams. Don’t explain categories. Don’t say “composition”, “operation” or “tensor product”. Never say about tensor unit. All you can use is “we can replace this subnetwork by that subnetwork by rule…”.

  3. Then ask to show what replacements he does usually in his networks (programs, something else …).

  4. Of course our goal is to collect rich enough set of replacements. But it would better if this would become his goal, not only your. So try to demonstrate that you can solve practical equations in that networks, in that area. Show that his intuition for replacements (semantics!) is not needed anymore - everything can be done using just knowledge of certain rules of replacements.

  5. In case of success he will quickly show wide and rich set of replacements (as I can do in case of programming) that you will never find from any books or articles.

Posted by: Osman on July 3, 2015 11:39 PM | Permalink | Reply to this

Re: Categories in Control

I agree that this is a good strategy. I seem to be doing okay looking at diagrams in textbooks, translating them into category theory, and discovering new things to say. But working with cooperative experts would clearly have a lot of advantages.

Posted by: John Baez on July 4, 2015 6:57 AM | Permalink | Reply to this

Re: Categories in Control

Of course you are okay, because it’s just you. But I’m looking for how to make this work more regular and widely available.

Posted by: Osman on July 4, 2015 8:20 AM | Permalink | Reply to this

Re: Categories in Control

It will happen. This is new applied math and you created it.

Posted by: Osman on July 4, 2015 9:18 AM | Permalink | Reply to this

Re: Categories in Control

I hope something like this happens! I’ve discovered, rather sadly, that I’m not very good at organizing projects like this.

Posted by: John Baez on July 4, 2015 8:51 AM | Permalink | Reply to this

Re: Categories in Control

John Baez wrote:

I seem to be doing okay looking at diagrams in textbooks, translating them into category theory

My idea is in fact inverse to your. You move domain information into categorical framework, but I suggest to move CT approaches into languages or notations specific for domain. It’s quite possible using ideology of equivalent replacements, including functors, natural transformations and all machinery. I demonstrated the formal idea in my redefinition of monoid above, https://golem.ph.utexas.edu/category/2015/04/categoriesincontrol.html#c049036

So, there are some different features:

  1. Go inverse direction.
  2. Research not only networks but any other notations where equivalent replacements make sense.
  3. Create specific software to make calculations simple.
  4. Pursue certain goal: first certify (verify) models of systems and then synthesize them automatically (when software will solve some equations automatically).

I’m sure it’s necessary to make your ideas used widely.

Posted by: Osman on July 7, 2015 12:57 PM | Permalink | Reply to this

Re: Categories in Control

This question is only tangentially on topic, but what the hell…

I am a working electrical engineer who reads math as a hobby.

I picked up and worked through J.L. Bell’s (excellent!) book “a primer on infinitesimal analysis”.

I was wondering if this theory was extended, and I am using that term loosely, to capture (explain?) Dirac Delta functions (or maybe Distributions would be a better term?)

I found researching the nLab and some papers on Anders Kock’s website that Lawvere/Kock/others have developed a theory of distributions, which I think is related to schwartz distributions. But to be honest, as a category theory-wise dumb EE, who doesn’t know what an inf-groupoid is I am snowed by them!

If anyone reading this blog comes knows of any treatment of Delta functions that is “elementary”, or readable like J.L. Bells’ book, I would love to read it.

This subject fascinates me. It is sort of amazing the calculations that are done with distributions and convolutions by engineers with only a paucity of theory to back them up. for example, pick up say “Continuous and Discrete Signals and Systems” by Soliman and you will find calculations where an infinite train of equally spaced delta functions is convolved with a real signal to produce a sampled output. And these calculations are done (or expected to be) by undergrads who just finished calc 101.

I was so impressed by the Kock/Lawvere presentation of calculus wherein basic theorems are “algebraized” and I have always wondered if there was something similar for delta function (calculations).

Any recommendations welcome.

Cheers

Posted by: Rob MacDonald on August 28, 2015 5:39 PM | Permalink | Reply to this

Re: Categories in Control

I imagine that people working on nonstandard analysis (that is, infinitesimals) have some fun ways to think about the Dirac delta and other distributions. Maybe Lawvere and Kock have some nice ways too. But, I don’t know any of these approaches. I just learned the usual nonrigorous approach to distributions in my physics classes, together with the usual rigorous approach in my real analysis classes.

Posted by: John Baez on August 31, 2015 5:18 AM | Permalink | Reply to this

Re: Categories in Control

There are two types of infinitesimals. The infinitesimals used in non-standard analysis à la Robinson are part of a field, which is to say a system of arithmetic in which one can take reciprocals of non-zero elements. These may be called “invertible infinitesimals”.

The other kind of infinitesimals as used in the Kock-Lawvere axioms are very different; particularly, the elements dd of the object DD that they use satisfy d 2=0d^2 = 0. These are called “nilpotent infinitesmals” (‘nil’ = zero; ‘potent’ = power, i.e. an element which raised to some power is zero). They are definitely not invertible, since if d 1d^{-1} exists then so does d 2d^{-2}, which would be an illegal inverse of 00.

The best kinds of models of synthetic differential geometry or SDG, as developed by Kock, Lawvere, and many others, have both sorts of infinitesimals inside them. The linear differential calculus that involves derivatives, differential forms, integration of linear forms, Stokes’ theorem, and so on – this is developed in terms of nilpotent infinitesimals. My understanding is that Dirac distribution and such is developed in terms of the other kind, invertible infinitesimals. I’m not an expert, but my intuition for the difference is that the Dirac distribution is approximated in finite terms by a function supported over (ϵ/2,ϵ/2)(-\epsilon/2, \epsilon/2) whose average value is 1/ϵ1/\epsilon, and expressed in infinitesimal terms by a function supported over an interval of infinitesimal length ee but with an average value of 1/e1/e, hence invertible.

Posted by: Todd Trimble on August 31, 2015 12:51 PM | Permalink | Reply to this

Re: Categories in Control

I’m not an expert either, but my impression is that the invertible infinitesimals in some models of SDG are not as good for this sort of thing as the infinitesimals in NSA. They don’t have as good of a transfer principle, for instance.

Posted by: Mike Shulman on August 31, 2015 6:08 PM | Permalink | Reply to this

Re: Categories in Control

John wrote:

We use the field k=(s)k = \mathbb{R}(s) consisting of rational functions in one real variable ss. A linear relation from k mk^m to k nk^n is thus a system of linear constant-coefficient differential equations relating mm ‘input’ signals and nn ‘output’ signals.

I don’t understand this. Take m=n=1m = n = 1. Then you’re saying that a linear subspace of kk=k 2k \oplus k = k^2 is a system of linear constant-coefficient differential equations relating a single input signal and a single output signal.

If I correctly understand what you mean by ‘signal’, this means that a linear subspace of k 2k^2 is a system of linear constant-coefficient differential equations in a function \mathbb{R} \to \mathbb{R}. Is that right so far?

Whether it’s right or not, maybe you can explain the following example. Let LL be the linear subspace of kkk \oplus k spanned by (λ,μ)(\lambda, \mu), where λ,μ(s)\lambda, \mu \in \mathbb{R}(s) are defined by

λ=s 2+6s1s+1,μ=s+3s 5+2. \lambda = \frac{s^2 + 6s - 1}{s + 1}, \qquad \mu = \frac{s + 3}{s^5 + 2}.

What system of differential equations does LL correspond to?

Posted by: Tom Leinster on February 4, 2016 4:46 PM | Permalink | Reply to this

Re: Categories in Control

Hi, Tom! I’m glad you asked a question, because I think this stuff here is cool.

If I correctly understand what you mean by ‘signal’…

To be precise, I might mean an infinitely differentiable function f:f: \mathbb{R} \to \mathbb{R} with f(t)=0f(t) = 0 for t0t \le 0. That should work fine.

There are other spaces of functions or distributions that would also work. All that really matters is that our set SS of signals is an (s)\mathbb{R}(s)-module. In the examples that really matter, like the example I just gave, ss acts as differentiation:

sf:=f sf := f'

and we can get any rational function of ss to act on SS, via Laplace transforms.

Say we have ψ(s)\psi \in \mathbb{R}(s) and we want it to act on a signal fSf \in S. Then we take the Laplace transform of ff, multiply it by ψ\psi, and take the inverse Laplace transform of the result.

When ψ(s)=s\psi(s) = s, this differentiates ff.

When ψ(s)=s 1\psi(s) = s^{-1}, this integrates ff. More precisely, it gives us the antiderivative FF defined by

F(t)= 0 tf(u)du F(t) = \int_0^t f(u) \, d u

If you know Laplace transforms, what I’m saying should sound familiar.

this means that a linear subspace of k 2k^2 is a system of linear constant-coefficient differential equations in a function \mathbb{R} \to \mathbb{R}. Is that right so far?

Not exactly.

If we take k=(s)k = \mathbb{R}(s), a subspace of kkk \oplus k is a linear relation from kk to kk. And this is supposed to describe some collection of linear constant-coefficient differential equations relating one input signal, say ff, to one output signal, say gg. If the relation is actually a function, the output gg will be a function of the input ff. That’s the case engineers actually think about. But the other cases turn out to matter for mathematical reasons.

To make life easy on me, you chose the simplest example of a subspace of kkk \oplus k: namely, the one spanned by (λ,μ)(\lambda, \mu) where

λ=s 2+6s1s+1,μ=s+3s 5+2. \lambda = \frac{s^2 + 6s - 1}{s + 1}, \qquad \mu = \frac{s + 3}{s^5 + 2}.

Note that this subspace is also spanned by

(1,μλ) (1, \frac{\mu}{\lambda})

Thus, this linear relation is actually a linear function from kk to kk: the function sending any fkf \in k to g=μλfg = \frac{\mu}{\lambda} f .

But now, if we have any kk-module, like our set SS of ‘signals’, we can use the same formula to define a function sending an input signal fSf \in S to an output signal gSg \in S:

g=μλf g = \frac{\mu}{\lambda} f

If your λ\lambda hadn’t been invertible, this wouldn’t make sense, and I couldn’t express the output as a function of the input. But I could still have written

λg=μf \lambda g = \mu f

and gotten a linear relation between input and output.

What does this relation actually say in your example? Where are the differential equations hiding?

Well, with your λ\lambda and μ\mu we have

s 2+6s1s+1g=s+3s 5+2f \frac{s^2 + 6s - 1}{s + 1} g = \frac{s + 3}{s^5 + 2} f

or equivalently

(s 2+6s1)(s 5+2)g=(s+3)(s+1)f (s^2 + 6s - 1)(s^5 + 2) g = (s+3)(s+1) f

In the examples that matter, ss has the meaning of differentiation, so we get this differential equation relating the output gg to the input ff:

(d 2dt 2+6ddt1)(d 2dt 2)g=(ddt+3)(ddt+1)f \left(\frac{d^2}{d t^2} + 6 \frac{d}{d t} - 1\right)\left(\frac{d^2}{d t^2}\right) g = \left(\frac{d}{d t} + 3\right) \left(\frac{d}{d t} + 1\right) f

Voilà!

Note: I’m using the fact that a linear relation from k mk^m to k nk^n gives a linear relation from S nS^n to S mS^m whenever SS is a kk-module. I’m just ‘tensoring with SS’.

I hope that wasn’t too confusing. If the procedure seemed mysterious, please ask another question.

Posted by: John Baez on February 4, 2016 10:28 PM | Permalink | Reply to this

Re: Categories in Control

Thanks for the detailed answer.

One thing that really makes a difference is the space of functions you’re using:

I might mean an infinitely differentiable function f:f\colon \mathbb{R} \to \mathbb{R} with f(t)=0f(t) = 0 for t<0t \lt 0.

That restriction is very important! I’d understood that ss meant differentiation. But ss is also a nonzero scalar in the base field, so the system of differential equations corresponding to the linear subspace span{(λ,μ)}span\{(\lambda, \mu)\} of kkk \oplus k must be the same system that corresponds to span{(sλ,sμ)}span\{(s\lambda, s\mu)\}. And that seemed wrong.

For instance, the subspace span{(1,0)}span\{(1, 0)\} of kkk \oplus k corresponds to the trivial differential equation f=0. f = 0. The subspace span{(s,0)}span\{(s, 0)\} of kkk \oplus k corresponds to the not-quite-so-trivial differential equation dfdt=0. \frac{d f}{d t} = 0. But since ss is a nonzero scalar, span{(1,0)}=span{(s,0)}span\{(1, 0)\} = span\{(s, 0)\}. So in order for your correspondence between subspaces and systems of differential equations to work, we must have dfdt=0f=0. \frac{d f}{d t} = 0 \implies f = 0.

Of course, that’s usually not the case. But it is if ff is restricted to lie in the function space you mention.

Posted by: Tom Leinster on February 5, 2016 1:46 AM | Permalink | Reply to this

Re: Categories in Control

Yes, electrical engineers have this habit, somewhat mysterious at first, of treating integration as a two-sided inverse to differentiation, as if they didn’t know that functions differing by a constant have the same derivative.

However, their excuse is that they mainly build machines that only start working after you turn them on. Thus, they can assume their signals are zero for t0.t \le 0. This fixes the constant of integration in a way that makes integration a two-sided inverse to differentation.

And the payoff is that their machines, if linear and time-translation-invariant, can be treated as linear relations from k mk^m to k nk^n, where kk is some field of functions in the Laplace transform variable ss. The easiest case is k=(s)k = \mathbb{R}(s). But even in this case, they like to think of these rational functions as functions on the complex plane. This lets them prove nice theorems connecting complex analysis to the behavior of their machines.

The only advantage Jason and I have over these electrical engineers is 1) we know category theory and 2) we know that linear functions are a special case of linear relations.

Posted by: John Baez on February 5, 2016 2:14 AM | Permalink | Reply to this

Re: Categories in Control

Right. And it’s not just that differentiation is being treated as a bijective process. Any differential equation of the form

a nf (n)+a n1f (n1)++a 1f+a 0f=g a_n f^{(n)} + a_{n-1} f^{(n - 1)} + \cdots + a_1 f' + a_0 f = g

(where the a ia_i are constants and gg is a “known” function) is assumed to have a unique solution ff. That’s pretty radical.

We really have to lean on that assumption that our functions f(t)f(t) are not only zero for t0t \leq 0, but also infinitely differentiable at 00. Those engineers must be very sure that their machines start smoothly.

Posted by: Tom Leinster on February 5, 2016 5:12 PM | Permalink | Reply to this

Re: Categories in Control

Engineers are very realistic and practical about these issues. The small piece of their formalism I’ve described may seem unrealistic taken in isolation, but it’s not used in isolation.

For example, engineers carefully avoid building machines that are described by unstable differential equations — ones where small disturbances amplify over time. Stability can be characterized using the location of the zeros and poles of the rational functions in ss that we’ve been discussing. For example,

f+f=0 f'' + f = 0

is stable but

ff=0 f'' - f = 0

is not, because the latter has a solution that grows exponentially over time, ultimately because

s 21=0 s^2 - 1 = 0

has a root with positive real part.

I suspect that for stable differential equations, your worry become less significant: the solution ff of a stable nnth-order linear ODE should not change dramatically if we change the initial data f(0),,f (n)(0)f(0), \dots, f^{(n)}(0) slightly.

Also, if you’re worried about whether functions really do have infinitely many derivatives, I believe we could also take our space of signals SS to consist of tempered distributions supported on the positive half-line. Then SS contains very nasty functions like step functions, but any element of SS can be differentiated to give another element of SS.

Anyway, these are just my off-the-cuff guesses, but I know that engineers have thought about these issues a lot more deeply than I have.

Posted by: John Baez on February 6, 2016 3:41 AM | Permalink | Reply to this

Re: Categories in Control

I’m not sceptical or worried — I’m just getting used to the idea of a world in which all linear differential operators are invertible. It hadn’t occurred to me that such worlds might exist. It’s interesting that they do, especially ones large enough to include tempered distributions.

I admit, I was also a little amused. You memorably explained:

However, their excuse is that they mainly build machines that only start working after you turn them on.

So I imagined a serious, oily piece of machinery, like a two-stroke engine or steam engine or something, being started up…

Man starting outboard motor

But then I read that it had to start infinitely smoothly, which, with that image in my head, made me smile. But I’m not making any serious or informed objection.

Posted by: Tom Leinster on February 8, 2016 2:17 PM | Permalink | Reply to this

Re: Categories in Control

Okay! Sorry, these days I react a bit defensively sometimes when mathematicians seem to be criticizing engineers (or, for that matter, vice versa). I’m trying to category theorists — often misunderstood as the ‘the purest of pure’ mathematicians — to talk a bit more to engineers, and vice versa.

In fact, category theorists often seem pretty interested in doing this, since they like to unify things, and they’re always looking for new sources of inspiration.

So far, I’m better at getting ideas from engineering to interest category theorists than vice versa. But I hope that someday the flow of ideas will be two-way…

Posted by: John Baez on February 8, 2016 5:50 PM | Permalink | Reply to this

Post a New Comment