30. The essence of graphical linear algebra

Before we get started, I have an annoucement. Recently I have been contacted by Vincent Verheyen, a Belgian polyglot mathematician/developer who generously offered to translate the blog into several languages, starting with Dutch and French, but also German, Spanish, and even Chinese (with the help of his girlfriend Chung-Yi Lan). The first few episodes are already available and more will follow in the coming weeks. Vincent has set up his website in a way that makes external contributions possible, and the translations themselves are published under the Attribution-ShareAlike 4.0 International licence. So, if you are interested, please do get involved! I’m really honoured that Vincent has invested his time and energy in this effort, and it’s wonderful that the material will find a wider readership: at the moment, about 80% of the hits on the blog are from English speaking countries.


 

There is a new video series on YouTube by 3Blue1Brown called “Essence of linear algebra”. It’s slick and gives visual intuitions for matrices, spaces, determinants etc. It makes the important point that intuitions are not emphasised enough: too often linear algebra is presented as a series of definitions and algorithms to memorise. But you’ll notice that the diagrams there are quite different to the kinds of diagrams on this blog. The series has inspired me to think about the “essence of graphical linear algebra”. The story on this blog has been divided into bite size chunks, and as a result, it is sometimes difficult to see the wood for the trees. So in this episode we take a step back and look at the big picture. But first, let’s start with a little history.

Early 20th century mathematicians and logicians were a nervous lot, facing an existential crisis and a severe inferiority complex. Engineers were building astonishing machines that transformed the world in the timespan of a single generation. Their work was made possible by physicists who made breakthroughs in understanding the basic laws that govern the physical world, and by chemists who charted interactions between different types of molecules and compounds. For all of these pursuits there was an external reality to point to, a sanity check. A plane that did not fly was not much use; the design was improved or thrown out. Similarly, theories in the physical sciences could be put to the test in the lab. They were falsifiable: if experimental data did not fit the theory, it was the theory that was thrown out, not the real world.

Mathematicians, instead, worked with abstract systems, applying various levels of rigour. Instead of an external reality, they could point to the beauty and intellectual depth of their intuitions and results.  An added bonus was—as the physicist Eugene Wigner put it in 1960—the unreasonable effectiveness of mathematics in the natural sciences. Therefore the party line was (and still is) that even if the applications were not immediately obvious, eventually research in mathematics pays off. Mathematical advances are thus a vital ingredient in the supply chain of civilisation and technological advancement.

It’s a nice story, but what if it’s all built on sand? The mathematician’s ultimate defence–and for many the raison d’être of the entire discipline–is rigour and logical certainty of the work. Unfortunately, this was shaken up severely by Bertrand Russell in 1901 with his famous paradox. We have already seen that Russell had interesting things to say about causality. With the paradox, he showed that (naive) set theory, a branch of mathematics developed in the 19th century as a unifying formalisation for mathematics, was inconsistent. Basically, this meant that any proposition whatsoever could be proved. We could prove 2+2=4, but we could also prove 2+2=5. Nothing could be falsified because everything was both true and false at the same time. This, understandably, led to a moral panic. There were several important consequences, including Hilbert’s programme, Zermelo-Frankel set theory, Gödel’s incompleteness and Nicolas Bourbaki.

This blog is not about philosophy of mathematics, so I will skip right ahead to the main point: my intense dislike of Bourbaki. If you have not heard of Bourbaki before, it’s a rather romantic, movie-script kind of story: the scene is Paris in 1935, where a group of young, disaffected, rebel mathematicians wanted to change the world; or, at least, their discipline. They began to discuss their ideas of how to change mathematics, which they saw as too often informal, too disconnected, old-fashioned and chaotic. It was time for a revolution.

paris1935.jpg

Street scene, Paris 1935.

To emphasise the collective nature of the endeavour, they published under the nom de guerre Nicolas Bourbaki. From 1939 onwards, Bourbaki authored a series of very influential textbooks. The project continued and gained power and prestige: over subsequent decades the group’s membership changed and at various times included many of the leading lights of modern mathematics as contributors, people such as Eilenberg and Grothendieck. The following is a description by Marjorie Senechal, taken from her wonderful 1997 interview with Pierre Cartier, a Bourbaki member between 1955 and 1983:

From its beginning, Bourbaki was a fervent believer in the unity and universality of mathematics, and dedicated itself to demonstrating both by recasting all of mathematics into a unified whole. Its goals were total formalization and perfect rigor. In the post-war years, Bourbaki metamorphosed from rebel to establishment.

Bourbaki’s unifying idea was that mathematics ought to be viewed as the study of mathematical structures. A mathematical structure is a set, i.e. an abstract collection of elements, with some structure: e.g. operations, subsets, constants. These then are required to satisfy a number of axioms. A vector space is one example: it is a set, whose elements we call vectors, containing a special element 0, an action of a field on that set, and an addition operation, all together satisfying a long list of axioms. All this data is now found in the first two pages of any advanced linear algebra textbook. Indeed, linear algebra–from the point of view of a Bourbakian–is the study of the mathematical structure called vector space. End of story.

Bourbaki resulted from similar currents of thought that produced fascism and totalitarian communism: moral panics leading to revolutions, and ultimately “final solutions”, all terrible and evil in various ways and degrees. Bourbaki was an attempted “final solution” for mathematics. This is not my hyperbole: in Senechal’s interview, Cartier says:

A final solution. There are good reasons to hate that expression, but it was in the people’s minds that we could reach a final solution. … In science, in art, in literature, in politics, economics, social affairs, there was the same spirit. The stated goal of Bourbaki was to create a new mathematics. He didn’t cite any other mathematical texts. Bourbaki is self-sufficient. … It was the time of ideology: Bourbaki was to be the New Euclid, he would write a textbook for the next 2000 years.

Bourbaki’s new mathematics had no space for pictures. Diagrams were too fragile, not nearly mensch enough. Cartier says:

Bourbaki’s abstractions and disdain for visualization were part of a global fashion, as illustrated by the abstract tendencies in the music and the paintings of that period.

Bourbaki is the reason why we still have boring textbooks in mathematics in general, and linear algebra in particular. Bourbaki hated intuitions. Bourbaki is partly responsible for the insane levels of specialisation in modern mathematics. In this blog we fight Bourbakism. ¡Hasta la victoria siempre!


 

Graphical linear algebra is not the study of a mathematical structure in a Bourbakian sense. Instead, we use diagrams to describe linear algebraic concepts. So matrices are not homomorphisms between vector spaces, but diagrams in a theory of adding and copying. As we have seen, an m×n matrix A is a diagram with n dangling wires on the left and m on the right. In our graphical shorthand:

matrix

The cool thing is that matrices are just the beginning. For example, a Bourbakian would consider the kernel of A as a sub vector space ker A of the domain of A: that is, a set of vectors v such that Av = 0. In graphical linear algebra the kernel is not a set. As we have seen, it is also a diagram, one that is obtained in a modular way from the diagram for A.

kernel

Similarly, the image of A is not the set { w | ∃ v. Av = w }. It is the following diagram.

image.gifOur diagrams are not fragile. They are precise mathematical objects and come with a set of equations which allows us to write proofs, transforming one diagram into another. As we have seen, all of these equations have rather simple justifications and describe how an abstract operation of addition interacts with an abstract operation of copying. Hence the slogan, which we saw back in Episode 7:

Linear algebra is what happens when adding meets copying.

Proofs are done through diagrammatic reasoning, which we discussed in Episode 6 . Their style departs from Bourbakian set theoretic arguments like “take an element x in ker A”. To show, for instance, that A has a null kernel if it is injective, we start with the diagram for A, append another diagram to obtain its kernel, and use the assumption of injectivity to transform it into the diagram for the null subspace. We saw this in the last episode, but here’s that part again, diagrammatically.

 

injectiveimpliesnullkernel


 

What really excites me about graphical linear algebra is the fact that it we can have our cake and eat it too: the diagrams provide intuition but are also sentences of rigorous, formal language.

Moreover, the diagrammatic method feels like a high level language when compared to the low level “machine code” of Bourbakian mathematical structures. We saw that the concepts of natural numbers, integers and fractions all follow from the interactions of the basic generators. There was no need to encode these concepts as separate mathematical structures. And the story led to some surprises too: in particular, we had to get over our dividebyzerophobia.

I hope to emphasise the idea of “diagrams as a high level language” in the next ten episodes or so. My plan is to start exploring how string diagrams can help in describing and reasoning about physical systems; in particular we will look at things called signal flow graphs in systems theory. There are some surprises in store: we will look at the idea of feedback in a new way. As we have seen, feedback is a concept that deeply troubles people who believe in causality. If causalists had their way, they’d happy throw the real world away to get away from the problems that feedback brings.

Bourbakism was the effect of the foundational crisis in mathematics of the early 20th century. Mathematicians can feel a little bit more secure today: after all, computer science and the information revolution has been built on mathematics and formal logic. Mathematicians also no longer seem to care very much about foundations, and computers mean that we don’t need to taylor notation for ease and speed of calculation. Instead, we can emphasise what I believe is the true purpose of maths: making complicated, seemingly impenetrable things intuitive and simple.


 

My sabbatical has finally started. On Monday evening I arrived in Honolulu, and I will be working with Dusko Pavlovic at the University of Hawaii for the rest of the year. Dusko has been working on very exciting things, one of which is to try to understand the “essence of computability theory” with string diagrams, not unlike the kinds of diagrams that we’ve been using on this blog. He uses them to form a theory called monoidal computer. You can check out an introductory paper here. I’m really excited to find out more and hopefully contribute something interesting.

