23. Frobenius Snakes and Spiders

separator

Graphical linear algebra is about the beautifully symmetric relationship between the operations of adding and copying numbers. The last episode was all about adding, the white structure of our diagrammatic language, using the new relational intuitions. Since copying, the black structure, is the yin to adding’s yang, in order to attain karmic balance we start this episode by shifting our focus to black diagrams. It turns out that the story is eerily similar: it’s the bizarro world all over again.

So, let’s take stock of what we know about copying. Here’s the generator that we already know quite well:

copyWith the relational interpretation, it represents the relation Num ⇸ Num×Num with elements

copyrelel

where x is any number. All this is saying, in the language of relations, is that the behaviour of the copying generator ensures that the three values on the dangling wires are all the same.

The relational interpretation of discard, copy’s sidekick

discard

is a relation of type Num ⇸ {}, but unlike zero from the last episode, it is not a singleton relation. Instead, it contains all elements of the form

( x, ★ )

where x is any number. This just means that discard, unlike backwards zero that “accepts” just 0, is not discriminating in the slightest.

From Episode 7, we know that copy and discard satisfy the commutative comonoid equations:

copying

And of course, these still make sense with the new, relational interpretation.


In the last episode we introduced the mirror image of the adding generator.This was backed by the relational interpretation; by thinking in terms of relations we could make sense of what it means to “add backwards”.

We can now do a similar thing with the copy and discard generators. We get a brand new generator, a backwards copy, or “copy-op”:

copyop

which, although not a function from left to right, is a relation of type Num×Num ⇸ Num. This relation is, as expected, the opposite of the one for ordinary copy:

copyoprel

The second new generator is the backwards discard

discardop

with relation { (★, x) | x ∈ Num }.

Not surprisingly, the mirror images of copy and discard satisfy the mirror versions of the equations for copy and discard.

copyingop


Now that we’ve seen both reverse adding and reverse copying, it’s natural to ask if anything interesting happens if these two structures meet. Back in Episode 8 we went through what happens when the ordinary versions of adding and copying meet.

So imagine you are standing in front of someone who is looking in the mirror. Do you get any more information from looking at the mirror than directly at the person? Typically not so much, the information is the same, but reversed. This is also the case for mirror add and mirror copy: they interact in the same ways, but backwards. Here’s a rundown of the equations; they are just the mirror image of the ones we discussed in Episode 8.

addingcopyingop


As in the case of adding, the interesting stuff happens when copying meets its mirror image. If you’ve just read the previous episode, the equation below will fill you with a sense of déjà-vu.

bfrob

Yes, it’s none other than a black version of the famous Frobenius equation.

In the last episode, to see that the white version of (BFrob) made sense, we had to do a few, admittedly simple, calculations. Here, the job is even easier: the copy generator carries the same value on all the wires; so tagging wires with the numbers that flow on them we see that the behaviour of the left hand side of (BFrob) ensures that all of the wires carry the same value.

froblvars

The story is similar for the right hand side of (BFrob).

frobrvars

In both the left and the right hand side of (BFrob), it’s thus quite simple to compute the underlying relation: it contains as its elements those pairs of elements that look like this

frobrel

where x is any number. The relations of the left and the right hand sides agree, so (BFrob) makes sense for copying.

So what other equations hold? Here’s another one that we’ve seen a few times by now: the special equation.

special

Again, just by looking at the thing, it’s pretty obvious that it works. On the left hand side of (BSpecial), the copy and it’s mirror image make sure that all the wires carry exactly the same value, meaning that the only behaviour exhibited is the one where the values on the dangling wires are the same. Which is the same behaviour as that of a single wire, the right hand side of (BSpecial).

Finally, we also have the bone, in black.

bbone

Summing up, we have identified three equations, just as we did in the last episode.

copyingcopyingop


Since we’ve now seen the Frobenius equation in two different contexts, it’s worthwhile to step back and see what interesting properties hold in Frobenius monoids, the algebraic structure that we mentioned briefly in the last episode. Stepping back and thinking more generally will help us get a better feeling for what’s going on under the hood. For the purposes of this discussion, we will switch to anonymous gray mode, remembering that the gray can be replaced either by white or black.

