19. Integer Matrices

In the last episode we introduced the fifth and final principal actor of graphical linear algebra, the antipode. This episode’s main task is showing that diagrams built up of the five generators constitute a diagrammatic language for integer matrices and their algebra. We will also discuss a cute example involving the complex numbers.

The cheat sheet for the diagrammatic system H  that includes the antipode is repeated below for easy reference.

cheat

We have already showed that H allows us to extend the syntactic sugar for natural numbers to a sugar for all the integers. We have also verified that the integer sugar obeys the usual algebraic laws of integer arithmetic. In particular, we proved that

minusonesquared

using the equations of H and diagrammatic reasoning: this is just -1 ⋅ -1 = 1, expressed with diagrams.

 


 

Let’s start with an example. The diagram below has two dangling wires on both sides.
iAs such, it ought to denote some 2×2 matrix, and to get the entry in the ith row and jth column we need to look at the paths from the jth dangling point on the left to the ith dangling point on the right.

Before the antipode entered the frame, it sufficed to count the number of paths; the current situation is a little bit more complicated because there are positive paths—those on which the antipode appears an even number of times—and negative paths, those with an odd number. To get the relevant integer entry, we need to take away the negative paths from the positive paths. So, in the very simple example above, we have exactly one positive path from the first point on the left to the second point on the right, and one negative path from the second point on the left to the first on the right. The corresponding matrix is therefore:

imat

Actually, I didn’t choose this matrix at random: it allows us to consider the complex integers (sometimes called the Gaussian integers) and their algebra in a graphical way. We will come back to this after tackling the main topic for today.


 

We want to prove that H is isomorphic to the PROP MatZ of matrices with integer entries. The letter Z is often used to mean the integers, from the German word Zahl meaning number; this notation was apparently first used by Bourbaki.

MatZ is similar to the PROP Mat that we discussed in Episodes 12 and 13: the arrows from m to n are n×m matrices, and just like before composition is matrix multiplication. The monoidal product is again direct sum of matrices.

The proof H ≅ Mat(the symbol  is notation for isomorphic to) is similar, and not much more difficult than the proof, outlined in Episodes 15 and 16, of ≅ MatLet’s go through the details.

First we define a homomorphism of PROPs from H to MatZ. Let’s call it φ, the Greek letter phi. Since both H and MatZ are PROPs, and H is a free PROP built from generators and equations, it is enough to say where φ sends all the generators, and then check that the equations of H hold in MatZ.

It turns out that φ works the same way as θ for all of the old generators. The new part is saying where the antipode goes, and not surprisingly, it is taken to the 1×1 matrix (-1). Like so:

phi

For φ to be well-defined, we need to check that all the equations of  H also hold in MatZ. Fortunately, most of that work was already done for θ, we only really need to check the new equations that involve the antipode. Let’s check the most interesting of these, (A1); we need to calculate whether the following is true:

phia1

This amounts to checking if

phia1t

and it does, indeed, work. The other equations, (A2) through to (A5) are similarly easy computations and we will skip them; but feel free to check!


 

So we have a homomorphism φ: H → MatZ. To show that it is an isomorphism, we will show that it is full and faithful. Fullness—the fact that every matrix has a diagram that maps to it via φ—is the the easy part.

First, we need to check that the sugar that we defined in the last episode works with φ as expected, which is confirmed by the following simple calculation:

negsugarv

Any matrix with integers as entries can now be constructed following the procedure described in Episode 15. We will skip the details, as it is all pretty straightforward! The upshot of the construction is that we can extend the sugar for natural number matrices to a sugar for integer matrices: given an m×n integer matrix U we obtain a sugar

matrixsugar

such that

fullness

This establishes that φ is full.


 

So what about faithfulness, the property that says that whenever two diagrams map to the same matrix then they must already be equal as diagrams?

The trick is to get our diagrams into the form where the

copying comes first, then the antipodes, then the adding  (★)

One way of doing this is to use the theory of distributive laws. Eventually we will go through all of this properly, but for now I will just give you a high-level executive overview. The main insight is that we have three different distributive laws, the first involving the adding and the copying (B1)-(B4), the second the antipode and copying (A2)-(A3), and the third the antipode and adding (A4)-(A5).

The three distributive laws, are compatible with each other in a sense identified by Eugenia Cheng in her paper Iterated distributive laws. The fact that the distributive laws play together well in this way gives us the factorisation (★) that we want. We will discuss Cheng’s results in more detail in a later episode. Incidentally, she has recently written a book about category theory and recipes; I wonder if she knows about Crema di Mascarpone!


