First an announcement. Graphical linear algebra is going on the road!

I will give a tutorial on it at QPL 2015 in Oxford on 13-14 July.

I will also talk about it at the ICTAC summer school, in Cali, Colombia, on 25-27 October. I’ve never been to Colombia before, I’m super excited!

---

In this episode we are going to discuss the recipe for Crema di Mascarpone, one of my favourite desserts. We are also going to write our first proof, using only diagrams.

First, a recap of where we are in the story.

We have been talking about addition and zero, and how to construct diagrams. Addition and zero are two generators (basic diagrams) of our system:

We can make more complicated diagrams with two operations: direct sum (⊕) and composition (;). Direct sum stacks its arguments one on top of the other, and composition connects wires.

When constructing diagrams we also often use two special diagrams, called identity and twist.

Identity and twist are the basic plumbing of diagrams; they give us some flexibility, allowing us to connect the right “studs” to the right “holes”, to use a Lego analogy.

Let’s leave addition and zero for now, and move on to sweeter things.

---

Crema di Mascarpone is the delicious, silky smooth filling that you find inside Tiramisù. It’s also great as topping on Pandoro or Panettone, the two famous Italian christmas cakes. A word of warning to those planning to visit Italy: it may be the case that it’s a minor misdemeanour to put Crema di Mascarpone on a Panettone; I believe that it’s only officially sanctioned on a Pandoro. Nevertheless, this crime is of course nowhere near as severe of drinking a cappuccino after 11am or (the horror!) putting pineapple on a pizza. Apologies to my Italian readers for making you even consider the possibility of such an atrocity.

You will need two eggs, 200g of Mascarpone and 2 tablespoons of white sugar. We will represent the recipe for Crema di Mascarpone as a diagram, but since making food is much more complicated than addition, we first need to introduce a whole load of generators:

Of all of these, we should stop and examine the first—the Crack Egg generator—because it’s the only one we have seen so far where there is more than one result wire. We will meet a generator like this in the next episode. It’s a very important part of the story of graphical linear algebra.

The rules for direct sum and composition are a little bit more complicated than the ones we have already seen, because it is not enough to know just the number of dangling wires but also what the wires represent. We don’t want to confuse our ingredients! We would also need a few different versions of identity and twist to give us the plumbing for all the different kinds of wires: for instance we need the identity wire for mascarpone, and a twist where a yolk and white wires cross over, and so on. Since this blog is not really about recipes, we are going to cheat slightly and not going to bother writing down the more complicated versions of the rules, nor the more complicated plumbing. Let’s keep things simple.

Here is the recipe for Crema di Mascarpone.

We could write a formula for this, even if it’s not as nice to look at as the diagram.

(C ⊕ C ⊕ id₂) ; (id ⊕ tw ⊕ id₃) ; (W ⊕ B ⊕ id) ; (id ⊕ S) ; F

In the formula C stands for “Crack Egg”, W for “Whisk”, B for “Beat”, S for “Stir” and F for “Fold”. We also use id to stand for identity and tw for twist. Finally,  id₂ and id₃ stand for, respectively, the direct sum of two and three identity wires.

It’s maybe not clear how to pass from the diagram to the formula. So let’s develop a technique for this. First, I choose appropriate points to divide the diagram into vertical slices.

If I name the slices V, W, X, Y and Z, then it’s clear that the whole diagram can be constructed by evaluating

V ; W ; X ; Y ; Z

It is important to keep in mind that the composition operation on diagrams is associative:  whenever I have diagrams X, Y and Z that can be composed, then (X ; Y) ; Z is the same diagram as X ; (Y ; Z). For this reason it makes sense not to write parentheses in the equation above — the order in which we perform the compositions does not matter!

The final vertical slice, Z, is easy: it’s just the Fold generator. We now divide the remaining vertical slices horizontally, so that each of the resulting rectangles is either a generator or basic plumbing. Like so:

Now, scanning down each slice we can write down an expression for each of V, W and so on. For example

V = C ⊕ C ⊕ id ⊕ id.

We again left out parentheses, because—you guessed it!—direct sum is associative.

That’s how we can get to the long formula for the recipe: first subdivide into vertical slices, then subdivide those slices horizontally. Now, while Crema di Mascarpone is amazingly delicious, the real point of this section is to describe how to work with diagrams. There are four rules to remember. The first is:

Rule 1: Always draw diagrams so that it’s possible to subdivide them, obtaining a formula that uses the generators, plumbing, ⊕ and ;.

So here’s an example of something that we are not allowed to draw at the moment.

Let’s examine why. It would make sense to draw the vertical bars around addition, since we know it’s a generator. We get something like this.

So far so good: the middle slice is identity direct summed with addition. But what are we to make of the left and the right slices? It looks like we would need some plumbing that looks like

 and

The first one has no dangling wires on the left and two on the right, and the second two on the left and none on the right. But we don’t have any advanced plumbing like this, we only have a supply of identities and twists in our toolbox. Something has gone wrong — by Rule 1 this is not a diagram that we are allowed to draw.

The diagram that we disowned is actually quite interesting: the result of the addition is “fed back” as the first argument. Feedback is extremely important in computer science, control theory and engineering. It has launched a thousand papers. Graphical linear algebra has some interesting things to say about feedback too, as we will see.

Rule 2: Wires don’t tangle 

This rule tells us about how the plumbing in our diagrams behaves.  For example, we consider the following two diagrams to be equal.

There is an intuitive way to think about the equality above: imagine starting with the left hand side and pulling on the wires until they are tight. Since we are in the beautiful world of graphical linear algebra and not in the hideous world of the back of your TV, the wires do not get tangled. We end up with the diagram on the right hand side.