I will also, hopefully, have more time to write.

Continue reading with Episode 31 – Fibonacci and sustainable rabbit farming.

29. Dividing by zero to invert matrices

I’ve let the blog slide. At the end of this episode I’ll write a bit about what I’ve been doing in the last few months. For now, let’s just jump straight back into graphical linear algebra.

In order to motivate myself to get back to writing, I brought forward an episode that I’ve been excited about since late last year, when I first did the research. This material is closely linked to Episode 26 on division by zero. If you haven’t read it, or you have forgotten, it will be useful to take a look before continuing.


 

Episode 26 was quite popular — maybe the clickbait title helped. It did leave some people a bit skeptical: ok, so this guy has derived addition and multiplication tables that seem to say that dividing by zero makes sense. But can this weird idea of dividing by zero actually be useful, or is it merely a curiosity?

There are other number systems that, in principle “allow” you to divide by zero. Many of them work similarly to the IEEE standard for floating point arithmetic, which has an additional entity called NaN (not a number). Roughly speaking, it’s the result of all of the calculations that shouldn’t make sense, like dividing by zero. Next, if you add and multiply a NaN with anything else, you still have a NaN. So it’s kind of like a black hole number: once you get it part way through your calculation you can be pretty sure that something has gone wrong and that the overall result will be a NaN — no matter what you do, you will never end up with an ordinary number again.

This is not the case for the number system from Episode 26. In fact, the three additional elements , , do show up in calculations. The cool thing is that they are not a sinkhole like NaN: you don’t need to panic if you get, say, a  in one of your calculations. It’s possible that things will finish well. This episode is entirely devoted to one example: inverting matrices.


 

We will need a few definitions.

An n×m matrix A is said to be invertible when there exists an m×n matrix B, such that when you compose in either direction, you get the identity. In diagrams:invdef.gif

If such a B exists, we sometimes write A-1 = B. Many matrices are not invertible. One property of those that are is that m=n, that is, invertible matrices are all square; the number of rows is equal to the number of columns.

Actually, it’s like this in most PROPs – you can usually only invert things where the left and the right boundaries have the same size. A useful intuition to keep in mind is that something can only be invertible if it can be undone. And since wires carry information, we can’t just throw one away or add a new one and expect to be able to undo it.

Back to definitions. We will say that an n×m matrix A is injective, or mono, when the following is true.

mono.gif

The backwards facing A is none other than the mirror image symmetry  that we discussed in Episode 27.

The above definition probably seems a bit strange. In most ordinary linear algebra textbooks, the defining property of an injective n×m matrix is that it takes  different m-vectors to different n-vectors: that is, it is injective as a function. This is actually an equivalent formulation, but we don’t think about matrices as functions on this blog.

One interesting property of mono matrices is that they are left-cancellable: that is, given two equal-sized matrices B, C for which AB and AC is defined, if AB=AC then B=C. In fact, this is true when B and C are linear relations. Diagrammatically:

injleft.gif

implies that

injright.gif

Here B and C are linear relations, i.e. arbitrary diagrams in IH. This of course includes the case where B and C are matrices.

Actually injectivity and left-cancellability are also equivalent, i.e. assuming one, you can prove the other. I’ll leave the proofs as an exercise but I’ll give you a hint: it’s handy to use the fact, stated in Episode 27, that for any linear relation A, A is its weak inverse.

The bizarro of injective is surjective. We will also use the word epi. Thus, an n×m matrix is surjective when the following is true:

epi.gif

Just as mono matrices are left-cancellable, epi matrices are right-cancellable; given B and C such that BA and CA make sense, if BA=CA then B=C. In terms of ordinary linear algebra, surjective matrices are those that are surjective as functions; for every n-vector b, there exists an m-vector a such that Aa=b.

There is one final observation that we will need later: any invertible matrix is both injective and surjective. To keep things moving along, I’ll also leave the proof of this as an exercise.


 

Let’s now prove a classic result of linear algebra. It refers to kernels and images, which are linear subspaces that we discussed in the last episode.

Kernel and Image Lemma. Suppose that A is an m×n matrix. Then:

  1. A is injective exactly when it has a null kernel
  2. A is surjective exactly when it has a full image.

Proof. Properties 1 and 2 are mutually bizarro, so it’s enough to prove just one. We will do 1.

Suppose that A is injective. Then:

kernellem1

Which means that A has a null kernel.

Suppose now that A has a null kernel; we want to show that it must be injective.

kernellem2

That’s it, we’re done, QED.

 


 

The following lemma is very useful because it gives us some useful graphical intuition about invertible matrices.

Invertible Matrix Lemma

Suppose that A is a square matrix of size m. Then the following are equivalent

  1. A has inverse B
  2. There exists matrix B such

inverse

Proof. Let’s first show that 1 implies 2. Assuming 1, Suppose that A has inverse B. Since A is invertible, we know that A is injective. So we have the following:

lem1

Which gives us 2. In the first step, we used the assumption that B is the inverse of A, and in the second step we used the fact that A is injective.

We still need to show that 2 implies 1. So, supposing that A is equal to some matrix B heading in the opposite direction, we need to show that B is the inverse of A. To do that, it’s useful to show that A must be injective. Here we can use our Kernel and Image Lemma.

lem2

So, by the kernel lemma, A is injective. We can now use this to show that A followed by B is identity.

lem3

To show that B followed by A is also identity, we can do the bizarro thing, first showing that B is surjective.


 

Our aim is to obtain a formula for the inverse of a matrix, if it exists. The starting point is an arbitrary 2×2 matrix, so something like this:2x2.gif

If an inverse exists, then we know it’s also going to be a 2×2 matrix:
2x2prime.gif

The tricky part is, how can we calculate a’b’c’ and d’, knowing ab, c and d? If you remember your linear algebra, maybe you’re thinking determinants and adjugate matrices. We will bypass all that and draw some pictures instead.


 

Let’s start by using our Invertible Matrix Lemma. As diagrams in IH, we have:

2x2eq.gif

Now adding a matrix to -1 times itself gives us the zero matrix. Using this trivial observation, we get the following rather complicated looking equation:

step1.gif

We can extract the formula for each of a’, b’, c’ and d’ by plugging up some of the dangling wires in the above equation. Let’s work through the procedure for a’.

The first step is to plug a zero and a discard at the right places in both sides, like so:

pattern

Doing that, we get the first equality below.

step2.gifThe second equality follows from the bone equation of bimonoids.

So far so good: but now we can drastically simplify the left hand side. Essentially, we’ve plugged a white unit into a black comultiplication, and vice versa; usually when that happens, there is mass destruction. I’ll leave the graphical derivation to you. After you’ve killed off most of the diagram, the left hand side ends up looking like this:

step3

The nice thing is that now a’ is the only entry from the inverse matrix that’s left. And we already know that the diagram above is equal to zero, i.e.

rhs

So we are in the situation where a’ plus -1 times some mess is equal to 0; thus:

step4

This is starting to look like a formula. We can untangle the still somewhat messy right hand side above. The result is:

step5.gif

In terms of a bona-fide, old-fashioned syntactic formula—if you’re into that kind of thing—this translates to:

fomulaaprime

Note that I did not go further in simplifying the denominator because d might be zero, and in that case, multiplication may not be commutative. Relax; to evaluate the formula for specific numbers, we can use our addition and multiplication tables from Episode 26.

There is nothing special about a’. We adapt our procedure by plugging up the other combinations of wires and obtain formulas for b’, c’ and d’. All together:

fullformula

I find it quite cute how a, b, c and d permute in each of the formulas. And no determinants, nor adjugates in sight!


 

Let’s do a worked example, calculating the inverse of the matrix:

example

Referring to the formula for the inverse, we have d=0, so we will divide by zero when calculating a’. For that, we can refer to the multiplication and addition tables from Episode 26. Here’s the calculation:

calc

The other calculations don’t involve any funny stuff — we end up with

res.gif

I promised you an example where the extended rational algebra of Episode 26 can be useful. And while inverting 2×2 matrices is not going to set the world alight, I hope that this is a hint that there is something interesting going on!

By the way, the formula that we derived for inverting 2×2 matrices generalises to arbitrary square matrices. I don’t have the space for this in this episode, but if there’s interest I can come back to this topic. Let me know.


 

Not writing is like not going to the gym (which, coincidentally, I’m also guilty of). I mean that once you start not writing, it’s difficult to get back into it. “I’ll do some writing next weekend” – you tell yourself. Before you know it, half a year has passed. Same with (not) going to the gym. I’m still working on that.

Having said that, it’s been a very busy half a year. In addition to teaching,  I visited Paris—and more specifically, Jean Krivine—for a month. I love Paris; I spent a six-month postdoc there in 2005 and it was fantastic to be back in the 13e arrondissement.

paris

Apart from enjoying the city, it was a really productive visit and I learned a lot. Jean is currently working on a graphical high-level programming language for biologists, which shares many features with the kind of string diagrams that this blog is obsessed with.