We could also try a rewriting argument, taking for granted that the rewriting system described in Episode 16 terminates.  Adding the following rules

rew

it seems that the expanded system ought to terminate also, although I have not yet got around to proving it. These termination proofs are always really messy for a rewriting amateur like me; I would love to hear from an expert about how to do these kinds of proofs in a nice way.


 

Once we know that every diagram can be put in the form (★), the proof of faithfulness is fairly straightforward. We start with those diagrams that have one dangling wire on each side. Every such diagram in the form  (★)  is either the sugar for 0 (a single discard followed by a single zero) or it can be rearranged into the form:

1-1

for some natural number k of wires with one antipode and some natural number l of wires with no antipode. This is because we can always get rid of redundant discards and zeros with (Counit) and (Unit), cancel out multiple antipodes in series using (†), then rearrange, and eat up any annoying permutations with the iterated copy and add sugars.

Once our diagram is in this form we can desugar and repeatedly use (A1), each time destroying one pair of antipode wire and no-antipode wire. Either we end up with no antipodes left, in which case the diagram is equal to a non-negative sugar, or we end up with some number of antipode wires. In the latter case, we can use (A2) to pull out the antipode to the left, obtaining the sugar for a negative integer. We have thus shown that faithfulness holds for the (1,1) case, since every such diagram is equal to some integer sugar.

The general case, where diagrams can have any number of wires on the left and right, comes down to transforming the diagram in matrix form, as explained in Episode 16. This step completes the proof that φ is faithful, and since we already know it is full, it is an isomorphism.


 

So far we have been identifying “numbers” with diagrams of a particular kind; those with one dangling wire on each end. In B this gave us the natural numbers, and in H it gives us the integers. But, as argued in Episode 17, there’s nothing particularly special about (1, 1) diagrams; well, maybe apart from the fact that both in B and H composition for (1,1) diagrams turns out to be commutative. Our obsession with the (1, 1) case is due to history—the traditional way of doing matrix algebra means the concept of ‘number” comes first, then the concept of “matrix”.

The complex numbers are a nice example where it makes sense to consider “numbers” as something different than (1,1) diagrams  A complex number can be written as an expression r + si where rs are numbers and i is a formal entity that behaves like a number, but with the mysterious property i= -1. The numbers and s are sometimes called, respectively, the real component and imaginary components. What is important for us is that to describe a complex number, it suffices to keep track of two ordinary numbers.  Our intuition is that wires carry numbers, so it makes sense to carry a complex number with two wires, the first for the real piece, the second for the imaginary piece.

complexintuition

Now if we multiply a complex number r + si by i, we get (r + si)i = ri + sii = -s + ri. So what was the real component becomes the imaginary component, and the negative of what was the imaginary component becomes the real component. We have a diagram for that, and we have already seen it in this episode:

iint

It thus makes sense to call this diagram i:

idef

Now if we multiply r + si by an integer u, we get (r+si)u=ru + sui. So both the components are multiplied by u. We also have a diagram for that:

scalarsugar2

where on the right hand side we used the sugar for integers from the last episode.

For the rest of this section, to stop the proliferation of the digit 2 that clutters the diagrams, we will just draw the 2 wire using a thicker line, like so:

thick

Now we can do some calculations. First if we compose the diagram for i with itself we get:

isquared

We can also show that i commutes with integers:
icommutes

Following the general pattern of this blog,  we can ask what kinds of diagrams one can construct using the following gadgets.
componentsUsing our standard box of tricks for reasoning about diagrams, it is not difficult to show that the diagrams with one thick wire on each side will, in general, be of the form:

gaussint

Composing two such entities gives us

gaussianmult

which is of course what you’d get if you multiplied out two complex integers (those complex numbers u+vi where u and v are integers). In general, the diagrams that can be constructed from bricks (‡) are matrices with complex integer entries.

So what exactly is going on here? Let’s take a look under the hood.

hood

The result is in matrix form, and corresponds to the 2×2 matrix:

mat

and this is known as one way of representing complex numbers using matrices.

There is one more interesting thing to say here. Let’s take a look at the bizarro of i.

bizarro

So the bizarro of i is -i. It follows that the bizarro of a general diagram constructed in the system (‡) corresponds to the operation known as conjugate transpose in complex matrix algebra.

If you know about quaternions, they can be considered in a similar way. Of course, we are constrained to integer coefficients for now. Not for long ☺.


 