Here are the equations of Frobenius monoids again.

frobeniusmonoid

There are two interesting diagrams that can be built using the generators in any Frobenius monoid. First, we have a diagram with two dangling wires on the left and none on the right:

epsilon

and second, its mirror image, with two wires on the right and none on the left:

eta

Now, we can plug these two constructions into each other to form two different kind of “snakes”:

snakes

These two are involved in the snake lemma: both the snakes are actually equal to the identity wire. So, one intuitive way to think of  gadgets  and  is that they are a bent wire. When we compose such bent wires, we can stretch them back to get an ordinary straight wire.

snake

Here’s a proof of the second equality, which uses the Frobenius equation. The proof for the other equality is similar.

snakeproof

Because of the snake lemma, it turns out that any PROP with a Frobenius monoid structure is an instance of something called a compact closed category. Compact categories are all about bending things; we will say more about them in future episodes.


Maths is full of pretentiously sounding “fundamental theorems”, although perhaps this kind of language has become somewhat passé in recent decades. There’s the fundamental theorem of calculus, fundamental theorem of algebra, and a fundamental theorem of x for several other choices of x. The adjective fundamental is not really a precise classification; there is no definitive, widely accepted test of fundamentality. Rather, it’s more of a sociological endorsement that identifies a particular result because it holds some kind of spiritual, quintessential centrality for the field in question. A feeling that the point of view expressed by the theorem is a nice representation, a microcosm, of the subject as a whole.

Similarly, some people call the Euler identity e + 1 = 0 the “most beautiful equation” because it links, in one statement, some of the most important 19th century mathematical concepts: e, iπ, with timeless favourites 1 and 0. The 1 and the 0 may seem to be a bit contrived, and -1 seems to be getting a short shrift, why not e = -1? Not that I want to pick a fight with Euler.


It’s time for two particularly useful equations. In the spirit of pretentiousness and Platonic pompousness, we could call these the fundamental equations of graphical linear algebra, or the most beautiful equations, since they involve all of the generators that we have considered so far. But let’s not.

Here are the equations, which are mirror images of each other. Both feature the kind of “bent wires” that we were talking about before.

cc1

cc2

Let’s focus on  and calculate the relations. In the left hand side, we are composing the relation

addrel

with the singleton relation

zerorel

The operation of composition can be thought of as imposing a condition on the result of x+y.  Indeed, the composed relation consists of those elements

composed

where x+y=0. But to say that x+y=0 is to say that y=-x. In other words, the relation can be described as consisting of elements

final

where x is any number. But this is clearly the relation represented by the right hand side of , since the relational interpretation of the antipode is the relation with type Num ⇸ Num that consists of pairs (x,-x) for all numbers x.

 The justification for  is symmetric.


We have seen the snake lemma, it’s time for the spider theorem. It applies in special Frobenius monoids — those Frobenius monoids in which we also have the special equation. This, as we have seen, covers both the copying and the adding in graphical linear algebra. Here are the relevant equations.

specialfrobenius

In a very precise sense that we will eventually make clear, this theory, lets call it F, is dual to the theory we have been calling B, the theory of bimonoids. Remember that B consists of those equations that describes the interactions between adding and copying. Here’s a reminder of the equations, which by now we know quite well.

bimonoid

Back in Episode 16, when we were proving that a diagram in B is really the same thing as a matrix of natural numbers, we argued that diagrams in B can be factorised so that all the comonoid structure comes first, then the monoid structure: doing this made our diagrams look a lot like matrices. In F, the theory of special Frobenius monoids, the opposite thing is true: any diagram can be factorised so that all the monoid structure comes first, followed by all the comonoid stuff.

What this means is that any connected diagram from m to n is equal to the one in the picture below, where we use our usual syntactic sugar that collapses repeated multiplications and comultiplications:

spider1