Amongst other things, Jean told me about a family of string-diagrammatic calculi for logic, developed by the famous 19th century American logician C.S. Peirce (pronounced “purse”; it’s Dutch, apparently). Jean uses some of Peirce’s ideas for his programming language. Peirce’s systems are called existential graphs and have a fascinating history.  While Peirce considered them his most important scientific achievement, they remained unpublished in his lifetime; I guess due to a lack of typesetting technology for diagrams, but maybe also due to the fact that his ideas were so revolutionary that they were about 100 years before their time. In fact, Peirce’s diagrams came before the standard syntactic way of writing logic, with all the upside down As and backwards Es that logicians are so fond of. But his work was forgotten and were rediscovered only in the 1960s. They are still a topic of research.

Existential graphs really blew me away. I plan to understand them properly over the next few months, and maybe I will write about them more seriously one day. For now, if you’re interested in reading further, the PhD thesis of Frithjof Dau seems like a great resource.

This weekend I will be in Porto for the HDRA workshop, and the weekend after that I’m flying to New York for the LiCS conference. It’s going to be a busy summer, but I will try to work more regularly on the blog from now on.

Continue reading with Episode 30 – The essence of graphical linear algebra.

28. Subspaces, diagrammatically

There are two common ways to interpret the information represented by a matrix. Roughly speaking, it boils down to whether—when looking at a grid of numbers—you choose to see a list of columns, or a list of rows. The two interpretations are symmetric, and this is nicely captured by this blog’s obsession, the graphical syntax. And as we will see, the two ways of looking at matrices will lead us to two different, symmetric ways of understanding linear subspaces.


 

Consider an m×n matrix A, drawn with our graphical sugar for matrices as a gadget with n wires entering on the left and m wires exiting on the right, like so:

matrix

A can be viewed as consisting of n column vectors c1, c2, …, c. Each of the c‘s is individually a m×1 matrix, so it has one wire entering on the left and m wires existing on the right. We can then wire up A, emphasising the column vectors, like so:columns

Alternatively, we can view the same matrix A as consisting or of m row vectors r1, r2, …, rn, with each having n wires on the left and one wire exiting on the right. This leads to drawing A like this:rows

Even though in both cases we are talking about the same matrix—the same raw data—it turns out that the two different points of view lead to two quite different interpretations.


 

Let’s work through a concrete example. Consider the matrix

matex

which has no particular significance; I just pulled it out of a hat, so to speak. But it’s usually a good idea to have a particular, concrete object to work with, and this one does the job.

Emphasising the columns, it can be drawn like this:

colsex

Or we can focus on the rows, as shown below.

rowsex


 

Viewing a matrix as a list of columns leads to the first interpretation of what a matrix means: a recipe for of transforming n vectors—that is, columns of of n numbers—into m vectors, i.e. columns of m numbers.

Indeed, let’s take another look at A drawn in the way that emphasises its columns.

columns

We can imagine the n dangling wires on the left as being n different inputs. Now each ci takes an input number and produces a column of m numbers. At the end, the n columns, each of size m, are simply added up.

Let’s work through an example to see how this works, using the concrete matrix from before.

columnsex

Here, our input vector consists of 51 and -2. Each input results in two outputs, according to the recipe within each column block. They are then added up, e.g. 5+(-1)+(-2)=2 in the first output. Using the standard linear algebra jargon, we have produced a linear combination of the column vectors:

linearcomb

In our worked example above we took one particular, quite arbitrary choice of inputs: 5, 1 and -2. This leads to a natural question: exactly which vectors can be produced by this circuit, supposing that we are free to choose any inputs whatsoever.

In the example above, it turns out that all outputs can be produced by picking the appropriate inputs. But this is not always going to be the case; for example, if all the columns consist of only zeros then clearly only the zero output is possible.

The general question is, then, the following: given column vectors c1c2, …, cn, which m vectors can be written as a linear combination

α1c1 +  α2c2 + … + αncn?


 

How can we express this idea in our graphical language?

It turns out that the idea of considering all possible inputs is simple to describe. It is also quite intuitive. First, let’s return to our venerable discard generator.

discard

Recall that our intuition, backed by the functional semantics, is that this simply discards any number given to it. With matrices, we usually like to think of numbers flowing from left to right. So what are we to make of discard’s mirror image?

generate

Well, if the discard can throw away any number, then a nice way to think about its mirror image is that it can generate any number. So, to get back to our original question, we can talk about the linear subspace of Qm generated by the matrix A by simply considering all the possible inputs to each column. Like so.

range

The diagram now represents the subspace that consists of all the linear combinations α1c1 +  α2c2 + … + αncn of A‘s column vectors, where each α is a fraction. More precisely—as we have discussed in the last episode—the diagram gives us a linear relation of type Q⇸ Qm, which we can (since Q0 contains only one element) then simply think of as a subspace of Qm.

This subspace is quite famous and has several names; it’s variously called the image, range, or column space of A, or the span of c1, c2, …, cn. And, using our usual syntactic sugar, we can simply write it as:

rangesugar


 

I claimed above that our example matrix can produce any pair of outputs. Let’s do the calculation to make sure: it’s a nice little exercise in diagrammatic reasoning.

imageex

The image is thus the entire space Q2, so for any pair of fractions p, q we can indeed find inputs u,v,w such that

Auvw


 

Viewing a matrix as a collection of rows leads to another popular interpretation of the information that a matrix represents: a list of equations that constrain the inputs. Let me explain.

Drawing A in a way that emphasises the rows, we can think of each ri as encoding a linear combination of the inputs.

rows

For example, going back to our original matrix, let’s label the inputs with variables x, y and z.

rowsex2

So the rows tell us how to combine the various inputs to form the outputs: for example, the first row gives us x-y+z and the second 2y+z.

Here, the natural question is to think of the rows as homogenous equations, and consider the set of solutions, those concrete choices of x, y and z that satisfy them. Homogenous, by the way, means simply that we append = 0 to each linear combination of variables.

So for our running example, we could consider the collection of all the inputs constrained so that they satisfy the two equations:

x-y+z = 0                  ①             

2y+z = 0                  ②


We can also represent this graphically. When we emphasised the columns, we introduced a new intuition for the mirror image of discard. This time we are focussing on the rows, and so, not surprisingly, we will introduce a new intuition for the mirror image of the zero generator.

Recall that the zero generator, in the original left-to-right functional interpretation, simply outputs 0.

zero.gif

So how are we to think of it’s mirror image?

constrainThe answer is that it’s a constraint: it only accepts 0!

Using this insight, the solution set of the list of homogenous linear equations given to us by the rows of the matrix A is graphically represented as:

kernel

or using our usual sugar:

kernelsugar

This is a linear relation of type QnQ0, so for the same reasons as before, it’s pretty much the same thing as a linear subspace of Qn. This subspace is also very important in linear algebra, and is variously called the kernel, or the nullspace of A.


 

Let’s do a calculation that will give us more information about the kernel of our long running example matrix. The calculation is a bit longer than before, but the details are not so important at this stage.

kernelcalc

In the derivation we used the Spider theorem from Episode 23.

Here’s the interesting thing about the calculation: we started with a diagram in which we were thinking of the “flow” as going from left to right, where our inputs had to satisfy some equations. We ended up with a diagram which is easier to understand as going from right to left. Indeed, it’s an example of the kind of subspace that we got by focussing on the columns; it is:

N.gif

where N is the matrix

Bmat.gif

In other words, the kernel of M is the same linear subspace as the image of N. This tells us that everything in the kernel is of the form

kerneldesc

where α is some fraction. So the solutions of the system of equations  and  are x = 3α, y = α, z = -2α.


 

We have seen that some descriptions of a linear relation can be read “from left to right” and others “from right to left”. Indeed, we have just seen an example of a linear relation that had two descriptions:

spaceeq.gif

So what is really going on here? It turns out that we can think in two ways about every linear relation.

  1. Every linear relation can be seen as “being generated”, in the way we described the image subspace.

rangesugar2. Every linear relation can be thought of as consisting of the solutions of homogenous equations, of inputs “being constrained”, the way we described the kernel subspace.kernelsugar

Let’s be more precise about this. We will start by considering the first of the two situations, the “being generated” case.

The proof of IH ≅ LinRel—which we haven’t seen yet but we will go through in due course—has one important consequence: for every linear relation R: m⇸n we can find an m×p matrix A and n×p matrix B such that

spanform

If we have such matrices A, B then we will say that they are a span form of R. Span forms allow us to think of R as being generated. In fact,

rangesugaris in span form, since

ndiscardis the graphical representation of the unique 0×n matrix.

The proof of IH ≅ LinRel also gives us the “being constrained” case, which is pleasingly symmetric. For every linear relation R:m⇸n, we can, respectively, find q×m and q×n matrices C and D such that

cospanform

This is called a cospan form of R. Cospan forms capture the idea that a linear relation can be thought of as the solution set of a bunch of homogenous equations. An example is the kernel of a matrix A

kernelsugar

since

zerom

is the unique m×0 matrix.

One little quirk of history is that the traditional way of doing linear algebra focusses very heavily on the span view, and almost totally ignores the cospan view. One takes a space and finds a basis, one talks about its dimension, etc. But the cospan view is just as expressive, given the symmetries of graphical linear algebra. So, it’s entirely possible that Martian linear algebra has been developed in a way that prioritised the cospan view of linear subspaces. It’s fun figuring out the details, and we will do some of this in the next episode!


 

 

I’m having a very heavy start to 2016: originally I was planning to publish this episode in early January, and it’s now early February. The highlight of the month was a trip to Oxford on Friday January 8. I was there to examine a thesis entitled “!-Logic: First-Order Reasoning for Families of Non-Commutative String Diagrams” of (the now Dr.) David Quick, supervised by Aleks Kissinger. I liked the thesis very much: it’s about a logic for string diagrams, much like the ones on this blog. David’s logic supports reasoning about whole families of diagrams, including supporting sophisticated inductive arguments; much more sophisticated and powerful than the kind of induction that we have been using on the blog. I will have to write about it at some point in the future.

