8. When Adding met Copying…

Let’s start with a recap. Last time I claimed that linear algebra was all about what happens when adding and copying interact. So far, though, we have only focussed on properties satisfied by adding and copying in isolation. Properties such as (Comm) and (CoComm).

We noticed that adding and copying are bizarro version of the other: not only in the way that they look, but also in the equations that they satisfy. Remember that the word bizarro, as we have been using it, means to reflect the diagram and invert the colours. Left switches places with right, and white switches places with black.

In this episode, copying meets adding for the first time. Sparks fly.


 

It’s time to meet one of the most interesting equations of graphical linear algebra.

bialg

Equation (B1) is by far the most complicated of the ones that we have seen so far, so let’s stop for a moment and take the time to understand and appreciate it. First, notice that both the left hand side and the right hand side have the same number of dangling wires on both sides: two on the left and two on the right. Remember that it is important that any equation that we write down satisfies this property: otherwise the compositionality property—that is, swapping diagrams for equal diagrams in some larger context—wouldn’t make any sense since we wouldn’t know what to do with the extra/missing wires!

Next, let’s try to convince ourselves that (B1) makes sense by using the intuition of numbers moving along wires. In the left hand side, there are two dangling wires on which we can input numbers x and y, and they are first added, then copied. Like so:

bialglhs

Now let’s do the same thing for the right hand side: first we copy the two numbers, we swap two copies in the middle, then we add. Like this:

bialgrhs

Since we are making no assumptions about what actual numbers x and y represent, our demonstration shows that the behaviour of the left hand and the right hand sides of (B1) is the same: we can’t detect any difference between them if we cover up the internal contents of the circuits and only experiment with them by providing various inputs and observing outputs.

I want to say one more thing about (B1) — its bizarro version is itself! If we reflect the left hand side and switch the colours, we get the left hand side again. Same with the right hand side. By the way, here’s a useful exercise for you to get comfortable with the algebra of diagrams: write down a formula that constructs the right hand side of (B1) using the operations ⊕ and ; on the basic generators, identity and twist. Remember how we did it for Crema di Mascarpone?

 

What happens when adding meets discard, copy’s sidekick? That scenario gives rise to the second key equation.

adddiscard

The rationale for (B2) is easy: in the left hand side, we add our two inputs and then throw away the answer. But, clearly, the observable behaviour is the same if we just went ahead and threw away the two inputs without adding: the behaviour in both cases consists of taking any two numbers and not producing any results.

Next up is an equation that concerns the situation when zero meets copying.

zerocopy

Remember that the behaviour of the zero generator is simply to output the number 0 on its result wire. If I copy 0, I get two 0s. That’s what (B3) is saying.

Take another look at (B2) and (B3). Can you see how they are related? One is the bizarro version of the other. Graphical linear algebra is full of bizarro situations like this: we already noticed that the equations for adding and copying are bizarro versions of each other. In fact, this is part of a general fact of graphical linear algebra:

If an equation holds, then its bizarro version holds too.

This will be true for the entire run of our story; even as we consider additional generators, diagrams and equations. It’s a useful thing to keep in mind because sometimes it will save us half the work, and sometimes it will allow us to see connections between seemingly quite different phenomena.


 

This is probably a good point to take a short break for a discussion about our methodology. Some of you, probably including most of the non-mathematicians, may be confused as to why we keep identifying certain equations and giving them names.

I hinted a few of episodes ago that we want to gradually get away from thinking about “numbers moving on wires”. Instead, we will use the key equations that we have identified so far as axioms; that is, basic postulates that we simply accept to be true.

Much of our attention will be on examining what kind of things these axioms allow us to prove, and what they do not prove, using only the rules of working with diagrams together with basic logical reasoning. Just as when we proved the upside down version of (Unit). Historically, this kind of methodology—that is, identifying basic properties and seeing how far they get you—is tried and true: the tradition goes back at least to 300 BC with Euclid and his elements.

In this episode we identify four equations; we have seen three of them so far, (B1), (B2) and (B3). Together with the three equations for adding and the three for copying, this system of ten axioms will suffice for the next few episodes. As we will discover, it is already a very interesting system, even if it may not look like much at this point! For example, we will use diagrams to do some basic arithmetic in the next episode.


 

The final axiom is a bit strange.

bone

First, the left hand side is what happens when you compose zero with discard. It’s a strange kind of diagram that we have not seen before, because there are no dangling wires at all. But what is the right hand side? I didn’t forget to draw it: it is also a diagram, the diagram with nothing in it. A blank piece of paper.

We will sometimes call the left hand side of (B4) by the extremely technical name “bone“. I guess that I probably don’t need to explain the etymology. The name was invented by my coauthor Fabio—at one point the whiteboard in my office was covered with them and we needed to call them something!

So (B4) tells us that, in any graphical proof, whenever we come across a bone we can simply erase it. That’s because, if I output zero and promptly discard it, it’s like doing nothing at all.


 

Mathematicians call structures that satisfy equations (B1) through to (B4) with different names, typically bimonoids or bialgebras. We will use the term bialgebra. It’s not a great name, but it will do.

There is one more thing to be said. Maybe you remember that, in ordinary arithmetic, products distribute over additions: so the following is true for any numbers a, b and c:

a(b+c) = ab + ac

In the equation above, when evaluating the left hand side, the addition comes first followed by a multiplication. Instead, in the right hand side, the order is reversed: we multiply first and add later. So the distributivity property reversed the order in which we perform operations.

Our new equations from this episode can also be understood as reversing the order of the operations. For example, take another look at (B1). In the left hand side, the addition comes first followed by a copy, while in the right hand side it is the copying that comes first, followed by additions.

In fact, it is really the case the equations (B1) through to (B4) can also be considered as a distributive law in a formal mathematical sense. I will not go into the details of this now, because it is not strictly necessary to understand in order for us to make progress in the story. For the interested, it is all explained in a wonderful paper by Steve Lack. Steve is one of the extremely brilliant category theorists that I have been lucky enough to meet and learn from: he supervised my honours project at Sydney Uni, back when I was finishing my undergraduate degree.

Continue reading with Episode 9 – Natural numbers, diagrammatically

Advertisements

2 thoughts on “8. When Adding met Copying…

  1. Typo: “it’s the bizarro version is itself”.
    I assume you meant “its bizarro version is itself” or “it’s the bizarro version of itself”?

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s