This suggest an even better syntactic sugar for connected diagrams in special Frobenius monoids: a spider!

spider2

So—long story short—any diagram in F can be seen as a collection of jumbled up spiders: this result has become known as the spider theorem. Here’s an example with three spiders.

spidersex

Notice that if we have the bone equation around, we can get rid of the unfortunate legless spider. One more thing: when two spiders connect, they fuse into one spider. This is a really nice way of thinking about diagrams in F.

The spider theorem was proved by Steve Lack, in the paper Composing PROPs that we have already mentioned on more than one occasion. But later, it took on a life of its own, due to the usefulness of diagrammatic reasoning in quantum computing. The person probably most responsible for this is Bob Coecke; this paper with Eric Paquette is a good example of spiders in action.


It’s again been a pretty hectic few weeks for me.

Two weeks ago I was in Lyon for Fabio’s PhD defence. It’s now possible to download his thesis, which received high praise from the very impressive thesis committee. The thesis is currently the most thorough account of graphical linear algebra and its applications, so do take a look! After a well earned doctorate, Fabio has now moved to Nijmegen in the Netherlands to take up a postdoc.

Last week I was deep in paper writing mode, trying to meet the FoSSaCS deadline. If you remember Episode 2, this for me means pretty hard work. I get a bit too obsessive when writing, and the process takes up all of my time and energy: fortunately, the closer to the deadline, the more the adrenaline kicks in to keep you going. Deadlines are great at forcing you to get something done, but afterwards you end up feeling somewhat exhausted. So I tried writing for the blog this last weekend and it ended up feeling a bit too much like work, which is really not the point.

The paper itself, which has just been put up on the arXiv, is something that I’m really excited about. If you flick through it, I’m sure that you will recognise many of the equations! My coauthors are Brendan Fong, a brilliant PhD student of John Baez, whom we met in Episode 10, and Paolo Rapisarda, who is a control theorist in Southampton and an ex-PhD student of Jan Willems, whom we met in Episode 20. Academia is a small world. Anyway, it was a really fantastic collaboration; I very much enjoyed doing the research and I learned a lot from both Brendan and Paolo.

The paper is about the class of linear time-invariant dynamical systems, a foundational playground of control theory, where basic concepts that gave birth to the subject, such as controllability and observability, show up. In the paper, we give an equational characterisation—which means, for example, that questions about controllability can be reduced to looking at the shape of the diagrams that represent dynamical systems.

Next week I’m off to Cali, Colombia to talk about graphical linear algebra and its applications at the ICTAC conference. Then, hopefully, the noise will die down a little bit so that I can spend a bit more time on the blog.

Continue reading with Episode 24 – Bringing it all together.

22. The Frobenius Equation

After all the hype about relations in the last two episodes, it’s high time to use them to do something interesting. Let’s start by quickly reviewing the relational interpretation of our addition and zero generators. First, the addition:

add

Using our updated intuition, we are thinking of this as representing a relation of type Num × Num  ⇸  Num, defined as the set of all pairs

pairs

where x, y and z are any numbers that satisfy the condition x+y=z. So, for example, this relation contains the following three elements:

addexamples

The zero generator

zero

also has a relational interpretation. Its type is  {★} ⇸  Num. The reason for this is that Num0 is actually a singleton set—that is, a set containing precisely one element—and, since the name of this element does not matter, we may as well call it . The relational interpretation of the zero generator is the singleton relation

{(★, 0)}.        (‡)


 

The fact that Num0 is a singleton is related to a fact memorised by everyone in high school: we all know that k0 = 1 for any integer k. We will not spend a lot of time getting very deep into this now; let me just say that it’s one of the things that category theory can explain really well, maybe even better than people on Quora. I will just outline the basic idea—and if the following is too technical, don’t worry, it’s not important for our story.

The cartesian product of sets is an example of a general phenomenon called a limit. Binary, tertiary, and n-ary cartesian products (sets of pairs, triples, n-tuples, and so forth) are particularly simple instances: they are limits indexed by very simple categories.