I arrived in Oxford quite early, and it was a really beautiful morning. On my walk from the train station to the computer science department I got the urge to take a photo.

12417944_10153936526981383_3321537427747874569_n.jpg

The next Friday, January 15, I was in Cambridge to give a talk. That trip was also a lot of fun, and I got the chance to catch up with some old pals. The evening was very pleasant, and I decided to walk from the computer science department to the train station. On the way I took this photo:

11237564_10153952837936383_628595388964310973_n

I later noticed—and I promise, as much as it looks like it was, this wasn’t planned!—that the photos themselves are quite symmetric: compare the relationship of water to land. Since we spend a lot of time talking about symmetry on this blog, I think it’s somehow appropriate.

Continue reading with Episode 29 – Dividing by zero to invert matrices.

 

 

 

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

firstmat

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

secondmat

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

exback

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 MatZ of 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 Qm to Qn. 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 Qm ⇸ Qn is a relation, so a subset of the cartesian product Qm × Qn. 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 QQ that consists of all pairs

addrel

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: Qm ⇸ Qn must be a linear subspace of Qm × Qn, 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.

zero

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

ab

and

cd

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

abpluscdIt 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 a1+c1, a2+c2 and so on until am+cm. So—using our new shorthand notation—for R to be closed under pointwise addition, whenever (ab) and (cd) 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

ab

is in R then also

kab

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 ka1, ka2, …, kam. 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: Qm ⇸ Qn and S: Qn ⇸ Qp gives R;S : Qm ⇸ Qp 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:

  1. verify that the identity relation is a linear relation,
  2. check that composing two linear relations results in a linear relation, and
  3. 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: Qm ⇸ Qn and S: Qn ⇸ Qp are linear relations then so is R;S.

Let’s prove closure under pointwise addition: suppose that (x1z1) and (x2z2) are in R;S. We need to show that (x1+x2, z1+z2) is also in R;S. Using the definition of relational composition, there exist y1, y2 such that (x1y1) and (x2y2) are both in R and (y1, z1) and (y2z2) both in S. Since R and S are linear relations, they are both closed under pointwise addition, so we can conclude that (x1+x2, y1+y2) is in R and (y1+y2, z1+z2) is in S. It thus follows that (x1+x2z1+z2) 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

twist

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

twistgen

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

IHLinRel.

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 BMat and H ≅ MatZ. 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: since IHLinRel 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.

bot

The diagram for this linear relation is

botdiag

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.

top

The corresponding diagram is

topdiag

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

iddiagis the line with slope 1.

id

All the fractions arise like this. For example, the line for the fraction 1/2,  diagrammatically

minhalfdiag

is the line with slope 1/2

minhalf

You get the idea for the other fractions.

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

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

zeroline

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

infline

which is the plot for

infdiag

that we called  in the last episode.

If we think relationally, then the operations x+y, x×y and 1/x are all easy to define, and are total on the set of linear relations  Q. Multiplication is simply relational composition, and 1/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: (ba) is in R exactly when (ab) 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 bc such that (ab) is in D, (b, c) is in D and (cd) is in D. And since (bc) is in D, (cb) is in D.

Now, using the fact that D is a linear relation that contains (ab), (cb) and (cd), we have that

