27. Linear Relations

In the last two episodes we focussed on fairly simple diagrams in IH: those with just one dangling wire on each end. In this episode we expand our horizons and consider arbitrary diagrams. It’s time to return to linear algebra. We will also revisit division by zero from a different, but equivalent, point of view.

We’ve known since Episode 10 how to handle matrices diagrammatically, and since our expanded graphical language can handle fractions, we can put the two together and draw matrices of fractions. The algebra works as expected: if we restrict our attention to these matrices, composition is matrix multiplication, and the monoidal product of two matrices is their direct sum. Here’s a reminder of how to draw, say, the following matrix

$exmatfrac$

But we can do much stranger things. Since we have the mirror image operation † in our arsenal, we can consider matrices going backwards. We don’t have any traditional notation for this: how could you write a matrix that “goes backwards”? But here’s an example in the language of diagrams, if

Then we have can draw the diagram for B going from right to left.

Matrices and backwards matrices are not the full story because diagrams can get more complicated. In general, diagrams from m to k will be quite strange beasts: imagine a zig-zag of matrices going back and forth. It’s as if we took our Lego and got confused about what are the studs and what are the holes. Everything goes.

Let’s clear up the mystery. We know that the sub theories B and H are isomorphic to, respectively, the props Mat of matrices of natural numbers and Mat_Zof integer matrices. Knowing this helped us to understand the diagrams in those theories, and what they were capable of expressing.

So, without further ado, it’s time to meet the linear algebraic prop LinRel that hides behind the equations of graphical linear algebra. Coincidently it’s my favourite category, so please forgive me if I sound a bit too much like a fanboy in the following. Before we start, we need some notation: in the following, the bold letter Q stands for the set of fractions, aka the rational numbers.

The arrows from m to n in LinRel are linear relations from Q^m to Qⁿ. Roughly speaking, LinRel is what happens when you combine matrices and relations. The result is truly delightful; it is much more than the sum of its parts. You will see what I mean.

Before I explain what linear relations are in more detail, let me first say that it’s a huge mystery that the concept of linear relation does not seem to be particularly standard or well-known: there is not even a wikipedia page at the time of writing this episode! Since there’s an informative wikipedia page about, say, Cletus from the Simpsons, this is a bit offensive. Maybe it’s because of a human preference for functional thinking, at the expense of relations? We discussed that a bit in Episode 20.

So what is a linear relation exactly?

First, a linear relation of type Q^m ⇸ Qⁿ is a relation, so a subset of the cartesian product Q^m × Qⁿ. De-jargonifying, this means that it’s a collection of pairs, with each consisting of an m-tuple and an n-tuple of fractions. For example, the linear relation for the addition generator—which we have already discussed informally in Episode 22—is the relation of type Q²⇸ Q that consists of all pairs

where r and s are fractions. We have thus finally demystified what the enigmatic universe of numbers Num is: for now Num = Q, our numbers are fractions.

We still need to account for the word linear in linear relations. Said succinctly, to be linear, a relation R: Q^m ⇸ Qⁿ must be a linear subspace of Q^m × Qⁿ, considered as a Q vector space. If you don’t know what those words means, let me explain.

First, R must contain the pair of zero columns.

R must also satisfy two additional properties.The first is that it must be closed under pointwise addition. This scary sounding condition is actually very simple: if R contains pairs

and

then it also must contain the pair obtained by summing the individual numbers:

It takes a lot of space to write all those columns, so let’s introduce a common notational shorthand: we will write a for the a-column (or column vector), b for the b-column and so forth. When we write a+c we mean that a and c are columns of the same size and a+c consists of a₁+c₁, a₂+c₂ and so on until a_m+c_m. So—using our new shorthand notation—for R to be closed under pointwise addition, whenever (a, b) and (c, d) are both in R then also

(a, c) + (b, d) := (a+c, b+d)

must be in R.

The second property of linear relations is that they must be closed under scalar multiplication. This means that whenever

is in R then also

must be a member, where k is any fraction. We can also do say with the shorthand notation: given a vector a and fraction k, we will write ka for the vector with entries ka₁, ka₂, …, ka_m. So, being closed under scalar multiplication simply means that if a is in, then ka must also be in.

Composition in LinRel works just like it does in Rel, so composing R: Q^m ⇸ Qⁿ and S: Qⁿ ⇸ Q^p gives R;S : Q^m ⇸ Q^p with elements (x, z) precisely those for which we can find a y such that (x, y) is in R and (y, z) is in S.

I claim that LinRel is a prop. To be sure, we need to do some things that may not be immediately obvious:

verify that the identity relation is a linear relation,
check that composing two linear relations results in a linear relation, and
say what the symmetries are and make sure that they work as expected.

The first one is easy, try it!

For point 2, we need to show that if R: Q^m ⇸ Qⁿ and S: Qⁿ ⇸ Q^p are linear relations then so is R;S.

Let’s prove closure under pointwise addition: suppose that (x₁, z₁) and (x₂, z₂) are in R;S. We need to show that (x₁+x₂, z₁+z₂) is also in R;S. Using the definition of relational composition, there exist y₁, y₂ such that (x₁, y₁) and (x₂, y₂) are both in R and (y₁, z₁) and (y₂, z₂) both in S. Since R and S are linear relations, they are both closed under pointwise addition, so we can conclude that (x1+x₂, y₁+y₂) is in R and (y₁+y₂, z₁+z₂) is in S. It thus follows that (x1+x₂, z₁+z₂) is indeed in R;S. I’ll leave you to check that it’s closed under scalar multiplication, the argument is very similar.

For point 3, for now I’ll just tell you what the relation for the twist 2 → 2 is and hope that it gives you the general idea. The twist in LinRel is the smallest linear relation that contains the elements

Since we need to close under addition and scalar multiplication, elements in this relation will look like

where k and l are fractions.

We have already discussed the relational semantics of the generators in Episodes 22, 23 and 24 and verified that the equations make sense, relationally speaking. It is not difficult to check that each of the relations is linear. Long story short, this assignment of relations to generators defines a homomorphism of props

IH → LinRel.

As we will eventually prove, this is an isomorphism; it is both full and faithful.

The proof of IH ≅ LinRel is quite a bit more involved than the proof B ≅ Mat and H ≅ Mat_Z. We will eventually go through it in detail—apart from following our principle of not handwaving, the proof is quite informative. But for now, LinRel and its diagrammatic presentation IH are perfect playgrounds for linear algebra and that’s what we will concentrate on over the next few episodes.

