We spent the last few episodes assembling our toolbox of equations. The game in graphical linear algebra is as follows: we consider two diagrams to be equal exactly when we can use the equations and graphical reasoning to prove it. If we cannot, we will consider them to be different. A mathematician would say that we are considering the free system on this set of equations.

If this idea is not clear,  then imagine playing a board game: the things that you are allowed to do are only those that are specified in the rules. If something is not in the rules, then it is not allowed. Board game rulebooks typically do not include every possible way of how one could break the rules. People are way too creative at cheating; no wonder that law is such a complicated mess! In a similar way, we are usually not going to explicitly say when two diagrams are different: we consider them to be different if it is not possible to show, using the rules, that they are equal.

Anyway, here’s a convenient cheat sheet for the equations we have met so far, to save unnecessary clicking between episodes.

---

 

 

I hinted back in Episode 3 that graphical linear algebra has something to say about counting. That’s the plan for today.  We will focus our attention on a very particular class of diagrams: those with exactly one dangling wire on the left and on the right. As it turns out, such diagrams are very closely related to natural numbers: that is, non-negative integers 0, 1, 2 and so on. For example it makes a lot of sense to associate the following diagrams with the corresponding numbers:

Remember the intuition about numbers travelling on wires? Well, associating numbers to diagrams is compatible with all that. For example, let’s consider sending a number x on the left dangling wire of the diagram that we are associating with the number 3.

The output is x + x + x = 3x. So, whatever the input, the diagram acts by multiplying it by 3. If you look at the diagrams for 0, 1 and 2, the idea is the same.

There is also a nice graphical intuition at play here: the number associated to a diagram is  the number of paths from the dangling point on the left to the dangling point on the right. So, in the diagram to 0 there are no paths from left to right, in 2 there are two different paths, and so on. This graphical intuition is very important and we will come back to it again soon.

Although this is all quite cute, the correspondence between numbers and diagrams is not merely skin deep. As we will discover, the algebra of diagrams allows us to perform the basic operations of arithmetic: addition and multiplication. Thus, while our slogan so far is that linear algebra is all about what happens when adding and copying meet, we can actually be more extreme: even the basic idea of natural numbers is explained by adding and copying!

---

 

We start by defining a translation from numbers to diagrams, which will be useful for us as a syntactic sugar. The expression “syntactic sugar” is probably quite familiar to you if you are a programmer: it means a construction that is useful to have as part of your language, but that does not actually add anything new: the language does not become any more expressive. Syntactic sugar can always be translated away to phrases that we had before, but having it may be convenient for several reasons. This is exactly the case that we have before us.

Our syntactic sugar is a family of special diagram components, one for each natural number. We start with our good friend 0. We use the special := notation to indicate that we are actually defining the thing to the left in terms of things that we already know about.

The reason for the name (base) is that we will define the syntactic sugar recursively, and the definition above is the base case of the recursion. The recursive case is:

Maybe you have not seen the use of recursion before. It is something that many first year Computer Science undergraduates are very scared of; I know from personal experience! The reason is that, if you look at (rec), we are trying to define something (the left hand side), but we are using it again in the definition (the right hand side). This looks circular and weird — but don’t worry, it makes sense, and is not very difficult. The best way to get the hang of it is to experiment with some concrete examples.

So let’s understand the first few numbers, starting with 1.

We use (rec) to get the first equality, then (base), then (Unit), then (Counit). So the diagram that corresponds to 1 is simply the identity.

Let’s do 3 now.

We use (rec), then (rec) again, and then we use our knowledge of the diagram  for 1, which as we have discovered above, is simply the identity.

---

 

It is important not to confuse the syntactic sugar for a natural number with a number travelling on the wire, as per our standard intuition. In fact, the sugar acts by multiplying its input by the number it represents, like so:

Let’s prove this!

But how does one prove something about all natural numbers?  We could start showing that it holds for individual cases, say n = 13, but that would not be very satisfactory. Maybe we got lucky with that particular choice, maybe it’s not true for n = 12?

The trick is to use mathematical induction: if we show that the above is true for n = 0 (the base case) and whenever it is true for n = k then it is also true for n = k + 1 (the inductive step), then we can conclude that it holds for all natural numbers n. It’s kind of a bootstrapping process: how do I know that it’s true for n = 13492? Well, we know it’s true for n = 0. But because it’s true for n = 0, it must be true for n = 1, using the inductive step. But because it’s true for n = 1, it must be true for n = 2. And so on, until eventually we get to n = 13492.

We start with the base case, n = 0. Using (base) we need to check the behaviour of the following circuit.

 

And indeed, according to our established intuition about how the generators behave, a number x arrives on the left, is discarded, and a 0 is produced by the zero generator. But 0 = 0x, so the effect of the 0 sugar is to multiply its input by 0, as we are claiming.

Now let’s assume that this works as advertised for n = k and try to show that it holds for n = k + 1. The assumption is called the inductive hypothesis. For the k + 1 circuit, we use its defining equation (rec) and consider the behaviour of the following.

 