For example, binary cartesian products are limits indexed by a category with two objects and only identity arrows. Such very simple categories, where there are no non-identity arrows, are sometimes called discrete.

Then, n-ary cartesian products are limits indexed by a discrete category with n objects. So what is a zero-ary cartesian product? A limit for the discrete category with no objects (i.e. the empty category) has its own name: it’s called a terminal object. And, in the category of sets, any singleton does the job of being terminal.


 

One of the things that you can do with relations that you can’t, in general, do with functions is turn them around. The result is sometimes called the opposite relation. We can use this idea to make sense of the following new generator, which looks like the mirror image of addition:

addrev

We will be thinking of this strange new beast as representing “addition backwards”. Although that does not make much sense as a function from left to right, it makes perfect sense as a relation; it is the one that consists of pairs

pairsrev

where x, y and z are any numbers that satisfy x+y = z. Of course, this is just (†), but backwards.

We can also reflect the zero generator to get a new generator that looks like this:zerorevThe relation this generator represents is, not surprisingly,

{(0, ★)}

which is just (‡) backwards.

As we do more graphical linear algebra, you will see that these mirror versions of addition and zero are extremely useful to have around!


Back when we were talking about ordinary addition, we identified some equations that concern the addition and zero generators. These were (Comm), (Unit) and (Assoc), and here they are again:

adding

Since the backwards addition is still addition, it satisfies the same equations, but backwards.

addingop

It’s useful to notice that these end up looking a lot like the equations for copying; here they are again, as a reminder:

copying

In fact, the equations for adding backwards and copying are exactly the same, apart from the colouring of the nodes. The colours make sure that we don’t confuse backwards addition and copying, since our intuition is that they stand for different relations. Also, again in order to avoid confusion, we tag all the new equation names for with op, for opposite. We will come back to copying, viewed relationally, in the next episode.

The equations for backward adding are not controversial. In fact, they are rather boring, and we have not really discovered anything new about addition so far. The interesting, new stuff comes when we think about what happens when addition sees itself in the mirror.


So what happens when we connect the adding generator to its mirror image? Let’s focus on the most interesting examples first, and concentrate on the relation represented by the following diagram:

frobleft

We could translate everything back to first principles and compute the composition as in Rel, but just by looking at the diagram it’s clear that there are three variables involved; the numbers on the three wires that connect as arguments to the two additions. Let’s call these x, y and z and label the wires accordingly:

frobleftann

So, the relation consists of pairs

frobleftrel

for all choices of x, y and z. For example, taking x=1, y=-1 and z=3, we see that

frobleftex

is in. Another example, taking x=3, y=2, z = -5 gives us

frobleftex2

Looking at these examples, it seems that there may be another way of describing these pairs: those in which if we add the components, we get equal sums. Indeed, in the examples above we have 1+2 = 0 +3 = 3 and 3+-3 = 5 + -5 = 0.

So let’s see if is actually the same relation as ② below, which consists of all pairs

frobmidrel

where p+q = r+s. Incidentally, ② is the relation represented by:

frobmid

Just by looking at  and , clearly every  is an instance of , since summing up either of the two components of  gives x+y+z. Then to show that  and  are the same relation, it’s enough to to show that every instance of  is an instance of .

So lets take a closer look at . Since p+q = r+s, we can express each variable in terms of the other three, so in particular q=(r-p)+s and r=p+(q-s). This is almost in the form required by , we just need to show that r-p = q-s and indeed:

r-p = p+(q-s)-p = q-s.

That finishes the job:  and  denote the same relation. These arguments give us the justification for introducing the following intriguing equation.

frob1

In fact, the argument above can be recycled to show that also

frob2

since the calculations involved are clearly symmetric.

A nice way of memorising  is that it says “Z = X”: the diagram on the left looks a bit like the letter Z and the one on the right looks like an X. Then, the mnemonic for  says, for similar reasons, that X = S. Together, we have Z = X = S, and so in particular Z = S.

frob