In the last episode we discussed how (1, 1) diagrams allowed us to divide by zero. By looking at the corresponding situation in LinRel, we can shed some more light on this curiosity. So let’s take a look at linear relations Q ⇸ Q: since IH ≅ LinRel these are in 1-1 correspondence with (1, 1) diagrams. We can plot linear relations of this type using conventional graphical notation, thinking of the domain as the horizontal x axis and the codomain as the vertical y axis.

Since every linear relation must contain the pair that consists of zero columns, every plot will contain the point (0,0). In fact, the singleton {(0,0)} is itself a linear relation: clearly it satisfies the two required properties. Here’s its plot.

The diagram for this linear relation is

which we dubbed ⊥ in the last episode. Next up, the entire set Q×Q is a linear relation. Here we colour the entire plane red. Sorry for the eye burn.

The corresponding diagram is

which we were calling ⊤ last time. These two linear relations give some justification for the names ⊥ (bottom) and ⊤ (top), since the former is—set theoretically speaking—the smallest linear relation of this type, and the latter is the largest.

The other linear relations are all lines through the origin. So, for example, the plot for the identity diagram

is the line with slope 1.

All the fractions arise like this. For example, the line for the fraction –¹/₂, diagrammatically

is the line with slope –¹/₂

You get the idea for the other fractions.

There are two lines that represent interesting corner cases. The first is the line for 0

which is the line with zero slope, that is, the x-axis.

Finally, there’s the line with “infinite” slope, the y-axis.

which is the plot for

that we called ∞ in the last episode.

If we think relationally, then the operations x+y, x×y and ¹/_x are all easy to define, and are total on the set of linear relations Q ⇸ Q. Multiplication is simply relational composition, and ¹/_x is the opposite relation x^†. Finally, addition can be defined set theoretically as

x + y = { (a, c) | there exist (a, b1) in x and (a, b2) in y such that b1+b2 = c }.

The above definition simply mimics the sum operation, as we have been doing with diagrams. So we could reconstruct the addition and multiplication tables from the last episode by working directly with linear relations.

Identifying numbers with lines through the origin is an old idea. It is one way to understand projective arithmetic. What is not so well-known is that we can define the arithmetic operations directly on the underlying linear relations, and moreover, throwing ⊤ and ⊥ into the mix makes the operations defined everywhere, with no need for dividebyzerophobia. If you have seen this done somewhere else, please let me know!

Here’s one very cool fact about LinRel, and it concerns the mirror image symmetry †. Remember that if R is a relation then R^† is the opposite relation: (b, a) is in R^† exactly when (a, b) is in R. In the last episode we saw that for any (1,1) diagram d we have

d;d^†;d = d.

It turns out that this works for arbitrary linear relations. Thus R^† is always the weak inverse of R. This is something that will be very useful for us in the future. Let’s prove it.

Suppose that D is some linear relation. Since D;D^†;D and D are both sets (of pairs), to show that they are equal it’s enough to show that each is a subset of the other. It is easy to show that every element of D must be an element of D;D^†;D, since, taking (a,b) in D, the chain of elements (a,b), (b,a), and (a,b) proves that (a,b) is in D;D^†;D.

We just need to show that the opposite inclusion also holds. So suppose that (a, d) is in D;D^†;D. By definition, there are b, c such that (a, b) is in D, (b, c) is in D^† and (c, d) is in D. And since (b, c) is in D^†, (c, b) is in D.

Now, using the fact that D is a linear relation that contains (a, b), (c, b) and (c, d), we have that

(a, b)-(c, b)+(c, d) = (a–c+c, b–b+d) = (a, d)

is in D.

The fact that D;D^†;D is not larger than D is one thing that’s special about linear relations: it is not true for ordinary relations! For example, think about what happens to this relation 2 ⇸ 2:

Today is Boxing Day, so this is a Christmas special episode of the blog. The next one will probably arrive in January, so let me take this opportunity to wish everyone a fantastic

Continue reading with Episode 28 – Subspaces, diagrammatically.

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:

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

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:

The zero generator

also has a relational interpretation. Its type is {★} ⇸ Num. The reason for this is that Num⁰ 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 Num⁰ is a singleton is related to a fact memorised by everyone in high school: we all know that k⁰ = 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:

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

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:The 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:

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

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

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:

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:

So, the relation consists of pairs

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

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

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

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

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.

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

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.

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!

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

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.

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:

Let’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 (★,★).

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.

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.

14. Homomorphisms of PROPs

In the last two episodes we have established that our diagrams, constructed from the four generators, and subject to the equations below, are the arrows of a PROP B.

We have also talked about another PROP, Mat, that has as its arrows matrices of natural numbers.

In maths, it is often the case that to understand something properly you need to think about how it relates to other things. Our current task is an example of this, since we need to establish exactly what we mean when we say that diagrams and matrices “are the same thing”. This brings us to the notion of homomorphism —a generic jargon word that means “structure-preserving translation”—of PROPs.

So suppose that X and Y are PROPs. It’s useful to colour them so that we can keep track of what’s going on in which world, the red world of X and the hot pink world of Y. A homomorphism F from X to Y (written F : X → Y) is a function (a translation) that

for any arrow A : m → n in X produces an arrow FA : m → n in Y.

Notice that the domain and the codomain must be preserved by the translation: both A in X and FA in Y have domain m and codomain n.

But PROPs come with a lot of structure, and homomorphisms have to preserve all of it. For example, for any other arrow A’ in X, it must be the case that

F(A ⊕ A’) = FA ⊕ FA’ ①

The above equation says that if I translate the monoidal product of A and A’ taken in X then I get the same thing as if I had translated A and A’ separately and took the monoidal product in Y. Remember that monoidal product is defined differently in different PROPs: for example in B it is the stacking diagrams on top of each other, while in Mat it is forming a certain matrix.

Similarly, if we can compose A with A’ (which we can do exactly when the domain of A’ is n) then:

F(A ; A’) = FA ; FA’ ②

Again this says that translating A composed with A’ in X should be the same thing as translating the individual components separately and doing the composition in Y. Recall that in B composition is simply connecting dangling wires together, while in Mat it is matrix multiplication.

Moreover, as we have seen, every PROP has special identity arrows, one for each natural number m. These form a part of the structure of PROPs and so must also be preserved:

Fid_m = id_m ③

Finally, for any natural numbers m, n, there are the special “wire-crossing” arrows σ_m,n that also must be preserved:

Fσ_m,n = σ_m,n ④

That takes care of all the structure. So if we can find a translation F that satisfies ①, ②, ③ and ④, we have got ourselves a homomorphism of PROPs.

Back in Episode 11 we started to define a translation called θ. There we listed the matrix that is assigned to each generator:

But to have a homomorphism from B to Mat, we need to give a rule θ that translates every diagram with m dangling wires on the left and n dangling wires on the right to an n×m matrix. It turns out that because of the way in which B is constructed, the above four rules tell us everything we need in order to define a homomorphism from B to Mat. All the other stuff is predetermined.

This is because B is special: it has diagrams as arrows, and every diagram is constructed from the four generators, identity and twist. That means that there is only one way we can extend the translation above so that it defines a homomorphism. We do not even need to say how to translate the identity and twist diagrams, since they are part of the PROP structure: they are respectively id₁ and σ_1,1 of the PROP B. And ③ together with ④ tell us that they must be translated to id₁ and σ_1,1 in the PROP Mat:

Next, since we already know how to translate the most basic diagrams, rules ① and ② give us the recursive rules for translating more complex diagrams. We already worked through an example.

Because of the middle-four interchange and the identity laws it does not matter how we subdivide the diagram: since Mat is also a PROP, it also satisfies these laws. Moreover, the procedure is well-defined, since, as we have seen in the last two episodes, diagrammatic reasoning amounts to using equations that hold in any PROP, and the additional equations of B that can be shown to hold in Mat: we did the work of checking this back in Episode 11.

That alleviates all of our fears from when we started discussing the translation. All that hard work of going through PROP lore is finally paying off! If you are not that impressed then don’t worry, we will have the opportunity to see many other examples of PROPs in action further on in the story.

Stepping back a bit from what we’ve been doing above, there is one thing worth mentioning. Back when we were talking about how natural numbers can be seen as special kinds of diagrams, I mentioned that they are free: two diagrams are considered to be equal exactly when we can prove it using diagrammatic reasoning and our equations.

In fact, the PROP of diagrams is the free PROP on the four generators and ten equations. This is the “special” nature of B that I alluded to before, and the thing that makes PROP homomorphism from B pretty easy to define: we just need to show where the generators go and make sure that the equations of B are also true in the codomain PROP.

How can we tell, in general, that two different languages can express exactly the same concepts?

One way is to construct a perfect translation. To understand what this could mean, we could start by thinking what non-perfect translations look like. For example, let’s pretend that I claim to be qualified English to French translator—which I’m definitely not, by the way—and you give me two English words to translate, say serendipity and dog. Suppose that both of the times I say chien. Then my translation cannot be very good, even if you don’t know what the word chien means.

The reason is that you could ask me to translate chien back to English. This would force me to choose one of serendipity or dog, or maybe something else entirely. If I say dog then you know that something went wrong: you asked me to translate serendipity to French, I said chien, then you asked me to translate back and I said dog.

serendipity → chien → dog

Since you know that serendipity and dog are two different concepts, something clearly got lost in the translation. Even If I said serendipity, you would still be able to catch me out, since then the translation chain would be:

dog → chien → serendipity

The moral of this story is that we would expect that a reasonable translator would not translate two different concepts in English to the same word in French.

The mathematical jargon adjective for such reasonable translations is injective. And because PROPs come from category theory, they inherit their own special jargon: a homomorphism F : X → Y is said to be faithful when,

given two different arrows A ≠ A’ : m → n in X, we have FA ≠ FA’: m → n in Y.

Another way a translation, say from Klingon to English, could be less than satisfactory is if there are some words in English for which a word in Klingon does not exist. This is likely because Klingon only has about 3000 words: so some English words like “serendipity” do not have a Klingon equivalent. But don’t quote me on that, I’m not an expert in Klingon.

The common mathematical jargon for a translation that hits every word in the target language is surjective, and in the world of PROPs the word is full. So a PROP homomorphism F: X → Y is said to be full when

for all arrows B: m → n in Y, there exists an arrow A: m → n in X such that FA = B.

It turns out that a homomorphism F: X → Y that is both full and faithful is perfect in the the following sense: there exists a translation G: Y → X that “reverses” F. G is called the inverse of F and satisfies the following two properties:

for all arrows A: m → n in X, GFA = A
for all arrows B: m → n in Y, FGB = B

So if I start with some A in X, translate it to Y and translate back again I end up where I started. Same if I start with some B in Y. There is a special word for homomorphisms that have inverses: they are called isomorphisms. A translation that has an inverse is about as perfect as one could expect.

The PROP homomorphism θ: B → Mat is full and faithful and thus an isomorphism of PROPs. We will discuss why this is the case in the next episode.

The upshot of θ being an isomorphism is that the diagrams of B and matrices of natural numbers are really two languages that talk about the same thing. In particular, we should be able to translate concepts from one language to the other.

Here’s one example: we saw that the bizarro operation on diagrams, where we reflect a diagram and interchange white and black, is quite useful: it has already saved us quite a bit of work with proofs, since a proof of any claim can always be translated to a bizarro proof of the bizarro claim. So what does it mean to consider the bizarro version of a matrix: that is, if I start with a diagram D and its bizarro version D^bizarro, what is the relationship between matrices θD and θD^bizarro?

Well, it turns out that the equivalent concept for matrices is called transpose. If I give you an m×n matrix A (n columns, m rows) then its transpose A^T is an n×m matrix (m columns, n rows) that has, as its entry at the ith row and jth column, the entry at the jth row and the ith column of A. Intuitively speaking, the rows of A become the columns of A^T. Here’s an example, if I let A be the matrix

then its transpose is the matrix

What about a concept that maybe you’ve come across in the language of matrices? For example, linear algebra courses usually go on about special kinds of matrices called row vectors and column vectors. A row vectors is simply a matrix with exactly one row, and a column vector is a matrix with exactly one column.

So the concept of a row vector, translated to the world of diagrams, is a diagram with exactly one dangling wire on the right. Here’s an example:

Similarly, a column vector translates to a diagram with exactly one dangling wire on the left. Like so:

Some of you, especially those who are already familiar with matrices, are probably asking yourselves what is the point of having two languages to describe the same thing. It all seems to be a bit redundant, since you already know about the concept of a matrix of natural numbers. Please hang in there for now: I hope to convince you that looking at the world through the prism of diagrams gives you a different, sometimes truly surprising perspective.

Continue reading with Episode 15 – Matrices, diagrammatically

13. PROPs (Part 2) and Permutations

First, a brief reminder of where we are at the moment. We are going through the various parts of mathematical structures called PROPs (product and permutation categories). As we go through each new piece, we pause to check that both our diagrams as well as matrices of natural numbers satisfy the conditions. The goal is to conclude that both diagrams and matrices organise themselves as the arrows of two PROPs. The translation from diagrams to matrices from two episodes ago will turn out to be an isomorphism of PROPs, which means that for all intents and purposes we can regard diagrams and matrices as different languages to talk about the same thing.