I will give a 3 hour tutorial about graphical linear algebra at QPL ’15 in two chunks on Monday and Tuesday of next week. I’m desperately trying to get the slides done on time. Running this blog has been helpful in that it forced me to develop material, but unfortunately what we have covered so far will only be enough for around the first 30 mins; I should have started this blog back in January!

Continue reading with Episode 20 – Causality, Feedback and Relations.

Advertisements

10. Paths and Matrices

Back in episode 5 I promised to explain how to multiply matrices in a way that you probably have not seen before. I also said that I would do that within 5 episodes, and since this is now episode 10, my hands are tied.

By the way, if you are enjoying this blog, I think that you will also enjoy Dan Ghica’s wonderful series on inventing an algebraic knot theory for kids: Dan uses a similar diagrammatic language to talk about knots, but there’s one major difference between his diagrams and ours: his wires tangle! No wonder, since wires that do not tangle are not particularly useful if you want to construct knots. If you want the “real” reason, it is that his underlying mathematical structure is a braided monoidal category, whereas ours is symmetric monoidal category.

There is one more blog to mention: John Baez has recently been writing about PROPs and linear systems; check it out if you want a sneak preview of one of the star applications of graphical linear algebra! John and his student Jason Erbele developed the theory independently and more or less at the same time as Filippo, Fabio and I. But, apart from the fact that they have different conventions for drawing diagrams, the equational theory that they have developed can be shown to be equivalent to the one we will develop here. It’s super interesting that science is full of temporal coincidences like this; it’s not even the first time that this kind of thing happens to me!


 

 

We start by quashing the fear that the sky may fall on our heads: that is, that somehow graphical reasoning could let us do unreasonable things, like proving that 2 = 3.

Let’s convince ourselves by doing some counting, armed with a hypothetical example. Suppose we have a diagram A, say with two dangling wires on the left and one on the right. Let’s give the first left wire a name, say p and let’s call the right wire q. Suppose also that we’ve cut up the diagram into chunks, like we did with Crema di Mascarpone, and we’ve identified one particular diagram component, called B, with one dangling wire on the left, called r, and one on the right, called s. In the diagram r and s are drawn as dangling from B, but inside of A they may connect to other components.

paths

Now how do we count the number of paths from p to q? We could write down a formula as follows.

pathsformula

This idea generalises easily enough; think about what happens if B has multiple dangling wires on the left and on the right. But what does all this counting tell us?

Well, for one, to count the number of paths from p to q we do not really need to look inside B, we only need to know about the number of paths from each of its dangling points on the left to each of its points on the right. In particular, if I swap B for another diagram, say C, with the same numbers of paths, then the overall number of paths from p to q will not change. The idea of counting paths is compositional.

So let’s now think about diagrammatic reasoning. Clearly stretching or tightening wires doesn’t change the number of paths. Neither does sliding generators along wires. So the only point where things could go wrong is when we use one of our equations. And what happens when we use an equation? We identify a part of the diagram, a component, that corresponds to one side of the equation, and replace it with the other. Here’s our cheat sheet again, for reference:

cheat

The thing to notice is that, in every equation, the path numbers are the same in both left and right hand side. For example, in both sides of (B1) there is one path from every dangling point on the left to every dangling point on the right. In (B2) there are no dangling points on the right, so there are no paths to speak of. In (Unit) and (Counit) there is exactly one path… and so on.

What all of this tells us is that the number of paths from any dangling point on the left to any dangling point on the right is an invariant in diagrammatic reasoning for the theory of adding and copying that we have painstakingly identified so far. So, for instance, starting with the diagram for 3 from the last episode, every diagram equal to it according to diagrammatic reasoning will have precisely three paths from the left dangling wire to the right one. In particular, this excludes the possibility of 2 being equal to 3. Phew!


 

In the last episode we concentrated on diagrams with precisely one dangling wire on the left and right. Let’s now broaden our horizons and draw some more complicated diagrams.

Last time I claimed that every diagram with one dangling wire at each end is equal to one that comes from the natural number syntactic sugar. We will convince ourselves of this fact soon, but for now let’s just believe that this is indeed the case. I want to compound that claim with another: there is also a general shape that describes every diagram with two dangling wires at each end. It is the following, where a, b, c and d are arbitrary natural numbers.

abcd

So, in the diagram above, there are a paths from the first dangling point on the left to the first dangling point on the right, b paths from the second on the left to the first on the right, and so on. All these fun facts almost make you want to write down a nice 2×2 square of natural numbers.