These three equations are quite famous; they are called the Frobenius equations. It’s a little bit redundant to keep all three, because it turns out that all three of (Frob),   and  are equally powerful: any one one of them lets you prove the other two, using diagrammatic reasoning. So, out of the three, we will just keep (Frob) because it is the most symmetrically pleasing.

For example, below there is the proof of , assuming that we have (Frob). I’ll leave the other five implications for you as nice exercises!

frobproof

By the way, structures satisfying these equations, repeated below in an anonymous, gray mode, are often referred to as (commutative) Frobenius monoids.

frobmonoid


Ferdinand Georg Frobenius was a German mathematician, active in the late 19th and early 20th century. He was very good, but he also happened to have an extremely cool last name. These two facts combined mean that a surprisingly large number of mathematical notions are called after him. He also had a pretty inspirational beard, as verified by the following photo.

Frobenius

The Frobenius equation (Frob) is probably most famous for the role it plays in the impressively named and difficult-sounding field of 2-dimensional topological quantum field theories (2D TQFT – even the acronym is scary!). There’s a very nice book on the subject by Joachim Kock called  Frobenius algebras and 2D topological quantum field theories. You can’t say that the title is misleading. And 2D TQFT, despite the name, is actually not that difficult to get your head around. A bit like the Sierpinski space.

Frobenius didn’t actually discover the Frobenius equation. As is often the case, there is a bit of controversy about who exactly thought of it first. Mathematicians can get quite uppity about this sort of thing. Some mathematics message boards descend into mini flame wars as people argue about what exactly was written in the corner of some blackboard at an obscure conference somewhere off the coast of Britain in the mid 1960s. I guess that professional mathematicians are amongst the very few people who actually remember any details of that particular decade.

My feeling is that—as is not uncommon with good maths—it’s likely that number of people thought of it at around the same time. The Frobenius equation was in the air. And it’s going to be a favourite of ours on this blog.

Having said all that, one of the earliest people to realise the importance of the Frobenius equation was Bob Walters, who I’ve talked about in Episode 12. If you’re interested in some of the history, you can take a look at a blog entry of his here where he wrote about some of its history. Note that Bob talks about the equation X=S, our equation . But as we’ve discussed before, it doesn’t matter which one of (Frob) or  you consider.


There are two more equations that show interesting ways in which addition interacts with itself in the mirror. We have already seen the first one in the last episode, where it featured as one of the equations of the special bimonoid, the structure isomorphic to the PROP of relations. It is none other than the “special” equation. Unfortunately the name “special”—terrible as it is—seems to have caught on, so we are stuck with it. Here it is:

specialLet’s convince ourselves why it makes sense in our context of addition interacting with its mirror image. Doing the simple calculation, the left diagram represents the relation

{ (x, y) | there exist numbers u, v such that u+v = x and u+v = y }.

Now, given any element (x, y) in this relation, it’s easy to see that x = y, since they are both equal to u+v for some u and v. Also, for any number z, (z, z) is in the relation because we can take, for example, u = z and v = 0. These two arguments combine to mean that the relation is actually the identity relation

{ (x, x) | x is a number }

which is, of course, the relational meaning of the identity wire. So, long story short, (Special) is compatible with our intuitions.

The second equation, (WBone), is pretty self evident: it’s the white version of the bone law from Episode 8. Both of the diagrams in (WBone) represent the relation that contains the single element (★,★).

wbone

The table below summarises the equations that we have discussed in this episode, which capture the various ways in which addition interacts with its backwards twin.

addingaddingop


Unfortunately, the rate of articles has slowed down somewhat recently. This is mainly due to the time of the year: it’s the start of semester, so teaching, supervision and related activities are taking up a lot of my time.  Also, coincidently, this is the time of year when there are a few paper deadlines. And on top of all that I have a few pretty exciting research leads to chase. I’m sure that some of these will make it on the blog eventually.

I hope that the pace will pick up again in October. If you’ve stuck with the series so far, let me just say that we are getting very close to the really interesting stuff!

Continue reading with Episode 23 – Frobenius Snakes and Spiders.