In the last episode we went through some of the structure of PROPs, but the story is not yet complete. Actually, so far we have talked only about the “PRO” in PROPs. The final P stands for permutation, and permutations are the main topic for today.

Let’s start by introducing another convenient syntactic sugar for diagrams. It will be useful for discussing permutations, but it will also come in handy for us later on. This one is pretty simple: whenever we write a natural number k above a wire, it simply means the diagram that results from stacking k copies of the identity on top of one another. Of course, when k = 1 there is no need to write any number at all: the wire with 1 above it is just a wire.

In the last episode we have seen that this diagram serves as the identity on k in the world of diagrams. There’s one thing to keep in mind about this sugar: it’s important not to confuse it with our standard intuition of numbers travelling along wires. In the case where we feed numbers into a circuit we will always be careful to write them below the wires.

PROPs come with some structure that allows us to permute—that is, jumble up—any collection of wires. Given natural numbers m, n, every PROP has a special arrow called

σ_m,n : m + n → n + m.

The symbol σ is the Greek lowercase letter sigma. Now of course, m + n = n + m, so the domain and the codomain of every such σ is actually equal. The reason why I wrote it in two different ways is that the intuition about σ_m,n is that it swaps the m and n.

In diagrams, we already know σ_1,1 by its nickname, the twist.

In general, we are going to need a gadget that looks like the following, for any two natural numbers m and n.

The intuition for σ_m,n is clear: it should be the diagram consisting of m wires crossing over n wires. Let’s draw it for a particular case; say for m = 2 and n = 3.

The key observation is that we can zoom in, as illustrated below, and apply the Crema di Mascarpone procedure to obtain a formula that only uses identities and twists. For example:

We could now ask whether we could do something along these lines for any m and n. First, we can draw a diagram where the m wires cross over the n wires, then… it seems like it should be possible to zoom in far enough and then subdivide the diagram, obtaining an expression that only uses identities and twists.

In any PROP, the family of σs have to satisfy a few equations. For now let’s examine the following two:

σ_k,m+n = (σ_k,m ⊕ id_n) ; (id_m ⊕ σ_k,n) (†)

σ_k+m,n = (id_k ⊕ σ_m,n) ; (σ_k,n ⊕ idm) (‡)

together with special cases σ_k,0 = id_k and σ_0,k = id_k for all k. These equations tell us how to construct the family of σs using just twist and identity; in fact, they already almost look like a recursive definition. We will use them to define the gadget σ_m,n recursively as another syntactic sugar. Again, the sugar is something that will be useful to have in our pantry as we do more graphical linear algebra.

The equations may look mysterious, but when we draw them as diagrams, they become pretty straightforward. Starting with (†) (the symbol is called dagger):

Thus, to cross k wires over m+n wires is the same as first crossing k over m wires, then over n wires. The second equation (‡) (double dagger) is similarly intuitive:

Now let’s translate the equations to a bona fide recursive definition.

We start with the case where there is just one wire that crosses over n wires: that is, we will define σ_1,n for any n using recursion. The base case n = 0 is simple, it is just the identity: a wire that crosses over zero wires is simply a wire. Now, if I know how to construct the diagram for a wire crossing over k wires then I can construct a diagram for a wire crossing over k + 1. Indeed, the recursive case is

which is a special case of equation (†). That gives us σ_1,n for any n.

Now, for σ_m,n, we let σ_0,n be the identity on n (n copies of the identity, stacked). The corner case is σ_0,0 which is just the empty diagram.

Since we already know how to construct σ_1,n for any n, the general recursive case can be built as follows:

where, in order to cross k + 1 wires over n we use σ_1,n and recurse. This definition is a special case of (‡). That takes care of all possible ms and ns. And because of the recursive way we constructed the family σ_m,n, it is not difficult to prove, using induction, that (†) and (‡) hold.

Thus, in the world of diagrams, we have our family of σs, as required of all PROPs. But PROPs need this family to satisfy two additional conditions, because they are supposed to be symmetric monoidal categories. The first of these is:

σ_m,n ; σ_n,m = id_m+n ①

Diagrammatically, this means:

We could go ahead and prove this, using induction, and use diagrammatic reasoning to tighten individual wires, but we will not bother as it’s already pretty obvious just by looking at the diagram: it is not difficult to imagine tightening all the wires in the left hand side at the same time until we get to the right hand side: our wires don’t tangle.

The other requirement is called naturality and it says that, categorically speaking, the σs define a natural transformation. In any PROP, naturality can be summarised by stating that the following diagram commutes for any natural numbers m, n, m’, n’ and arrows A: m → m’, B: n → n’:

Let me explain what the word “commutes” means. If you look at the diagram above, there are two paths we can follow, starting at the top left point of the diagram. We can either go right then down, or down then right. The fact that the diagram commutes means that the two paths are equal. As an equation:

(A ⊕ B) ; σ_m’,n’ = σ_m,n ; (B ⊕ A) ②

Now lets translate this to the world of diagrams. Equation ② says is that for any diagram A with m dangling wires on the left and m’ wires on the right, and any diagram B with n wires on the left and n’ on the right, the following two diagrams ought to be equal:

The above can be considered as a more general version of the rule that we call sliding along wires, since we can get from the left hand side to the right hand side of the diagram above by sliding A and B across the crossing of the wires on the right. But we don’t really need to make any additional assumptions about diagrammatic reasoning: it can be proved from the two principles of diagrammatic reasoning that we already identified back in Episode 6: 1) generators can slide along wires, 2) wires do not tangle.

The proof is a little bit more complicated than the kind of inductions that we have seen so far since we have to deal not only with the fact that n, m, n’, m’ are arbitrary numbers, but also that A and B are arbitrary diagrams! The important insight is that we know how any diagram is constructed: by starting with generators, identities and twists and using the two operations ⊕ and ; of the algebra of diagrams. Given the fact that any diagram whatsoever can be constructed like this, the trick is to use a slight generalisation of induction, called structural induction, that is very popular in programming language theory. The base cases would be to show that it holds when A and B are actually generators, twist or identity. Then the inductive steps would consider how to construct more complicated instances of A and B with our two diagram operations ⊕ and ;. But again let’s not bother with this for now as it is a bit tedious — but do let me know in the comments if you’re interested in seeing this done in more detail!

We have argued that diagrammatic reasoning can be used to show that our diagrams satisfy all the conditions expected of PROPs. In fact, diagrammatic reasoning characterises these conditions: any fact that can be shown by just stretching or tightening of wires or sliding diagrams along wires can be equivalently shown by using only the various equations required by the definition of PROPs.