(a, b)-(c, b)+(c, d) = (ac+c, bb+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:

weakcounter


 

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

2016

 

Continue reading with Episode 28 – Subspaces, diagrammatically.

 

26. Keep Calm and Divide by Zero

The fear of dividing by zero is a common affliction. I caught it at school when trying to get my head around this well-known “proof” of 1 = 2:

  1. suppose that a = b
  2. then a2 = ab
  3. subtracting b2 from both sides gives us a2 – b2 = ab – b2
  4. factorising gives (a + b)(a-b) = b(a-b)
  5. dividing both sides by a-b gives a+b = b
  6. But also a+b = b+b = 2b, so 2b = b. Dividing by b gives 2 = 1.

The problem is in step 5, in which both sides of the equation are divided by zero: helpfully, this article with a similar wrong proof explains that you cannot ever do that.

Looking at the available evidence in popular culture, interest in dividebyzerophobia is prevalent: for example, this Numberphile video has over 2 million views. Even Siri has something amusing to say.

So I was understandably very nervous when I first realised that graphical linear algebra lets you divide by zero. I double checked everything: something must have gone seriously wrong.

Let me explain.

In the last episode we saw that ordinary fractions v/w (where w≠0) can be represented as the sugar:

sugardef

We then discovered that the usual rules for doing arithmetic with fractions follow from the equations of our algebraic system:

addition

multiplication

The derivations made use of the fact that q and s are not zero.

So far so good, but there’s an important difference between fractions and our diagrams. Fractions are inherently asymmetric: the numerator is allowed to be zero, but the denominator is not. On the other hand—as we saw two episodes ago—the generators and equations of graphical linear algebra are symmetric.

So, since by definition we haveoneandzero

if we can draw the diagram for 0/1, then there’s nothing stopping us from drawing the diagram for 1/0:

onedividedbyzero

But we are never allowed to do this, right?

Stay calm and take a deep breath: dividebyzerophobia is an irrational fear, caused by a deficiency of the fraction notation that we all grew up with. I no longer suffer from it and, with the right dosage of graphical linear algebra, neither will you.


 

As we have seen, all fractions are diagrams with one dangling wire on the left and one on the right. But—as we just discovered—not all diagrams of this type are legal fractions. In fact, there are precisely three that fail to be of the right form, and they all involve dividing by zero in some way. Let’s give them names:

extraelms

It makes sense to choose ∞, the symbol for infinity, as the name for the 1/0 diagram: for example 1/x diverges to positive or negative infinity as x approaches zero. And positive and negative infinity are one and the same in projective arithmetic.

We will come back to projective arithmetic in more detail in the next episode. For now, let’s verify whether our diagrams indeed tell us that positive and negative infinities are equal.

posneginft

The remaining two elements,  and ⊥, are two ways of resolving what we might mean by 0/0, which is ambiguous. This ambiguity does not exist when talking about ordinary fractions: if w is nonzero, the following two diagrams are equal, using the fact that nonzero sugars commute with sugars heading in the opposite direction. We showed that in the last episode.

equalfractions

So both of these diagrams represent the fraction v/w. But when v=w=0, the two diagrams are different: the first is , the second .


 

I’ve coloured ∞, ⊤ and ⊥ differently from our usual sugars, because, as we will see, they don’t behave quite as well as ordinary fractions. Nevertheless, we can try to do arithmetic with them as we did with fractions.

For example, what happens if we take some (legal) fraction p/q and add it to ?

fracplusinfty

We seem to get stuck at this point because we don’t have any equation that tells us what happens when we plug the (wrong way) zero generator into a copy. It turns out that:

dagger

Here’s a derivation:.

lemma

Using what we know about symmetry in graphical linear algebra, we can immediately state the bizarro version, which is

ddagger

Continuing our calculation , we get

fracplusinfty2

So, given any fraction p/q we have that p/q + ∞ = ∞. In fact, using (†) and (‡), we can also show that  ∞ + ∞ = ∞,  ⊤ + ∞ = ∞ and ⊥ + ∞ = ∞. So anything plus infinity is infinity.


 

In the fifth line of the above calculation we used a property we have not yet proved, that whenever w ≠ 0, the w can come out of a discard. This property is related to one from the last episode: nonzero sugars can go the wrong way over copy. Here’s a reminder of what this means, together with its bizarro version:

wrongway

To keep a clear conscience, let’s prove the new property. Its bizarro version, which says that the zero generator can swallow nonzero sugars, will also come in handy in proofs.

wrongwayunits

Using the usual symmetry argument, it’s enough to prove one.

proofwrongwayunit

Also, since we didn’t do it earlier, this seems a good time to check whether 0/w is actually the same as 0. In the second step we use our new fact about the zero generator and nonzero integer sugars.

zerofrac


 

We may as well fill out the full addition table, which takes account of all possible ways that (1,1) diagrams can be added. In the table below I separated 0 from the nonzero fractions, where both the numerator and the denominator are not zero.

Remember that our diagrammatic addition is commutative, so we don’t need to fill the table below the diagonal.

+ 0 r/s
0 0 r/s
p/q sp+qr/qs

Perhaps the most mysterious equation in this table is ⊤ + ⊥ = ∞. It’s very simple to justify:

topplusbot

Multiplication is a bit more hairy, because although it is commutative on ordinary fractions—as we saw in the last episode—it is not always so when we consider the expanded system with the additional three elements. This means that now we need to fill in the entire table.

× 0 r/s
0 0 0 0
p/q 0 pr/qs
0 0

There are some interesting symmetries in the table. And we can resolve the old philosophical conundrum about what happens when we multiply infinity by zero! In graphical linear algebra it turns out that 0 × ∞ = ⊥ and ∞ × 0 = ⊤.


 

What do we really mean by “dividing by zero”? As Siri says, it does not make much sense to divide cookies amongst zero friends; even when the Cookie Monster is happy, you are still sad.

Graphical linear algebra comes with the mirror image symmetry. We will use the dagger () superscript to mean mirror image. So if d is a diagram of type (m,n) then its mirror image d is a diagram of type (n,m). Clearly, no matter what the d, we always have d†† = d.

When d is a nonzero fraction sugar, then it turns out that d† is the multiplicative inverse of d: this means that d ; d† = d†; d = 1. It’s an easy derivation:

multinv

When d is 0 or  then this is no longer the case, as can be seen from the multiplication table. For example 0 ; 0†  =  0 ; ∞  =  ∞ × 0  =  ⊤ and 0† ; 0 = 0 × ∞ = ⊥.

Since does not always mean multiplicative inverse, what are some properties that it does satisfy for all (1,1) diagrams? Here is one: d and d are the weak inverse of each other.

d ; d ; d = d

d ; d ; d = d

I’ll leave this as a simple exercise. It will be great as the first step in your dividebyzerophobia treatment programme. For nonzero fractions, the equations follow from the fact that gives us the multiplicative inverse. To treat the other cases, you will only have to do four calculations, because  = ⊤ and  = ⊥.

The mirror image symmetry will be very useful when we talk about inverting matrices in graphical linear algebra. I’m thinking of bringing some of this material forward—maybe already to the next episode—because it is a nice example of how dividing by zero can actually be useful in calculations.


 

Although it was fun to fill in the addition and the multiplication tables, there are good reasons not to give  and  the same status as we give to the numbers (naturals, integers, fractions) that we have seen so far, and others (reals) that we will talk about in the future. This is why we have been colouring their sugars differently.

I don’t plan to get bogged down in a philosophical discussion about “what is a number?” (Episode 17 did not seem to go down too well) but there are a number of useful properties that “numbers” ought to satisfy in graphical linear algebra. For one, the bizarro of a number should be itself. This works for ∞, but ⊤ and ⊥ are the bizarro of each other.

It is also very useful to know that numbers, whatever they are, satisfy the following:

usual

We know from earlier episodes that they hold for the natural numbers and for the integers. Given what we now know about nonzero sugars going “the wrong way” over copy and addition, and into discard and zero, it is follows that they hold for fractions as well. So, the a in the above equations can be any legal fraction.

These properties allow us, amongst other things, to prove that multiplication distributes over addition. But all three of  and ⊥ fail some of these four tests. For example, we have:

inftyfailure

And these two diagrams cannot be shown equal in our theory. For now, you could think about the underlying relations, but we will get more precise about characterising diagram equality in the next episode.

So—long story short—while we will not think of them as numbers per se, we will not panic when we see and  popping up in calculations. They are all perfectly harmless.


 

In algebra, the notion of a set of elements with addition and multiplication, where multiplication is commutative and distributes over addition is called a commutative ring. If all nonzero elements also have a multiplicative inverse, the resulting structure is called a field. The rational numbers (i.e. fractions) and the real numbers are two examples.

Fields are a little bit peculiar from an algebraic perspective, because the operation of taking multiplicative inverse is partial0-1 is left undefined. Having partially defined operations complicates things.

One classic way of addressing this defect is projective arithmetic, which we will see in more detail in the next episode. There 1/0 makes sense, but 0/0 is still typically left undefined. Recently, inspired by projective arithmetic, Youtube legend Norman Wildberger proposed to hack fraction notation so that 0 is allowed in the denominator: you can check out some videos starting from this one. I have not yet had the time to understand the details, but it seems that you have two new elements that correspond to 1/0 and 0/0; the latter seems to be our  but there is no .

There are some other algebraic systems that go the whole hog and make all operations defined everywhere. Two that I’ve come across are wheels and meadows. If there is interest, I can write more about these; let me know in the comments.

There is one fundamental difference between the above approaches and arithmetic in graphical linear algebra. There, existing notation (e.g. addition, multiplication, fraction notation) and associated equational theories were extended in some way to make sense of dividing by zero. In graphical linear algebra, addition is not even a primitive operation, or at least it’s not primitive in the same sense. So instead of setting out to make sense of 1/0, we discovered that it was already happening, in a similar way to how we discovered the natural numbers lurking in the theory B of bimonoids.


 

I was in Edinburgh for a couple of days last week. I left Southampton on a cold, dark and wet morning and arrived in a Scotland bathed in glorious sunshine.

I was there as the external examiner for the PhD defence of Ricardo Honorato-Zimmer, a student of Vincent Danos. It was great to have the chance to catch up with Vincent. He is one of the few scientists I know who is a true polymath—his background is the French school of logic, and his early contributions to the proof theory of linear logic are pretty famous. Around ten years ago, Vincent became interested in stochastic formalisms and graph rewriting, and together with a number of people he developed the Kappa language for modelling protein interaction networks. Vincent’s group is now full of chemists, biologists, mathematical physicists, mathematicians and computer scientists who all manage to communicate (this is far from easy in my experience!) and moreover come up with real advances. Academic politicians like to throw around the term “multi-disciplinary research”, but often the reality behind the buzzword is somewhat underwhelming. It’s always amazing to see the real thing in action.

The day after the defence I gave a short talk about graphical linear algebra at the LFCS seminar. Afterwards I met Kevin Dunne, who is doing a PhD with Ross Duncan at the University of Strathclyde in Glasgow. Kevin told me his idea about how to develop the theory of eigenvalues and eigenvectors with graphical linear algebra: it sounded fantastic and I’m really looking forward to figuring out the details. I also met Nick Behr, who is a mathematical physicist working with Vincent. He told me about the Umbral calculus, used to reason about formal power series, and we tried to figure out the relationship with some related techniques that Filippo, Fabio and I developed using graphical linear algebra. He will visit Southampton for a few days in January; it’s going to be exciting!

I had to come back to Southampton not long after my talk. This time, I experienced some more common Edinburgh weather: I walked from the computer science department to Waverley station in rain and gale force winds. The locals seemed undisturbed.

Continue reading with Episode 27 – Linear Relations.

 

 

25. Fractions, diagrammatically

I’ve been looking forward to this moment for some time. Now that we’ve gone through all of the equations of graphical linear algebra, it’s time to have some fun. In this episode we look at how fractions are represented in the graphical notation, derive the usual rules of fraction arithmetic, and go through a very early example of an algorithm that produces fractions: Fibonacci’s procedure for division by composite numbers.

We will concentrate on diagrams with two dangling wires: one on the left and one on the right. In previous episodes we have seen that these diagrams have a tight relationship with various kinds of numbers. For example, in the theory of bimonoids, a sub-theory of graphical linear algebra, they were in 1-1 correspondence with the natural numbers. When we added the antipode, extending the theory, we got the integers.  Since then, we’ve added the mirror image generators and figured out the equations that relate them. So what additional “numbers” do we get in the theory IH of interacting Hopf monoids that we finished assembling in the last episode?


 

We get fractions, the stars of this episode. Let’s start by proving a useful little lemma. Suppose that w ≠ 0. Then the w sugar can jump over any sugar that’s pointing in the opposite direction, like so.

comm

Here’s the proof of (†):

commproof

In the first and final steps we used the assumption w ≠ 0, since the scalar equations that we introduced in the last episode need this condition. The steps in the middle use the fact that multiplication of integers is the same as composition; we went through this in Episode 18.

We immediately get the mirror version of (†), where the nonzero w scalar is now pointing to the right:

commmirror

No proof needed, because of the mirror symmetry in the equational theory that we discussed in the last episode.


 

Any fraction can be written vw where v and w are integers and w ≠ 0. So let’s extend the syntactic sugar for integers, and define a sugar for fractions as follows:

fractionsugar

At this point we have to be a little bit careful, because a fraction is not merely a pair of integers, one written on top of each other. Fractions represent ratios; for example 12 = 24 since the ratio of one-part-in-two is the same as two-parts-in-four. But (1,2) and (2,4) are different pairs of numbers, and so the usual, formal textbook definition says that a fraction v/w is the equivalence class [(v,w)] where w ≠ 0. The underlying equivalence relation relates (p,q) and (r,s) when ps = qr, since this condition captures exactly what it means for p/q and r/s to represent the same ratio. For (1,2) and (2,4) we have 1 ·4 = 2 ·2, and so 1/2 = 2/4.  So, for our definition of fraction sugar to even make sense—for it to be well-defined—we ought to show that 

welldefn

Let’s do this now. In addition to ps=qr, we can also assume q,s ≠ 0. All three of these assumptions are used in the following proof.

welldefnproof

Our new sugar wouldn’t be much good if we were able to show that two non-equal fractions are the same, using diagrammatic reasoning, i.e. if the translation was not faithful. For this reason, it’s useful to show that the implication that we just proved also goes the other way:

sugarfaithful

Here’s the proof.

sugarfaithfulproofSo we have shown that any fraction can be considered, in a faithful way, as a diagram of graphical linear algebra with one dangling wire on the left and one on the right.

In fact, every diagram of this type—i.e. with one wire dangling from both ends— can be put, using diagrammatic reasoning, either in the form

cospanform

where u,v are integers or in the form

spanform

This follows from some more advanced insights about our equational system, so we will not prove it immediately. You will have to trust me for now.


 

Next up is the algebra of fractions. First a quick reminder of how we used diagrams to talk about the algebra of the natural numbers and the integers. In both cases, addition could be expressed in the graphical language as follows:

additiondef

Of course, this agrees with what we already knew about ordinary addition of integers. One advantage of defining addition in this way is that several of its properties immediately follow by diagrammatic reasoning: e.g. associativity, commutativity and the fact that 0 is the additive identity.

Similarly, multiplication can be defined as composition:

multiplicationdefn

Again, associativity is immediate, but commutativity does not follow for totally generic reasons. One can prove it for the natural numbers by induction, then use this to get commutativity of multiplication for the integers, since the antipode commutes with any natural number sugar.

Finally, for any integer v, we know that its sugar can slide past copying and adding in the following way.

rightway

We proved this for natural numbers by induction in Episode 9, and for integers it follows from the fact that the antipode also slides in this way. These facts can be used to show that multiplication distributes over addition.

Before we delve into the algebra of fractions, we need one more lemma. It says that nonzero scalars can go the “wrong way” past addition and copying.

wrongway

We only need to prove one of the two equations of (‡); the second is bizarro of the first: remember that bizarro is combining the mirror-image symmetry with the invert-colours symmetry and, as we saw in the last episode, both symmetries are present in our equational system.

So let’s assume that w ≠ 0 and prove that w can go the wrong way past copying:

wrongwayproof

In the proof used the scalar equations, which require the assumption w ≠ 0. In the second step we used our knowledge about integers going the “right  way” over copy.

So what happens when w = 0? Let’s take a look at the diagrams. First, if we have 0 going the wrong way to the left of copy we have

zeroleft

and two zeros on the right gives

zeroright

The two results are different: they cannot be made equal using diagrammatic reasoning in graphical linear algebra. We will make the reasons more precise in the next few episodes; for now, we could go back to our relational intuition and figure out that the two diagrams

twodiags

define two different relations. Zero can’t go over addition the wrong way for similar reasons.


Let’s mimic the algebra of the integers and see what happens when we define:

additionfracdefn

and

multiplicationfracdefn

First, multiplication. Using the definition of our fraction syntactic sugar, the right hand side of the above definition is the following diagram

multstart

and we can use diagrammatic reasoning to put it into the form (★):

multiplication

So  r/s · p/q = rp/sq, as we all learned in school. Since we know that multiplication of integers is commutative, this also gives us the commutativity of multiplication for fractions.

Next, let’s do the same thing for addition, transforming the diagram for p/q + r/s into the form (★).

addition

Again, transforming the diagram into (★) using diagrammatic reasoning gives us the formula we all know: p/q + r/s = (sp + qr)/qs . In the fourth step of the proof, we were able to move the qs the wrong way past addition (‡) because we know that both q and s are not zero, so qs is also not zero.

So just by using diagrammatic reasoning, we “discovered” the rules for fraction arithmetic. This is different from the usual treatment: if one defines a fraction to be an equivalence class of pairs (p,q), then multiplication and addition are defined by the formulas we derived. It feels better to derive than to define.

There are a few more things left to do: e.g. show distributivity of multiplication and the fact that we have additive inverses. We will finish the job in the next episode.


 

This weekend I finally got around to reading Liber Abaci by Leonardo of Pisa, aka Fibonacci, translated into English by Laurence Sigler. I’m six chapters in and I’ve really enjoyed it so far. I already knew roughly what was in it, but that’s a bit like saying that I knew that Romeo and Juliet contained a teen suicide before I had to read it at school. A lot of fun, of course, comes from the actual reading, from getting into Fibonacci’s head. It’s a real shame that classic works of mathematics—and you don’t get much more classic than Liber Abaci—don’t get anywhere near as much attention in our culture as classic works of literature or philosophy. Fibonacci’s raw excitement about calculating with the new Indo-Arabic positional notation does not come across anywhere near as vividly in more modern, prescriptive texts.

As I keep reading, I will pull out the bits that I find the most interesting and talk about them on the blog. We start today with fractions, which get a lot of attention in Liber Abaci. Fibonacci used a different notation to the one we all know. Actually, there are several related notations, but the most common one is the following: what Fibonacci would write

\frac{1\ 5\ \ 7}{5\ 6\ 10}3

we would recognise as 3 + 7/10 + 5/6·1/10 + 1/5·1/6·1/10).  The notation is thus read from right to left. It’s a bit like a decimal expansion, in the sense that reading more gives you more information about the number. First, we know the number is larger than 3 but smaller than 4. Then, after reading the next bit of the fraction, we know that it’s a bit more than 7/10ths of the way from 3 to 4, but not quite 8/10ths. Of that final 1/10th, we know it’s a little bit more than 5/6ths. And so forth.