Again a number x arrives on the left, and is copied. The first copy is fed into the k sugar, which, by the inductive hypothesis, multiplies its input by k, resulting in the output kx. The second copy of x is untouched, and so kx and x are fed into addition, resulting in the output kx + x. But kx + x = (k + 1)x, which is what we want!

This concludes the induction and the proof. We will do many more induction proofs, so if all this is new to you then you will have plenty of examples to get comfortable!

---

 

We now move to the meat of this episode: showing how the algebra of diagrams can be used to express some familiar operations on numbers. Let’s start with adding: we willl prove that the following equality holds for all natural numbers m, n:

One way of understanding (sum) is that it show that ordinary, old-fashioned addition of natural numbers is already a part of our language: we can understand it with the basic operations of graphical linear algebra.

 

So let’s start by looking at what happens when n = 0, the base case of the induction.

We first use (base), then (Unit) and (Counit) together in a single step. Finally m = m + 0, as we all know.  This shows that, no matter what m is, (sum) is true when n = 0.

Next, let’s look at the inductive step: remember, we can assume that what we want to prove, (sum), is true whenever n = k, and simply show that it is true for n = k + 1. Here we go:

First we use (rec), then (Assoc), then (CoAssoc). Next comes the use of our inductive hypothesis, and finally we use (rec) again. This completes the induction, and the proof of (sum).

 

We are going to prove a few more things in this episode. The first is the following useful equation, which holds for any number m.

Again the proof is by induction. For m = 0, it suffices to use (B4), the bone equation.

Next the inductive step.

First we use (rec), then (B2), then the inductive hypothesis, and finally (Counit). That’s (discarding) proved then.

 

The next property that we need is the following.

Let’s do the induction. For the base case, we have:

The proof of the inductive step is long, but not very complicated. We just need to apply (CoAssoc) a number of times and (CoComm) once to get the right alignment of the copies on the left. In the third step we use the inductive hypothesis.  It is not super important to follow all the steps, so feel free to skip it.

If you did go through the proof carefully, maybe you spotted the one step where I cheated.  It was the point at which I used (sliding) — remember that we are allowed to slide generators along wires. The reason why I was being slightly naughty is that the diagram for the number k is not, strictly speaking, a generator: it is syntactic sugar. However, because it is built from basic generators, one can show without too much difficulties that it can also be slid. In fact, it is not too difficult to show that any diagram whatsoever can be slid along wires.

 

Here’s a claim which I will not prove, because you have seen enough of examples of how to prove things by induction to be able to do it yourself. The claim is this:

For any natural number n, the bizarro version of the diagram for n is itself.

This is a useful fact to note, because we immediately get the following two things for free:

The reason why we know that (zero) and (adding) hold is because they are the bizarro versions of (discarding) and (copying). We can simply repeat each step in the proofs of (discarding) and (copying), but in the bizarro world.

We should spend a little bit of time discussing (adding), because it seems contrary to our expectation that the adding generator ought to be adding things. So why isn’t m + m = 2m? Well, let’s come back to our intuition of numbers on wires. Consider the left hand side of (adding), it has two dangling wires on the left on which we can send two numbers x and y. Next, remember from the introduction that the diagram for m acts by multiplying its input by m. Then the two outputs are fed into the adding operation, like so:

What about the right hand side? Performing the individual operations gives us the following behaviour:

But multiplication distributes over addition, so m(x + y) = mx + my; the behaviour of the two sides of (adding) is the same. We have, of course, already seen how to add natural numbers in graphical linear algebra, and it is handled by a combination of the adding and copying generators, as demonstrated in (sum).

 

 

There is just one more thing to prove in this episode, and it concerns another famous operation  on natural numbers.

Just like (sum) can be understood as saying that ordinary addition of natural numbers can expressed using graphical linear algebra, (multiplication) is saying that ordinary multiplication of natural numbers is just composition.

To prove it—you guessed it!—we will use induction.  The base case is the following, and we have the chance to use the (zero) property.

Next comes the inductive step, where we use both (adding) and (sum).

This completes the proof of (multiplication).

---

We have shown how natural numbers, addition and multiplication arise in graphical linear algebra. But there is one point about which you may be nervous: we have shown all kinds of useful properties, but what if actually 2 = 3 in graphical linear algebra? What if every number is equal to every other number? Maybe there is some crazy graphical proof that shows this? And how do we show that one cannot prove something, anyway? This is where the graphical intuition about counting paths comes in, and we will come back to this in the next episode.

Another question that you may have is the following. We have shown that all natural numbers can be understood as certain diagrams with one dangling wire on the left and one on the right. But are there some diagrams of this kind which are not equal to one that represents a natural number? In fact, this is not the case: this class of diagrams is in 1-1 correspondence with the natural numbers: every diagram with one dangling wire on the left and right is equal to one that comes from a number. There are several ways to show this, and we will explore some of these techniques in subsequent episodes.

Continue reading with Episode 10 – Paths and Matrices