We have already seen in the last episode how just the action of drawing the diagram can save the writing of equations. I hope that it’s becoming apparent in this episode that our diagrammatic syntax, together with diagrammatic reasoning, is a real equational bureaucracy monster slayer.

So far in this episode we have only talked about the world of diagrams, but we also need to understand what the σs are in the world of matrices. Let’s summarise: σ_m,n is a matrix that, in general, looks like this:

where I_m and I_n are identity matrices of size, respectively, m and n, and the 0s are shorthand for filling in all the available spaces in the grid with 0s. For example, σ_2,3 is the following matrix:

It is not difficult to show that (†), (‡), ① and ② are true the world of matrices, but it is a bit boring, so we will skip it. You are welcome to go ahead and check it as an exercise! By the way, there is a special name for these kinds of matrices and their products in matrix algebra, they are called permutation matrices.

We have now finally ticked all the required checkboxes that were necessary to establish that both diagrams and matrices are the arrows of PROPs.

Lets call the PROP that has as its arrows diagrams constructed from the copy, discard, add and unit generators, subject to our ten equations with the name B, which stands for bimonoids or bialgebras. And we will call the PROP that has as its arrows matrices of natural numbers with the name Mat. Given our now more complete understanding of diagrams and matrices, in the next episode we will return to our translation θ from diagrams to matrices.

Permutations are popular topic in maths, especially in combinatorics and group theory: everyone likes to think about shuffling cards. If you already know about a little bit about permutations then you may find this aside useful; otherwise feel free to skip it; it does not really contribute to our story.

Permutations on a finite set of size n are the elements of a mathematical structure called the symmetric group S_n. The group action is composition of permutations.

Maybe you already have an inkling that, in any PROP, the arrows from n to n include all the permutations. Indeed, any permutation can be constructed, using the algebra of PROPs from the identity on 1 and the twist (σ_1,1). One could ask if the arrows satisfy all the equations that are expected of permutations.

The answer is yes, and it can be easily checked since symmetric groups have a well-known presentation. We just need to check that the following two equations hold in any PROP:

The first equation is clearly an instance of ①. The second follows from the naturality condition ②. To see why this is the case, we can draw a box around the first twist in the left hand side and the last twist in the right hand side:

The remaining structure in each side of the equation is, by (‡), σ_2,1. But now I can write the two sides as a diagram that looks as follows

and this is clearly an instance of ②, so it must commute. Neat, right?

Continue reading with Episode 14 – Homomorphisms of PROPs.

12. Monoidal Categories and PROPs (Part 1)

So far we have not discussed categories in any depth. The reason for this is that I wanted to give you a feel for working with diagrams, for which we do not really need any deeper theory. I hope that I managed to convince you that diagrammatic reasoning is very intuitive: stretching, tightening and sliding along wires are all quite easy to visualise and think about. String diagrams are a user friendly notation, and the operations on them are also quite intuitive, at least if you ever played with Lego. These intuitive aspects are extremely important.

Similarly, it is perfectly usual to do sophisticated calculations using natural numbers without knowing the ins and outs of the Peano axioms, the definition of semirings, or the maths of initial algebras. In fact, maybe thinking too hard about the set theoretical definition of the natural numbers or the Church encoding would actually make calculation more difficult!

My point is that the natural numbers are best understood, at least at first, as an intuitive concept: adding and multiplying are operations that have many applications in the world around us. Similarly it’s possible, or even preferable, to work with diagrams and use them to perform calculations without thinking too much about the underlying mathematical baggage.

I have also, however, promised not to handwave. So I feel that I owe it to you to present a proper mathematical argument that supports the claim that the diagrams built from the copy, discard, add and zero generators are really the same things as matrices of natural numbers. And I do not know how to do this rigorously without using category theory. We have already started the proof of this claim in the last episode, by showing how to translate diagrams to matrices, but we need to understand what this translation amounts to exactly and why it makes sense.

In any case, while it is possible to do graphical linear algebra without any category theory, doing so misses out on a lot of fun. For example, knowing about PROPs, we will eventually have a nice explanation about where the ten equations that we have so far come from. Some techniques of graphical linear algebra rely on understanding this provenance. We will also have a tighter grip on the finer points of diagrammatic reasoning, which is useful since we will be using it more and more as we get deeper into the story. Finally, having the category theory around also makes it easier to convince people who already know about linear algebra that diagrams are relevant to their interests. Indeed, category theory gives us the tools to relate the two worlds: the world of diagrams and the world of “traditional notation”.

A PROP is a special kind of monoidal category. I suspect that the definition was kicking around for a while, but the first reference that I know of is in a 1965 paper by Saunders Mac Lane, one of the two founders of category theory.

We need to get through a checklist all of the requirements of PROPs, so please bear with me while we work our way through this taxonomy. Thankfully, we already have two examples that we can refer to: diagrams and matrices.

Maybe you have heard that categories consist of objects and arrows. As their objects, PROPs have the natural numbers: what this really means is that the things that we care about, diagrams and matrices, are indexed by pairs of natural numbers. As we have seen:

Any diagram has a number of dangling wires on the left and a number of dangling wires on the right.
Any matrix has a number of columns and a number of rows.

We need a neutral word that can describe both diagrams and matrices, so that we don’t get confused. That generic word from category theory is arrow. And we will see that both diagrams and matrices are indeed the arrows of two different (albeit extremely closely related) PROPs.

The traditional notation for arrows unfortunately looks very much like function notation, but it is important to keep in mind that arrows do not need to be anything like functions.

So an arrow in a PROP has two associated natural numbers, the domain and the codomain. For a diagram, the domain is the number of dangling wires on the left and the codomain is the number of dangling wires on the right. In a matrix, the number of columns is the domain and the number of rows is the codomain.

Because PROPs are monoidal categories, there is an operation called the monoidal product. It takes two arrows as arguments and produces an arrow as a result. The rule is as follows:

As we have seen, direct sum of diagrams, and of matrices fits into this general form. So direct sum, in both cases, is an example of monoidal product. Monoidal product in PROPs is typically not commutative, but it is required to be associative:

(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) ①

This is one of the ways in which PROPs, which are strict monoidal categories, are simpler than ordinary monoidal categories, which come with much more bureaucracy: in vanilla monoidal categories, the monoidal product is only assumed to be associative “up-to isomorphism”, which means that the equals symbol in ① is replaced with something weaker. This brings a whole load of extra baggage that we can simply ignore in PROPs. Maybe you heard about Homotopy Type Theory (HoTT), which has become quite fashionable in recent years: HoTT is all about getting to grips with the general idea of “replacing equality with something weaker”.

And so far so good for diagrams and matrices: direct sum passes the test for associativity in both of our worlds. Monoidal product also has an identity. It is a special arrow called id₀ : 0 → 0. It satisfies the property that, for any other arrow A, we have