After the quick calculation, this is 284/75, or 359/75, using the evil mixed fraction notation. Fibonacci’s fractions follow the convention that the denominators never get smaller as one reads the fractions left to right: e.g. in the example above 5≤6≤10. Also, by using 10 in the denominators, one can write decimal expansions. For example, 3.14159 can be written \frac{9\ \ 5\ \ 1\ \ 4\ \ 1}{10\ 10\ 10\ 10\ 10}3.

Fibonacci’s fraction notation translates neatly into the graphical notation. For instance \frac{1\ 5\ \ 7}{5\ 6\ 10}3, our example above, is:

fibonaccinotation

It’s easy to pass between the two notations: in the diagram, the numerators go from left to right, following successive copying. The denominators are interleaved with adding on the right.

The reason for Fibonacci’s choice of fraction notation could be that it is the output format of his algorithm—in Chapter 5—for performing division by composite (i.e. non prime) numbers. To prepare, Fibonacci first describes how to divide by prime numbers, and we can recognise this procedure as being equivalent to ordinary long division. Of course, long division works for composite numbers as well, but Fibonacci’s division algorithm means that if the composite has small factors then we can make the procedure simpler: it is usually easier to do long division when you divide by small numbers.

Fibonacci’s writing style is very entertaining: he describes a calculation technique and then solves a number of successively larger problems in full detail; some so large that it’s difficult to think of practical applications, especially since we are talking about medieval Italy. For example, in Chapter 2, he multiplies 12345678 by 87654321 to get 1082152022374638. It’s as if he’s saying: “Ok, so the abacists can probably also do the last example, but look, here’s a much bigger one. Good luck building an abacus big enough!”.

We will go through one of Fibonacci’s small examples from Chapter 5: dividing 749 by 75, illustrating his procedure for dividing by composite numbers with the graphical notation.

749div75

First we factorise 75 into primes—actually Fibonacci is not a stickler about this point and factorises into whatever is the most convenient to divide by—and write them in an increasing order.

749step2

The algorithm works by processing each of the 3, 5, 5 in turn, building up the Fibonacci fraction in the process. We start with the and divide 749 by it, obtaining 249 and 2/3.

749step3

At this point we already have a chunk of the Fibonacci fraction: the 2/3. We can pull it aside for later

part1

and we are left with:

749step4

Next we perform the following calculation:

749step5

First the 5 goes over addition backwards (‡). Then we divide 249 by 5, obtaining 49 and 4/5. Next we use associativity of addition, and pull the 5 back over. At this point we have another chunk of a Fibonacci fraction ready to go, so we can pull it out:

part2

and we are left with

749step6

Now we perform the same steps as in the previous calculation: this is the “loop” in the algorithm. Each time the body of the loop is performed, we get rid of the next number in the decomposition of the denominator. It’s time to process the final 5.

749step7

At this point we do not have any more components of the denominator to consume, so the algorithm terminates. And composing ①, ② and ③ gives us the Fibonacci fraction we were looking for:

result

that the great man himself would write \frac{2\ 4\ 4}{3\ 5\ 5}9, the result of dividing 749 by 75.


 

Fibonacci’s division algorithm is not so useful for us today, since we have computers to do the division for us, and there’s no pressing need to keep the numbers that we are dividing by small. But it is very interesting as an early example of an algorithm tout court; here Fibonacci was probably influenced by al-Khwarizmi. The presentation, using graphical notation, also gave me an opportunity to show off the compositional nature of the graphical language; we could perform the computation in steps, chopping off parts of the diagram that we were finished with, and gluing everything back together at the end. Compositionality is the strong point of the graphical notation, as we will discover time and again.

Continue reading with Episode 26 – Keep Calm and Divide by Zero.

24. Bringing it all together

We are on the home stretch. In this episode we complete the set of equations of Interacting Hopf monoids, the technical name for the equational theory behind graphical linear algebra. Afterwards, we will not see any new equations for some time. Instead, we will explore what this equational theory is good for. In the next few episodes I hope to convince you that I haven’t been wasting your time with all of this!

First—it’s been a while since the last episode—so let’s start with a little reminder of where we are in the story. In the last two episodes we discussed some of the ways that adding and copying interact with their mirror images. The upshot was that we identified the equations for adding

adding

and copying

copying

Both these situations are examples of special Frobenius monoids that we touched on in the last episode, with the additional bone equations. We saw that in any Frobenius monoid we can construct cups and caps, and in graphical linear algebra there are two equations that relate the black (copying) versions with the white (adding) versions. Basically, if you stick an antipode on one, the antipode can disappear as long as the colours are also inverted.

cupscaps

There are just a couple more equations to talk about. They are a bit different from those that we have seen so far because they involve the integers, for which we have constructed a syntactic sugar in earlier episodes.


Let’s turn our minds back to Episode 9 where we defined the sugar for natural numbers. The definition was recursive:

nats

Later, in Episode 18 where we met the antipode generator, we extended the sugar to all of the integers by letting:

negs

For any integer w, our intuition for the behaviour of the w sugar was that the input arrives on the left, gets multiplied by w, and is output on the right.

sugarbeh

The relational interpretation gives a relation of type Num  ⇸  Num that consists of pairs (x, wx) for all numbers x. It’s worthwhile to keep in mind that this is not a definition: it follows from the way we defined the relational interpretation of all of the basic components; the relation for the w sugar then comes out when we compose all of the component relations, following the recursive recipe of the sugar.