Let’s figure out what happens when we compose two such beasts; it’s an instructive exercise. We will perform a calculation to get the composition to fit into the general pattern described by the diagram above. A word of warning: the diagrams below get a bit complicated, but don’t worry, our calculations will hardly ever be this messy!

2x2pt1

So the first thing that we do is use (B1) twice. Next we apply the (copying) lemma from the last episode four times, to bring a,b,c and d over the copying generators to their right.

2x2pt2Next, we use the (adding) lemma to bring e, f, g and h over the adding generators to their left, and use the (multiplying) lemma to multiply each pair.

The next thing to notice is that there are two ways of getting from the first dangling wire on the left to the first dangling wire on the right; one that goes through ea and a second that goes through fc, as indicated by the red wires in the diagram below.

paths11

The key to simplifying the diagram further is to collect all such compatible paths and add them up. At this point though, it is useful to introduce some additional syntactic sugar that will help us to reduce the complexity of our diagrams.


 

 

The first of our new syntactic sugars looks like the copy generator, but with three dangling wires on the right.

copy3

The reason why it’s a nice syntax is that (CoAssoc) tells us that it does not actually matter in which order we perform the copy operation, we simply end up with three equal copies.

coassoc

We also introduce a sugar that looks like copy, but has four outgoing wires, as follows:

copy4

Again, the syntax is evocative, because (CoAssoc) implies that it doesn’t matter in which order we perform the copying. In particular, all of the following are equal.

pentagon

We can continue this procedure recursively, obtaining a family of sugars indexed by the number of outgoing wires. The recursive case is the following:

sugarrecursive

The base case, for one outgoing wire, is simply the identity. By the way, it is also useful to consider a “copy with zero outgoing wires”, and let this be equal to the discard generator.

Next we can derive two useful laws for dealing with this family of sugars. The first one generalises (CoComm) and says that if I permute two adjacent wires then the sugar can swallow up the twist.

generalisedcocomm

The equation follows from the fact that I can use (CoAssoc) to transform the diagram in such a way so that the twist connects directly to a copy generator, and then use (CoComm). Now, since any permutation whatsoever can be constructed from twist and identity using the two operations of diagrams, it follows that a copy sugar with k outputs followed by any permutation on the k wires is equal to the copy sugar: the sugar can eat up any permutation thrown at it. Simple, right? There is also a rule that generalises (CoUnit): if I cap any of the k outputs with the discard generator then the resulting diagram is the sugar with k-1 outputs. We will not use this second law for now, but it’s useful to keep in mind.

Now, since addition is bizarro copy, we can introduce a similar family of sugars for addition, which satisfy the corresponding bizarro properties that generalise (Comm) and (Unit). To get the idea, just reflect the diagrams in the explanation above and colour the circles white!

Remember the long proof of the inductive step of (copying) from last time? Using this syntactic sugar makes it much simpler. Try it! For now, we will use our sugar to simplify the rest of our current computation.

2x2pt3

After the sugaring step, we can easily rearrange the paths by sliding numbers along wires and getting the sugars to eat up any of the resulting twists. We can then desugar into the form that allows us to apply the (sum) lemma from the last episode.

Now, if you took undergraduate linear algebra then you probably memorised the technique for multiplying 2×2 matrices. Here’s a quick reminder:

\left(\begin{array}{cc} e & f \\ g & h \end{array}\right)\left(\begin{array}{cc} a & b \\ c & d \end{array}\right) = \left(\begin{array}{cc} ea+ fc & eb + fd \\ ga+ hc & gb + hd\end{array}\right)           ①

These numbers look familiar, don’t they?

In fact, the diagrams that we have been drawing all along are actually in 1-1 correspondence with matrices that have natural number entries. Moreover, just as composition of diagrams with one dangling wire at each end corresponds to multiplication of natural numbers, composing diagrams of arbitrary shape can be understood as matrix multiplication. We will go through this in more detail next time.

For now, a quick summary: the diagram

abcd

corresponds to the matrix \left(\begin{array}{cc} a & b \\ c & d\end{array}\right). In general, the number of columns of the corresponding matrix is the number of dangling wires on the left, and the number of rows is the number of dangling wires on the right. Moreover, the entry at row i and column j is the number of paths from the jth wire on the left to the ith wire on the right.

Finally, the composition

composition

corresponds to the matrix obtained by performing the matrix multiplication .

And, as you’ve seen, it all follows from how adding and copying interact!

Continue reading with Episode 11 – From Diagrams to Matrices