id₀⊕ A = A ⊕ id₀ = A

In the world of diagrams, the identity for the monoidal product is the empty diagram, which we have already seen in the right hand side of the bone equation (B4). In the world of matrices, it is the matrix () : 0 → 0.

The second operation in PROPs is the basic operation in category theory called composition. It works as follows.

Composition is required to be associative:

(C ; D) ; E = C ; (D ; E) ②

We have seen how to compose diagrams, and their composition is associative. In the world of matrices, we have seen that matrix multiplication plays the role of composition, and we have already seen that it is associative in the last episode.

In PROPs, for every natural number m, there is a special arrow id_m: m → m. We have already seen id₀ which is the special arrow in the case m = 0. Identities serve a special role with regards to composition: composing any arrow with an identity at either end has no effect. So, for any arrow A: m → n, we have that

id_m; A = A = A ; id_n ③

Can you think of what serves as identities in the world of diagrams? We have met id₁ which is the single wire diagram that we have already been referring to as identity. What about id_m for m>1? Well, we can construct this by stacking several identity wires on top of each other with the aid of direct sum. In fact, this follows from a requirement of PROPs that

id_k+m = id_k ⊕ id_m ④

Taking stacked wires as the identities means that equation ③ is inherent in diagrams: just by drawing diagrams we are implicitly assuming that it holds. This is because we can use the Crema di Mascarpone procedure to cut up the same diagram in different ways. For example, taking just the copy generator, we can get three different expressions for it just by slicing in the right places:

So you see, one diagram, two equations. There is more of this kind of thing to come.

In the world of matrices, the identity on m is simply the m×m matrix that has 1s on the main diagonal and 0s everywhere else. Conveniently, this notion is commonly known as the identity matrix, and identity matrices satisfy ③.

Now for an interesting way in which composition and the monoidal product are related. Suppose that we have diagrams A, B, C and D that connect to each other as illustrated below.

There are two ways we could reasonably slice this diagram apart to get a formula. The first one is how we went about it for Crema di Mascarpone, make a vertical slice first

and read off the formula (A ⊕ C) ; (B ⊕ D).

The other way is to make a horizontal slice first

and read off the formula (A ; B) ⊕ (C ; D). For simplicity I assumed that all four diagrams have a single dangling wire on each end, but the concept generalises for any numbers of dangling wires: the fact is that in any PROP, given A, B, C, D that can be composed in the way that I’ve illustrated, the following equation, sometimes called the middle four interchange, holds.

(A ⊕ C) ; (B ⊕ D) = (A ; B) ⊕ (C ; D) ⑤

Note that, again, just by drawing diagrams we are assuming that this property holds since the diagrams in each case are exactly the same, only the slicing technique changes. By the way, this is what I was alluding to last time when I mentioned that the same diagram can be cut up in different ways. In the world of matrices, showing that the middle four interchange holds is a matter of performing a simple calculation; we will skip the details.

Equations ③ and ⑤ illustrate the point I made all the way back in episode 2: a (large enough) diagram can tell a thousand formulas. The mere action of drawing a diagram sweeps away swathes of equational bureaucracy! This is one of the reasons why diagrams are such a great notation.

There is one final property of PROPs that I wanted to explain in this episode, and it concerns one instance of sliding along wires in diagrammatic reasoning. Let’s stay with diagrams A, B to illustrate it, but again the concept is more general since it generalises to any numbers of dangling wires in a straightforward way. Remember that since we can slide diagrams along wires, we consider the three diagrams below to be equal:

This yields the equations

(A ⊕ id ) ; (id ⊕ B) = A ⊕ B = (id ⊕ B); (A ⊕ id)

that are required to hold in any PROP and intuitively say that whenever A and B do not interconnect then they can be interleaved in arbitrary order. Actually, it turns out that the equations above are a consequence of the middle four interchange equation ⑤ and the way that identities work with composition ③. Can you see why? Think about what happens when we let some of the four diagrams in ⑤ equal the identity.

As we have seen back in Episode 6, the equality of the three diagrams illustrated above is part of what we have described as “sliding along wires”; one of the rules of diagrammatic reasoning. Next time we will complete our discussion of PROPs, explaining the mathematics behind the remainder of diagrammatic reasoning, and in the episode after that we will finish—for the time being— talking about the translation from diagrams to matrices. This detour is taking longer than I planned, and I’m itching to tell you about more graphical linear algebra.

An aside for people who already know the basic concepts of categories: properties ④ and ⑤ that relate the monoidal product to composition amount to saying that ⊕ is not just any old way of taking two arrows and obtaining a new arrow: it is actually a functor, a mapping from the cartesian product of the category with itself back to itself. Equation ④ says that the mapping preserves identities and ⑤ that it preserves composition.

By the way, if you are interested in a good book for learning the basic concepts of category theory, I highly recommend Categories and Computer Science by Bob Walters. It is the book that first introduced me to categories. Bob was a professor at Sydney Uni when I was an undergraduate there and I did a vacation scholarship with him at the end of my second year of uni. I kept in touch with Bob over the years and—thinking about it now—he influenced my thought process more than any other person. Sadly, he died earlier this year and I will really miss our discussions.

Continue reading with Episode 13 – PROPs (Part 2) and Permutations

11. From Diagrams to Matrices

It’s becoming traditional to start each episode with a plug, and this week’s one is for an event that takes place 22-27 June, 2015 in Nijmegen in the Netherlands. It’s the joint meeting of Mathematical Foundations of Programming Semantics (MFPS XXXI) and the 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). I’m co-chairing CALCO this year with Larry Moss, and we have some really fantastic papers and invited talks. Come along!

One of our invited speakers, Chris Heunen from the Quantum Group in Oxford, will talk about Frobenius monoids, which are a big part of graphical linear algebra, as we will see in a few episodes. I also have a paper at MFPS with my PhD student Apiwat Chantawibul in which we use the diagrammatic language of graphical linear algebra to study some extremely interesting and useful concepts of graph theory; I will probably write about this here at some point in the future.

Last time I—somewhat vaguely—claimed that there is a 1-1 correspondence between diagrams in our theory and matrices with natural number entries. In this episode we will start to discuss this correspondence properly.

First, though, we need to understand what matrices are exactly. And here I would argue that the definition given in Wikipedia (as of today, May 23, 2015) is not only overlong and boring, which is to be expected of our beloved internet creation, but actually wrong.

I quote:

“A matrix is a rectangular array of numbers or other mathematical objects”.

Well that tells part of the story, but ignores some hairy corner cases.