Since by now we have all of the mirror image generators, we can also construct the mirror images of the syntactic sugars; i.e.

backwardsscalars

With the functional intuition, it makes sense to think that in these backwards sugars the data flows in the opposite direction: the input arrives on the right and the output exits on the left. But relations don’t care about input-output assignments: given an integer w, the meaning of the backwards sugar is just the relation Num  ⇸  Num with elements of the form (wx, x), where x is any number.

The new equations of this episode tell the story of how, in graphical linear algebra, the forwards sugars interact with their mirror images.


First, let’s consider the situation where two sugars for w, one forwards and one backwards, meet head-on. Like this:

headon

When w=0, the above diagram is

0headon

The relation represented by this consists of all possible pairs of numbers (x, y), in other words, this is the cartesian product Num×Num.

What about the case when w≠0? For the sake of concreteness, let’s consider the case w=2 and work out its relational interpretation.

2cospan

Here we are composing the relation with elements of the form (x, 2x) with the relation that has elements of the form (2y, y), where x and y are arbitrary. After composing these two relations, the result consists of pairs (x, y) that satisfy 2x=2y. If our universe of numbers Num is the integers, the rational numbers (i.e. fractions), the real numbers or the complex numbers then 2x=2y implies x=y, since we can simply cancel out the 2. Which means that the following is true, relationally speaking.

cospaneq2

In fact, the same argument can be repeated for any nonzero integer w. This leads to the following equation, or more accurately, the following equation schema since it can be instantiated for any nonzero integer value of w, which here plays the role of a metavariable.

headoneq

By adding these equations, what we are really doing is assuming that our universe of numbers does not have zero divisors. A zero divisor is a nonzero u, such that there exists a nonzero v with uv = 0. In the integers and many other familiar number systems, including the ones mentioned before, these things don’t exist. We can use this fact—the nonexistence of zero divisors—as follows: if wx = wy then wx – wy = 0, and so w(x-y) = 0 (†). Since w ≠ 0 and there are no zero divisors, (†) implies that it must be the case that x – y = 0, that is x = y.


We considered the case where the w sugars meet head on, so let’s now take a look at what happens when they point outwards, like so:

wspan

Starting with the case w=0, we have:

0span

which gives us the singleton relation consisting of (0, 0).

Now let’s take a look at w=2 again and work out the relation.

2span

Her we are composing relations with elements of the form (2x, x) and (y, 2y), where x and y are arbitrary numbers. Composing the two enforces x=y, so we are left with the relation that has (2x, 2x) as its elements. If Num is the integers then this means that we are looking at a relation that contains pairs of equal even integers. If Num is the rationals, the reals or the complex numbers, then we can obtain all pairs (x, x): this is because, given any number x, we can divide it by 2, and compose (x, x/2) with (x/2,x). So, if division by 2 is something that we can do in our number system Num then the following is true in the underlying relational representation.

2spaneq

Division by non-zero elements is something that can be done in any field, and the rationals, the reals and the complex numbers are three examples. So, if Num is a field then the following equation schema is supported by our relational intuitions.

pointouteq


 

That’s it. We’ve covered all of the equations of graphical linear algebra!  We can now stop talking about intuitions and work purely algebraically, using diagrammatic reasoning within this equational system.

Let’s take a little bit of time to stare at the equations and appreciate them in their full glory. Here they are, all in one place.

ih

In our papers, Filippo, Fabio and I have been calling this system interacting Hopf algebras, or interacting Hopf monoids. The reason for the name is that the system of equations in the Adding, Copying, Adding meets Copying and the Antipode boxes is sometimes called a (commutative) Hopf monoid, as we discovered in Episode 18. The system of equations in the Addingop, Copyingop, Addingop meets Copyingop and Antipodeop boxes is a Hopf monoid again; the mirror image. And the remaining four boxes: Adding meets Addingop, Copying meets Copyingop, Cups and Caps, and Scalars tell the story of how these two Hopf monoids interact.

Altogether, there are quite a lot of equations, but there is a lot of symmetry going on. There’s quite a bit of redundancy as well: some combinations of equations imply the others. I will eventually write an episode that focusses on redundancy, but we are not going to be slaves to Occam’s razor. Let’s be honest with each other; conciseness and minimality was never a strong point of this blog.

The presence of symmetries is an important and interesting issue. Let’s account for two different ones. First, take any equation and invert the colours, swapping black and white; you get another fact, provable in the theory. This means that whatever theorem you prove, using diagrammatic reasoning, its “photographic negative” version is also true. We will take advantage of this symmetry quite a bit: it reduces your workload by half! Second, take any equation and look at in the mirror; it is also an equation of the system. So, whatever fact you prove with diagrammatic reasoning, its mirror image is also a theorem.

I want to leave you with one more observation. We have spent so much time talking about adding and copying… but looking at the equations, which ones tell us that the black structure means copying and the white adding? Well, we have just admitted that inverting colours is a symmetry of the system, so the answer must be… none of them. Copying and adding satisfy the same equations, and interact in the same ways. I still find this fact to be rather beautiful and mysterious.

There are several other, important properties satisfied by this set of equations, but I’ll save them for when they are needed. Most importantly: we know that the theory of Hopf monoids is isomorphic to the prop of integer matrices, so to give a diagram in that theory amounts to writing down a matrix of integers. So what linear algebraic notion does the theory of interacting Hopf monoids correspond to? I will leave you with this cliffhanger and save the explanation for the next episode, where we will also understand the algebra of fractions, diagrammatically.


 

I was in Cali, Colombia at the Javeriana university from the 25th of October to the 1st of November. I presented a tutorial on Graphical Linear Algebra at the ICTAC summer school, gave a talk at the Developments in Computational Models workshop, attended a whole bunch of inspirational talks, met up with some old friends and made some new ones. Everything was superbly organised and a lot of fun. Here’s a photo from my tutorial, where I seem to be demonstrating applications of graphical linear algebra to martial arts.

ictac

My favourite scientific talk was probably a mini tutorial by Jean-Raymond Abrial, also at the summer school, on doing maths with an “engineering” mindset. The idea is to capture the kind of process that goes on in a mathematician’s brain when writing a proof and formalise it (in a software tool!) as an instance of refinement, a software development concept popularised by Abrial and at the core of his B-method. Here’s a photo from that tutorial.

Abrial

Abrial demonstrated this by proving the Cantor-Schröder-Bernstein theorem in the Rodin tool. Here’s what I think, but first a disclaimer: I’m a theorem-prover/automatic-proof-assistant newbie. Also, I have to admit that I’m not a huge fan of the B-method in general: using sets and relations as building blocks is a bit too untyped and too low-level for my taste. Nevertheless, Abrial’s demonstration was intriguing. His discovery and distillation of the process of refinement in a mathematical context was quite compelling, and seemed to closely resemble “real mathematical thinking”, whatever that is.

At some point during the conference I was bragging to some of the attendees that I never suffer from jet-lag. Well, that was true up until now:I wrote about half of this episode after 1:30am, during a series of relatively sleepless nights spread over two weeks after returning from Colombia. I had jet-lag with a vengeance: I spent my days in a sleepy daze and got all my energy after midnight. Thankfully I’ve finally got back to normal over the last few days.

Continue reading with Episode 25 – Fractions, diagrammatically.

23. Frobenius Snakes and Spiders

separator

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

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

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

copyrelel

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

The relational interpretation of discard, copy’s sidekick

discard

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

( x, ★ )

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

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

copying

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


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

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

copyop

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

copyoprel

The second new generator is the backwards discard

discardop

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

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

copyingop


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

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

addingcopyingop


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

bfrob

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

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

froblvars

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

frobrvars

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

frobrel

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

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

special

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

Finally, we also have the bone, in black.

bbone

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

copyingcopyingop


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

Here are the equations of Frobenius monoids again.

frobeniusmonoid

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

epsilon

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

eta

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

snakes

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

snake

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

snakeproof

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


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

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


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

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

cc1

cc2

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

addrel

with the singleton relation

zerorel

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

composed

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

final

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

 The justification for  is symmetric.


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

specialfrobenius

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

bimonoid

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

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

spider1

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

spider2

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

spidersex

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

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


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

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

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

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

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

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

Continue reading with Episode 24 – Bringing it all together.

22. The Frobenius Equation

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

add

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

pairs

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

addexamples

The zero generator

zero

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

{(★, 0)}.        (‡)


 

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

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

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

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


 

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

addrev

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

pairsrev

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

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

{(0, ★)}

which is just (‡) backwards.

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


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

adding

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

addingop

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

copying

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

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


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

frobleft

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

frobleftann

So, the relation consists of pairs

frobleftrel

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

frobleftex

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

frobleftex2

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

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

frobmidrel

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

frobmid

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

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

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

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

frob1

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

frob2

since the calculations involved are clearly symmetric.

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

frob

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

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

frobproof

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

frobmonoid


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

Frobenius

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

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

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

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


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

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

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

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

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

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

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

wbone

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

addingaddingop


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

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

Continue reading with Episode 23 – Frobenius Snakes and Spiders.

21. Functions and Relations, diagrammatically

There is a cute graphical/algebraic way of understanding functions and relations between finite sets, and it deserves to be more widely known. The (formal) diagrams involved closely resemble the (informal) pictures that lecturers often draw when first explaining these concepts to undergraduates.

