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.