Our working definition is as follows. A matrix with natural number entries is an entity that consists of three things together: a natural number m that tells us how many columns there are, another natural number n that tells us how many rows there are and a n×m grid of natural numbers. We will write it as follows:

Here are three small examples.

Maybe you’re thinking that there is some redundancy here: I mean, if I give you a rectangular array can’t you just count the numbers of columns and rows to obtain the other two numbers? What’s the point of keeping this extra information around?

This is where the corner cases come in. Consider the following three matrices.

We are not good at drawing 15×0, 0×3 and 0×0 grids of natural numbers because they all end up looking a bit… empty. On the other hand, all three are usually used to represent different things, so it does not feel right to identify them. That’s why it’s useful to keep those two extra numbers around: they help us get around this small, yet important deficiency in the standard notation. There are other, more subtle deficiencies in matrix notation, and we will get around to exposing them in later episodes.

We define two operations on matrices, and they are quite similar to the operations on diagrams. The first is direct sum. Its action is governed by the rule

where the grid A₁ ⊕ A₂ is defined as follows:

Note that I’m being slightly careless with the notation; in the diagram above the two 0s, reading from left to right, are respectively m₁×n₂ and m₂×n₁ grids that have 0s as all of their entries.

So, for instance,

and

Notice that, just as is the case for diagrams, direct sum is not commutative. It is associative though, given any matrices A, B, C the bracketing does not matter:

(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

Here’s an example that illustrates why we need to keep the extra information about numbers of columns and rows:

So you see, that even though the number grid is empty in () : 3 → 0, you can certainly feel it when you direct sum it with something!

Here’s one final example.

Next we have the operation of composition, which is usually known by the name matrix multiplication.

Just as in diagrams, we can’t just multiply any two arbitrary matrices: you see that for composition to work, the number of rows of A has to be equal to the number of columns of B. Note also that the notational convention for the product is to write A after B even though we think of A as coming first, i.e. we wrote BA for the number grid part of the composition. If A and B were diagrams we would have written A ; B. It’s not a big deal, just a little notational quirk to keep in mind.

Now since BA is a grid of numbers, we need a way of figuring out its entries are. The formula that governs this is:

where (BA)_ij refers to the entry in the ith row and the jth column. Don’t worry about memorising the formula, we have computers to do the calculations for us.

Using this formula it’s not too difficult to prove that matrix multiplication is associative, that is, for all matrices A, B, C that can be composed, we have

C(BA) = (CB)A

And, again just as we’ve seen in diagrams, matrix multiplication is not commutative. First of all, for most pairs of matrices it only makes sense to multiply them in one way, since the rows and columns have to match up properly. For square matrices, where the numbers of columns and rows are the same, we can find simple counterexamples to commutativity. Here is one:

Are you missing diagrams already? I am. Let’s face it, grids of numbers are pretty dull. So just to scratch my itch, here are the two computations above, but illustrated as compositions of our diagrams.

How do we prove that our diagrams and matrices are interchangeable? To do so, we define a formal translation from diagrams to matrices. Since we will refer to it quite a bit, we may as well give it a name, say the Greek letter theta (θ). We can start defining θ by giving matrices for each of our generators. There are only four, so this is not very much work!

Next, we can use the observation that all of our diagrams can be subdivided so that we can write them as expressions that feature only the basic generators, identity and twist composed together with the two operations of diagrams ⊕ and ;. We demonstrated the procedure of how to get from a diagram to an expression for Crema di Mascarpone. Using this insight, the matrix for a composite diagram can be obtained by performing matrix operations on the matrices that are the translations of its subcomponents.

The above definition is saying that in order to work out the matrix for the composition of diagrams A and B, first work out the matrices for A and B separately, and then multiply them. We can say something similar for direct sum.

Note that this is an example of a recursive definition: we use θ in the right hand side of the two definitions above. The reason why it makes sense is that eventually we get down to the generators, identity or twist, which are the base cases of the recursion. So the only thing that remains to explain is how to deal with the wiring:

A brief aside. A few episodes ago I claimed that it is hard to talk about copying using “traditional mathematical notation”. Since we just translated the copy generator into something that most scientists would recognise, haven’t I just contradicted myself?

I would argue that this translation does not really do copy justice: it has some hidden “baggage” in the sense that matrix algebra relies on how copy interacts with addition through equations (B1) through to (B4). It is sometimes useful to keep copy isolated, because it does not necessarily interact in the same way with other generators that may look quite similar to addition. I know that all of this sounds a bit mysterious, but bear with me. We will come back to this point later.

Let’s go through an example to get a feeling for how θ works: we will translate the right hand side of equation (B1) to a matrix. First, we decompose the diagram into an expression that features only the basic components.

Next we use the definition of θ for expressions to turn the right hand side of the above equation into an expression on matrices.

In the first two steps we simply used the defining equations for θ, first on composition then on direct sum. In the third step we used the definitions of θ on basic components, then we direct summed the matrices, and finally we computed the matrix product, using Wolfram Alpha.

So, summing up, we have worked out that:

But does this way of defining θ even make sense? The problem is that we have many different ways of writing a diagram as an expression. As we have seen in the last few episodes, sometimes we consider two diagrams that look quite different to be the same thing. So what if one way of writing it one way and applying θ gives you some matrix A, but writing a different expression for it and applying θ gives you a different matrix B? Then θ would not be well-defined, we could not be sure what the matrix that corresponds to any particular diagram really is.

But don’t worry, it’s all fine. There are three ways of obtaining different expressions for a diagram.

We can subdivide the diagram in a different way. More on this in the next episode.
We can use diagrammatic reasoning to stretch or tighten wires, or slide generators along wires.
We can use our ten equations to replace components of diagrams.

We can tackle point 3. easily enough. We just need to check that, for each equation in our system, the matrices that we get for the left hand side and the right hand side are the same. For example, to complete the job for (B1), in which we have already worked out the matrix for the right hand side, we just need to consider the left hand side.

So applying θ to the two sides of (B1) gives the same matrix. The same can be said for all of the other equations in our system: go ahead and check a few!

That leaves points 1. and 2. — can we be sure that diagrammatic reasoning will not change the matrix? And what if we choose to subdivide a diagram in a different way?

The reason why these issues do not cause problems is that both diagrams and matrices organise themselves as arrows of two different symmetric monoidal categories. And θ is not just any old translation, it is a functor, a way of getting from one category to another. Moreover, the two symmetric monoidal categories are both of a special kind: they are PROPs, which are symmetric monoidal categories with extra properties that makes them an ideal fit for graphical linear algebra.

We have lots of cool graphical linear algebra to do, and so I don’t want this series to descend into a discussion of the finer points of category theory . As I said back in episode 2, the amount of category theory that we really need is fairly modest. At this point we need just enough in order to understand points 1. and 2.

Moreover, we still need to understand in what way θ captures the close relationship between diagrams and matrices. We will show that θ is an isomorphism of categories, and more than that, an isomorphism of PROPs. Isomorphisms are quite rare in category theory, where a weaker notion called equivalence of categories is much more common. It goes to show just how closely our diagrams and matrices of natural numbers are related!

Continue reading with Episode 12 – Monoidal Categories and PROPs (Part 1)

Aside

2. Methodology, Handwaving, and Diagrams

Since my first post, several people have asked about my plans for this blog. So let’s start with a few words about methodology.

I will try—as much as possible—to keep the material accessible to people who have never seen, or even heard of linear algebra. At the same time, I expect that many (most?) readers will be at least somewhat acquainted with the concepts. So for those in the know, I will sometimes include information about how what they already know can be understood in the different style that we will use. But if you’re an expert and think that the formula for multiplying matrices is so basic and natural that no one in their right mind should be writing blogs on the subject, then I suspect I will have a hard time trying to win you over.

I’m an academic. In my job I teach, do research, and write papers. I love teaching and doing research. Writing scientific papers is not so great. Writing, at least for me, requires massive amounts of work. A typical 15 page conference paper is, at minimum, a solid 60+ hours of work, not including the actual research work that comes beforehand. The amount of work is not linear in the length, and so twice the length means much more than twice the work. I once spent a solid 3 months working on a 60 page paper. After all the blood, sweat and tears, what happens next is somewhat depressing: the paper goes through (anonymous) peer review, and if you’re lucky it gets accepted with some lukewarm reviews. Sometimes reviewers are really petty and mean. It’s not pleasant.

If the internet has taught us anything, it’s that

humans + anonymity = unpleasantness.

History, moreover, has taught us time and time again that

humans + power = unpleasantness.

Anonymous peer-review combines humans, some anonymity, and a little bit of power. The results are not surprising.

The next step is for your paper to get published, and maybe presented at a scientific meeting, in front of an audience of anywhere between 10 and 100 people, 50% of whom will spend the entire presentation reading emails. Again, not a great feeling. Then, after your paper gets published, sometimes your colleagues will cite you. My most cited paper has around 150 citations. That’s considered to be not bad, by the way.

So, to get back on topic, I want to have fun writing this blog. Don’t expect anything like scientific writing. It will be totally unprofessional. I want to write about Makélélé and magic Lego. Sometimes I will present my opinions in somewhat “Australian” style. I spent my childhood in Poland, but I grew up in Australia. In this blog I will be channelling my Australian-ness. Australians, like the Scots, tend to call a spade a spade. The English aren’t usually so direct. Englishness is all about subtlety and insinuation. Over the centuries, they have refined their public discourse and developed high-level, advanced techniques like (damning with) faint praise.

It’s funny that famous, English, public-school educated, all round posh Oxbridge professors are often regarded in their international scientific communities as the perfect gentlemen. Some of them actually are, of course. Some are often as rude as their extreme Englishness can possibly allow them, it’s just that their worst insults are misunderstood as compliments. They get to have their cake and eat it too — this makes me really jealous. Let me explain for the non-English aware: say you ask their opinion about your work and they reply “I think that your work is very interesting”. Sounds like a compliment, right? Wrong. It’s a serious put-down, they hate it. Think about it: “very interesting” is not a particularly strong compliment; it can be understood in several ways. At least we regularly thrash them in the cricket.

As you can see, things will sometimes get a bit personal here. The people that know me, know what I mean. Some of them, even some English people, still talk to me.

I promise one thing: I will try to be serious about the maths. I mean, I will try very hard not to handwave. Handwaving is when you kind of sound like you know what you’re talking about, but you’re really only speculating, using vague analogies, etc. When people do this, they naturally tend to wave their hands a lot, hence the name. So, while I will give lots of intuition, all intuition will eventually be explained. It will be hard, because I really, really love handwaving. Please let me know if you notice any, and tell me to stop. I will also try to cite related work and acknowledge sources, and not make far-fetched claims about what the maths can be used for. But that’s about as professional as you’re going to get.

In our discussions we will use many diagrams. Hence the “graphical” in graphical linear algebra. Diagrams have got a lot of bad press in science and mathematics over the years, for being somehow less formal, less rigorous, less “mathsy” than formulas. Unfortunately, it is true that diagrams are often used by people who like to wave their hands a lot. When sceptical captains of science see a diagram, they recoil slightly. They look around the room. They shake their head knowingly at the most important person in the room. I mean, why not just write an honest-to-goodness formula? You know, like $e^{\pi i} = -1$ . Formulas will sometimes appear in this blog, mainly to appease the grizzled cognoscenti.

The point is that—if used carefully—diagrams can be extremely useful, rigorous and totally 100% no-hands-waved formal. As honest as the best formulas, but much more concise, and much easier to read. Even better than rectangles of numbers, which—as I have said—are very important. We all know the cliché “a picture tells a thousand words”. We will see how, quite literally, a diagram can tell a thousand formulas.

There’s a branch of mathematics called category theory, invented by Saunders Mac Lane and Samuel Eilenberg in the 1940s, where diagrams have been used since the very beginning. Category theorists are comfortable with diagrams, and we will use category theory to do graphical linear algebra. A lot of great category theory comes from Australia, by the way.

Maybe you already know something about category theory. If not, I’ll let you in on a little sociological curiosity: there’s a lot of animosity towards category theory out there in science-land. I’ve had several colleagues discreetly tell me things like “I’ve tried category theory once, but never again” or “One of my friends used it once and it was a total disaster. It’s just all too abstract. I like to do concrete things.” I normally manage to keep a straight face. But I wonder how many carpenters have ever said “I tried using an electric drill once, but it was a complete disaster. The thing made a hole in completely the wrong place. And the hole was the wrong size. Never again.” I mean, don’t get me wrong, it’s totally fine to be a carpenter and not use electric drills.

It is true that many category theorists like to explore the deep end of the pool. Sometimes the pool is not quite deep enough and they go away and imagine something deeper. Typically we end up with several, possibly non-equivalent, infinitely deep pools. It’s cool, but it makes my head spin.

So don’t panic. I’m not really a category theorist, although I’m lucky enough to have met and learned from some truly great category theorists. You can trust me. We will mostly stay in the shallow end, and do very concrete things, like adding. In fact, adding is the subject of the very next episode.

Continue reading with Episode 3: Adding (Part 1) and Mr Fibonacci.

Graphical Linear Algebra

Menu

Category Archives: Category theory