Although somewhat tangential to the main spine of the story of graphical linear algebra, the diagrammatic treatments of functions and relations give us two additional, simple examples where well-known mathematical structures are characterised as free PROPs. We have already seen two examples: the isomorphisms between Mat and B (Episodes 15 and 16) and between MatZ and H (Episode 19). We will see several more in future episodes.

Now is a good time for a discussion about functions and relations: as we discussed in the last episode, relations play a very important role in graphical linear algebra; this episode thus also serves as a little primer/reminder.


 

First, let’s fix some notation. A bold number n represents a finite set that contains the elements 0, … , n-1. So for example

1 = { 0 },  2 = { 0, 1 },  = { 0, 1, 2 }

and so on. 0 is the empty set, that is, it has no elements.

A function f from m to n, often written f: m → n, is a kind of “rule”; we can evaluate it by giving it an element k in m (i.e. 0 ≤ k < m). The result is denoted f(k) and it is an element in n  (i.e. 0 ≤ f(k) < n).

The definition does not specify how f works, and a function is considered to be equal to another precisely when the two have the same domain and codomain, and act the same way on all possible inputs. This is sometimes called the extensionality property of functions: in more mathematical jargon, if f and g have the same type, we have that:

 ∀x. f(x) = g(x)  implies  f = g           (extensionality)

So the only interesting information about a function is (1) its type and (2) where it takes each of its arguments.


 

I remember that when I first encountered the notion of function, I found it a bit weird. Shouldn’t there at least be some kind of formula or algorithm that calculates it? The functions that I remembered from high school always had a rule, and usually a simple one, say f(x) = x2.

I also remember finding the extensionality property strange at first. I can write two very different computer programs to calculate, say the factorial of a natural number. Extensionality says that they are considered to be the same thing when thought of as functions. So, if you like to think in terms of algorithms, it can be useful to think of a function as a kind of idealised specification, which may have zero or more implementations.


 

There are finitely many functions from any finite set to another. To get the total number of functions from m to n, the crucial insight is that we only care about where the elements from the domain go. We have n choices where to send 0, n choices where to send 1, etc. Since each choice is independent, the total is just n multiplied by itself m times, i.e. nm.

For example, here are pictures of the four functions from 2 to 2.
22functions

Let Fun denote the PROP where the arrows from m to n are functions from m to n. Composition in Fun is composition of functions: if f: m1 → m2 and g: m2 → m3 then their composition, often written g ○ f or f ; g is a function m1 → m3. We just apply one rule after the other:

(g ○ f) (k)  :=  g(f(k))

Pictorially, this means plugging in the output of the first function as the input of the second. So for example, composing the “twist” function with itself is the function

composition

which is the identity, by extensionality, since each argument ends up being taken to itself.

The monoidal product in Fun is similarly simple: it is “stacking one function on top of the other”. Pictorially, this is very simple to visualise, e.g.

funproduct

We can write a somewhat less enlightening formula for this. If f1: m1→n1 and f2: m2→n2 then

funproduct
The permutations of Fun are the obvious things–they are simply traditional permutations, viewed as functions. And it is not difficult to show that all the properties required of PROPs hold.


 

So what is the theory that characterises Fun? It turns out that we have met it already on this blog.

monoid

Let’s call the PROP that arises from the equations above M. Then M and Fun are isomorphic as PROPs. By the way, in this episode we colour all diagram nodes gray: this is so that we don’t get our intuitions confused, since our convention is that the white structure is “adding” while the black structure is “copying”.

The proof that M is isomorphic to Fun is not very difficult, but we will skip it for now. We will probably come back to it when discussing distributive laws, because they also rear up here. For now, to convince you that this has a chance of being true, I’ve drawn the diagrams that represent each of the functions from 2 to 2 that we enumerated previously.

fundiags

See what I meant about the diagrams looking very much like the pictures one draws of functions?

The isomorphism between M and Fun means that to give a function from m to n is the same thing as to give a diagram in M. And two diagrams are equal via diagrammatic reasoning exactly when they define the same function.


 

I took discrete maths course as a first year undergrad. That’s where I first encountered functions in the abstract, set theoretical sense.

Taking discrete maths was a fun experience, and challenging in some ways; even though the computations were not very complicated, it was my first exposure to abstract mathematics. We went through the basics of naive set theory, including the notions of cardinality, functions and relations, then went on to matrices, vector spaces, simple combinatorics, etc. I guess that the recipe is similar in most maths/CS degrees around the world.

Five years ago I found myself having to teach them in a Southampton variant of a discrete maths course. And I found out that teaching discrete maths, which I expected to be a breeze, is actually quite challenging.

In fact, the whole idea of abstract, untyped sets and basic operations on them can be quite strange for students straight out of high school. Once they get the basics though, functions are a breeze. But when we get to relations… there’s always trouble. And no matter how much time I spend on them, it seems that for some people it’s difficult to grasp; even when I keep repeating “remember, a relation is simply a subset of the cartesian product”.

I think that it’s got something to do with psychology: people already have a feel for functions, even before they know the formal definition. Rules are something familiar, it’s that inputs and outputs idea again. The world of relations, in comparison, seems strange and much less intuitive—even if the definitions are extremely simple.


 

If X and Y are sets, then a relation R from X to Y, written R: X ⇸ Y, is a subset of the cartesian product X×Y. What this means is that R is a collection of pairs of the form (x, y) where x is an element in X and y is an element in Y.

Just as with functions, it’s pretty easy to count the total number of relations between finite sets. For example, to figure out the number of relations from m to n, first we observe that the total number of pairs (x,y) where x is in m and y is in n is simply mn, since there are m choices for x and n choices for y. Second, a relation is a subset of the cartesian product, and a finite set of cardinality k has 2k subsets. It follows that there are 2mn such relations.

Let’s draw the relations from 2 to 2, there should be 24 = 16 of them. In the pictorial representation, a line connects x to y precisely when (x,y) is in the represented relation.

relationsann

There is one interesting thing to notice: if you look at the pictures of functions → 2, we can find similar pictures amongst the relations:  (h), (i), (j) and (k). This is because every function from m to n can be thought of as a relation. This relation is sometimes called the graph of the function, and it’s defined to be the subset { ( k, f(k) ) |  0 ≤ k < m }. It’s therefore quite natural to think of functions as special kinds of relations.

The PROP where arrows from m to n are relations from m to n is called Rel. Composition in Rel is, as expected, composition of relations. If you haven’t come across this before, it’s very simple. If R: m1 ⇸ m2 and S: m2 ⇸ m3 then R ; S is the relation m1 ⇸ m3 defined:

R ; S = { (x,z) | there exists y such that (x,y) ∈ R and (y,z) ∈ S } 

Again, pictorially, this is pretty simple to explain: we put the two relations we are composing side by side, and include a connection from the starting point to the end point if there is a path that takes us there. We don’t care about the precise number of paths, as long as it’s greater than 0. Here are some examples:

relcomprelcomp2

relcomp3

As we observed before, every function gives rise to a relation, and it’s not difficult to see that relational composition is compatible with composition of functions: if I compose two functions and look at the resulting relation then it is the same one as if I composed the two functions as relations.

The monoidal product in Rel is also similar to the one in Fun: again, we stack relations on top of each other. For example:

relproduct

The permutations are the graphs of permutations. Again, it’s not difficult to verify that Rel satisfies all the conditions required of PROPs.

The fact that composition and monoidal product are compatible in Fun and Rel can be captured succinctly by the observation that there is a faithful homomorphism Fun → Rel. Obviously this homomorphism is not full, because, in general, not every relation from m to n is the graph of a function.


 

As was the case with functions, we have also seen almost all we need to understand how to characterise relations diagrammatically. The theory that does the job is the following.

special

We have seen most of these equations before. Taking (S) away, it is just the theory B, and we went though all of its equations in detail in Episode 8. We know that B is isomorphic to the PROP Mat of natural number matrices.

The equation (S) is sometimes called the “special” equation. It’s not a great name, but it seems to have stuck so we will use it. If we think in terms of natural number matrices, (S) seems to be saying that

2 = 1

which may look… a bit weird. But, thinking about the graphical interpretation it makes sense. We saw in Episode 9 that the diagrammatic way of understanding natural number matrices has to do with counting paths. Similarly, when composing relations we also have to keep track of paths, it’s just that we are only interested in the Yes or No question “Is there a path?”, and we don’t care about the number. This is one interpretation of (S): it ensures that having 100 paths is the same as having 1 path (but different to no paths).

Again, we won’t prove that the PROP generated by the theory of special bimonoids is isomorphic to Rel. Let’s save that for later. For now, here is a picture of how some of the pictures of relations from before look as diagrams in the theory.

relpics


 

I wrote a part of this episode during my holidays on a train from Yerevan, the capital of Armenia, to Tbilisi, the capital of Georgia. The train trip was quite an experience.

It was an old Soviet relic from I would guess the 60s or the 70s. The weather was very warm, in the high 30s, but fortunately the train was equipped with air conditioning. Unfortunately, it was controlled by a matronly, but friendly, Russian lady who was in charge of the carriage. If she judged that the sun was not shining hard enough, she simply turned the aircon off and walked along the corridor, opening windows. Once the train heated up (way) past the point of comfort, the ritual was reversed.

train

The toilet wasn’t too pleasant and there was no running water. But; surprise! Fast, free public wifi.

One last thing. We are looking for PhD students!

Continue reading with Episode 22 — The Frobenius Equation.