Here’s a more complicated example, but the same intuitive principle applies (although, in the underlying mathematics, the equations hold for different reasons).

The thing to keep in mind is that in wiring, i.e. the kinds of diagrams that we can construct with just the identity and the twist, what matters is which dangling positions on the left are connected to which dangling positions on the right. By the way, we can understand these kinds of wiring diagrams as encoding permutations, and—long story short—composing wiring diagrams works the same way as composing permutations.

Rule 3: Generators can slide along wires

There are two things to say here. Let’s start by thinking about the part of the recipe where we crack the eggs.

It makes sense to think about the horizontal axis of the diagram as time, so in essence, our recipe says that we should crack our two eggs simultaneously. Fortunately,  graphical linear algebra understands that you only have two hands. The following diagram is considered to be equal.

Here we cracked the first egg before we cracked the second. But also the following diagram is considered equal.

So it does not matter in which order we crack the eggs, as one would reasonably expect when preparing desserts. We can move between the three diagrams by sliding the generators along wires. This kind of action is always allowed, and it won’t change the meaning of our diagrams.

There is a second way in which generators can slide along wires, and it involves the twist. Suppose that, in some hypothetical dessert, we had to whisk some egg whites, but we also had to crack an egg for some other purposes. Also, it turned out that our ingredients were in the wrong order on the table, so we had to rearrange them.

In this situation, we can slide the Crack Egg generator along the wires to the right, past the twists, like so.

So, essentially, we can wait with the cracking of the egg until we finish the whisking, and just rearrange the egg and the whisked egg white on our ingredient table beforehand. Look at the two diagrams above and imagine the Crack Egg generator sliding from its position in the first diagram to its position in the second diagram. Simple!

Rule 4: Diagrams are compositional

Compositionality is something that many mathematicians take for granted. They sometimes they call this principle “substituting equals for equals”. What it means is that in an algebraic structure, once you know that two things are equal then you can swap them as you like in larger formulas, and the two formulas will still evaluate to equal results. For example, we can calculate that 1 + 3 = 2 + 2. Next, we can use this fact to not actually do the following calculation. We can be lazy, because we already know it’s going to be true!

(1 + 3) × 4134221=(2 + 2) × 4134221

We can obtain the right hand side from the left hand side by replacing 1 + 3 with something equal to it, 2 + 2. Compositionality says that the results will be equal.

The real world is, alas, much more complicated. Let’s discuss one example that’s close to my heart. When I was a teenager, computers doubled their speed every 18 months or so. This is because engineers were able to fit in many more, smaller transistors on chips, and this made it possible to increase the clock speed; the pulse that determines how fast computers make their calculations. Engineers are still able to make smaller transistors and put more of them on chips. Unfortunately, because of the underlying physics, they are not able to ramp up the clock speed any more. When computer companies sell you their machines now, they no longer focus on the clock speed so much; instead they tell you about how many cores their computers feature. Dual core, quad core, hex core, etc. The more cores the better. If you have a mobile phone then you are probably carrying several hundred cores in your pocket. So what is a core exactly?

A core is a processing unit. Having two cores typically means that your computer is able to do two things at the same time. If you have hex core then it should be able to do 16 things at the same time. Sounds great, right? Well, the problem is that nobody told the programmers how exactly to take advantage of extra parallelism. Writing concurrent programs is hard.

I think that one reason why concurrency is hard is because the tools that we give to the programmers are not compositional. Two programs might have the same behaviour if we think of them as running on one core, but they may act very differently if ran in parallel with another program. This is because of things called race conditions. It is really, really difficult to understand non-compositional things.

Of course, I’m over simplifying things in this brief explanation; concurrent programming is a huge area. But maybe I will come back to this topic at some point in the blog. I have some work in progress, based on the ideas of graphical linear algebra, that may be helpful.

Let’s get back on topic: the good news is that diagrams are compositional. If we know that two diagrams are equal then we can substitute them for each other in more complicated diagrams. This is one of the principles of  diagrammatic reasoning: writing proofs with diagrams. We will work through an example below.

 

The four rules cover all you need to know about diagrams in order to do graphical linear algebra. You may be wondering why does it all work; where do the rules come from? The answer is that the diagrams, which many people call string diagrams, are actually a very nice notation for elements of mathematical structures called PROPs (which stands for product and permutation categories, somehow). PROPs are, in turn, examples of mathematical structures called symmetric monoidal categories. It is not important, at the moment, to delve into their arcane lore. Instead, keeping rules 1-4 in mind, we can start having fun.

---

Let’s use this knowledge to write our first completely diagrammatic proof.

Remember that, so far, we have identified three equations.

Now we are going to prove that the following is true.

We will use only our chosen three equations, and the principles of diagrams that we discussed earlier. Since it’s our first proof, we will go slowly; eventually, when you are more comfortable with the ideas, we will be able to speed up quite a bit.

Let’s start with the left hand side. First, draw a red square around the addition generator. The red square is not really a part of the diagram, it’s only there to help us to focus. The addition generator is the left hand side of (Comm), so using the principle of compositionality, we can replace everything inside the red square with the contents of the right hand side of (Comm).

Now, we can slide the zero generator across the twist. Here we are using the principle of sliding generators along wires.

But this is just the left hand side of (Unit). So we can replace it with its right hand side.

 And we’re done; we have followed a chain of reasoning that took us from the left hand side to the right hand side of the equation that we were interested in. Actually, it turns out that we didn’t need to use (Assoc) at all in the proof.

Cool, huh?

Continue reading with Episode 7 – Copying, Discarding and The Slogan.