The Sum of Subspaces

We know what the direct sum of two vector spaces is. That we define abstractly and without reference to the internal structure of each space. It’s sort of like the disjoint union of sets, and in fact the basis for a direct sum is the disjoint union of bases for the summands.

Let’s use universal properties to prove this! We consider the direct sum , and we have a basis for and a basis for . But remember that the whole point of a basis is that vector spaces are free modules.

That is, there is a forgetful functor from to , sending a vector space to its underlying set. This functor has a left adjoint which assigns to any set the vector space of formal linear combinations of elements of . This is the free vector space on the basis , and when we choose the basis for a vector space we are actually choosing an isomorphism .

Okay. So we’re really considering the direct sum , and we’re asserting that it is isomorphic to . But we just said that constructing a free vector space is a functor, and this functor has a right adjoint. And we know that any functor that has a right adjoint preserves colimits! The disjoint union of sets is a coproduct, and the direct sum of vector spaces is a biproduct, which means it’s also a coproduct. Thus we have our isomorphism. Neat!

But not all unions of sets are disjoint. Sometimes the sets share elements, and the easiest way for this to happen is for them to both be subsets of some larger set. Then the union of the two subsets has to take this overlap into account. And since subspaces of a larger vector space may intersect nontrivially, their sum as subspaces has to take this into account.

First, here’s a definition in terms of the vectors themselves: given two subspaces and of a larger vector space , the sum will be the subspace consisting of all vectors that can be written in the form for and . Notice that there’s no uniqueness requirement here, and that’s because if and overlap in anything other than the trivial subspace we can add a vector in that overlap to and subtract it from , getting a different decomposition. This is precisely the situation a direct sum avoids.

Alternatively, let’s consider the collection of all subspaces of . This is a partially-ordered set, where the order is given by containment of the underlying sets. It’s sort of like the power set of a set, except that only those subsets of which are subspaces get included.

Now it turns out that, like the power set, this poset is actually a lattice. The meet is the intersection of subspaces, but the join isn’t their union. Indeed, the union of subspaces usually isn’t a subspace at all! What do we use instead? The sum, of course! It’s easiest to verify this with the algebraic definition of a lattice.

The lattice does have a top element (the whole space ) and a bottom element (the trivial subspace ). It’s even modular! Indeed, let , , and be subspaces with . Then on the one hand we consider , which is the collection of all vectors , where , , and . On the other hand we consider , which is collection of all vectors , where , , and . I’ll leave it to you to show how these two conditions are equivalent.

Unfortunately, the lattice isn’t distributive. I could work this out directly, but it’s easier to just notice that complements aren’t unique. Just consider three subspaces of : has all vectors of the form , has all of the form , and has all of the form . Then , and , but .

This is all well and good, but it’s starting to encroach on Todd’s turf, so I’ll back off a bit. The important bit here is that the sum behaves like a least-upper-bound.

In categorical terms, this means that it’s a product in the lattice of subspaces (considered as a category). Don’t get confused here! Direct sums are coproducts in the category , while sums are coproducts in the category (lattice) of subspaces of a given vector space. These are completely different categories, so don’t go confusing coproducts in one with those in the other.

In this case, all we mean by saying this is a categorical coproduct is that we have a description of the sum of two subspaces which doesn’t refer to the elements of the subspaces at all. The sum is the smallest subspace of which contains both and . It is the “smallest” in the sense that any other subspace containing both and must contain . This description from the outside of the subspaces will be useful when we don’t want to get our hands dirty with actual vectors.

More on the C-G Eversion

Some people had trouble grabbing the whole 50MB file that I posted, so Scott Carter broke it into pieces. He also included these comments:

The red, blue, and purple curves on the large (distorted) spherical objects at the bottom of each page of the eversion are the preimages of the the folds (color coded of course) and the double decker sets. Since at each time the sphere is immersed it may have double and triple points. Each arc of double points lifts to a pair of arcs on the ambient sphere, and each triple point lifts to three points on the ambient sphere. These lifts are the “decker sets.”

They are obtained via Gauss-Morse codes. Pick a base point and orientation on each curve in a movie. These are chosen
consistently from one still to the next. Label the double points and the optima and read the labels as they are encountered upon a single journey around the curve. The labels, too, are chosen consistently from one still to the next. Write these down for each curve in a movie, and connect the letters in the words as the curves change according to the basic changes that occur in each of the movie scenes.

These curves then are instructions on how to immerse the ambient sphere to create the illustrations.

Sarah’s thesis computes that the fold set is an annulus, the double point set is the connected sum of three projective planes, and the double decker set is the connected orientation double cover: a genus 2 surface.

So here are the pieces:

1. Immersed spheres as movies (2.2 MB)
2. The basic movie moves (3.4 MB)
3. The eversion from the red side to the quadruple point (19 MB)
4. Half of the eversion from the quadruple point halfway to the blue side (24 MB)
5. The other half of the eversion from the quadruple point halfway to the blue side (17 MB)

There’s a glitch in part 4, so I’ll post that as soon as I can.

The Carter-Gelsinger Eversion

I’ve mentioned Outside In before. That video shows a way of turning a sphere inside out. It’s simpler than the first explicit eversions to be discovered, but the simplicity is connected to a high degree of symmetry. This leads to very congested parts of the movie, where it’s very difficult to see what’s going on. Further, many quadruple points — where four sections of the surface pass through the same point — occur simultaneously, and even higher degree points occur. We need a simpler version.

What would constitute “simple” for us, then? We want as few multiple points as possible, and as few at a time as possible. In fact, it would be really nice if we could write it down algebraically, in some sense? But what sense?

Go back to the diagrammatics of braided monoidal categories with duals. There we could draw knots and links to represent morphisms from the monoidal identity object to itself. And topologically deformed versions of the same knot encoded the same morphism. This is the basic idea of the category of tangles.

But if we shift our perspective a bit, we consider the 2-category of tangles. Instead of saying that deformations are “the same” tangle, we consider explicit 2-isomorphisms between tangles. We’ve got basic 2-isomorphisms for each of the Reidemeister moves, and a couple to create or cancel caps and cups in pairs (duality) and to pull crossings past caps or cups (naturality). Just like we can write out any link diagram in terms of a small finite collection of basic tangles, we can write out any link diagram isotopy in terms of a small finite collection of basic moves.

What does a link diagram isotopy describe? Links (in our picture) are described by collections of points moving around in the plane. As we stack up pictures of these planes the points trace out a link. So now we’ve got links moving around in space. As we stack up pictures of these spaces, the links trace out linked surfaces in four-dimensional space. And we can describe any such surface in terms of a small collection of basic 2-morphisms in the braided monoidal 2-category of 2-tangles. These are analogous to the basic cups, caps, and crossings for tangles.

Of course the natural next step is to consider how to deform 2-tangles into each other. And we again have a small collection of basic 3-morphisms that can be used to describe any morphisms of 2-tangles. These are analogous to the Reidemeister moves. Any deformation of a surface (which is written in terms of the basic 2-morphisms) can be written out in terms of these basic 3-morphisms.

We can simplify our picture a bit. Instead of knotting surfaces in four-dimensional space, let’s just let them intersect each other in three-dimensional space. To do this, we need to use a symmetric monoidal 3-category with duals, since there’s no distinction between two types of crossings.

And now we come back to eversions. We write the sphere as a 2-dimensional cup followed by a 2-dimensional cap. Since we have duals, we can consider one side to be “painted red” and one side “painted blue”. One way of writing the sphere has the outside painted red and the other side is painted blue. An eversion in our language will be an explicit list of 3-morphisms that run from one of these spheres to the other.

Scott Carter and Sarah Gelsinger have now created just such an explicit list of directions to evert a sphere. And, what’s more, they’ve rendered pictures of it! Here, for the first time in public, is a 50MB PDF file showing the Carter-Gelsinger eversion.

First they illustrate the basic pieces of a diagram of knotted surfaces (pp. 1-4). Then they illustrate the basic 2-morphisms that build up surfaces (pp. 5-6), and write out a torus as an example (p. 7). Then come a few more basic 2-morphisms that involve self-intersections (pp. 8-9) and a more complicated immersed sphere (pp. 10-11). Each of these is written out also as a “movie” of self-intersecting loops in the plane. Next come the “movie moves” — the 3-morphisms connecting the 2-morphism “movies” (pp. 12-17). These are the basic pieces that let us move from one immersed surface to another.

Finally, the eversion itself, consisting of the next 79 pages. Each one consists of an immersed sphere, rendered in a number of different ways. On the left is a movie of immersed plane curves. On the top are three views of the sphere as a whole — a “solid” view on the right, a sketch of the double-point curves in the middle, and a “see-through” view on the left. The largest picture on each page is a more schematic view I don’t want to say too much about.

The important thing to see here is that between each two frames of this movie is exactly one movie move. Everything here is rendered into pictures, but we could write out the movie on each page as a sequence of 2-morphisms form the top of the page to the bottom. Then moving from one page to the next we trace out a sequence of 3-morphisms, writing out the eversion explicitly in terms of the basic 3-morphisms. As an added bonus, there’s only ever one quadruple point — where we pass from Red 26 to Blue 53 — and no higher degree points.

I’d like to thank Scott for not only finishing off this rendering he’s been promising for ages, but for allowing me to host its premiere weblog appearance. I, for one, am looking forward to the book, although I’m not sure this one will be better than the movie.

[UPDATE] Some people have been having trouble with the whole 50MB PDF (and more people might as the Carnival comes to see this page. Scott Carter broke the file up into five pieces, and I’ve put them up here in a new post. There’s a glitch in part 4, but I’ll have that one up as soon as I can.

The Splitting Lemma

Evidently I never did this one when I was talking about abelian categories. Looks like I have to go back and patch this now.

We start with a short exact sequence:

A large class of examples of such sequences are provided by the split-exact sequences:

where these arrows are those from the definition of the biproduct. But in this case we’ve also got other arrows: and that satisfy certain relations.

The lemma says that we can go the other direction too. If we have one arrow so that then everything else falls into place, and . Similarly, a single arrow so that will “split” the sequence. We’ll just prove the first one, since the second goes more or less the same way.

Just like with diagram chases, we’re going to talk about “elements” of objects as if the objects are abelian groups. Of course, we don’t really mean “elements”, but the exact same semantic switch works here.

So let’s consider an element and write it as . Clearly lands in . We can also check

so . That is, any element of can be written as the sum of an element of and an element of . But these two intersect trivially. That is, if and then , and so . This shows that . Thus we can write every uniquely as .

Now consider an element . By exactness, there must be some so that . That is, we have a unique with . This shows that . It’s straightforward to show that also . Thus we have split the sequence: .

The Category of Matrices IV

Finally, all the pieces are in place to state the theorem I’ve been driving at for a while now:

The functor that we described from to is an equivalence.

To show this, we must show that it is full, faithful, and essentially surjective. The first two conditions say that given natural numbers and the linear transformations and the matrices over are in bijection.

But this is just what we’ve been showing! The vector spaces of -tuples come with their canonical bases, and given these bases every linear transformation gets a uniquely-defined matrix. Conversely, every matrix defines a unique linear transformation when we’ve got the bases to work with. So fullness and faithfulness are straightforward.

Now for essential surjectivity. This says that given any finite-dimensional vector space we have some so that . But we know that every vector space has a basis, and for it must be finite; that’s what “finite-dimensional” means! Let’s say that we’ve got a basis consisting of vectors.

Now we just line up the canonical basis of and define linear transformations by and . Remember that we can define a linear transformation by specifying its values on a basis (which can all be picked independently) and then extending by linearity. Thus we do have two well-defined linear transformations here. But just as clearly we see that for any we have

and a similar equation holds for every -tuple in . Thus and are inverses of each other, and are the isomorphism we need.

This tells us that the language of linear transformations between finite-dimensional vector spaces is entirely equivalent to that of matrices. But we gain some conceptual advantages by thinking in terms of finite-dimensional vector spaces. One I can point to right here is how we can tell the difference between a vector space and its dual. Sure, they’ve got the same dimension, and so there’s some isomorphism between them. Still, when we’re dealing with both at the same time they behave differently, and it’s valuable to keep our eye on that difference.

On the other hand, there are benefits to matrices. For one thing, we can actually write them down and calculate with them. A lot of people are — surprise! — interested in using mathematics to solve problems. And the problems that linear algebra is most directly applicable to are naturally stated in terms of matrices.

What the theorem tells us is that none of this matters. We can translate problems from the category of matrices to the category of vector spaces and back, and nothing is lost in the process.

The Category of Matrices III

At long last, let’s get back to linear algebra. We’d laid out the category of matrices , and we showed that it’s a monoidal category with duals.

Now here’s the really important thing: There’s a functor that assigns the finite-dimensional vector space of -tuples of elements of to each object of . Such a vector space of -tuples comes with the basis , where the vector has a in the th place and a elsewhere. In matrix notation:

and so on. We can write (remember the summation convention), so the vector components of the basis vectors are given by the Kronecker delta. We will think of other vectors as column vectors.

Given a matrix we clearly see a linear transformation from to . Given a column vector with components (where the index satisfies ), we construct the column vector (here ). But we’ve already established that matrix multiplication represents composition of linear transformations. Further, it’s straightforward to see that the linear transformation corresponding to a matrix is the identity on (depending on the range of the indices on the Kronecker delta). This establishes that we really have defined a functor.

But wait, there’s more! The functor is linear over , so it’s a functor enriched over . The Kronecker product of matrices corresponds to the monoidal product of linear transformations, so the functor is monoidal, too. Following the definitions, we can even find that our functor preserves duals.

So we’ve got a functor from our category of matrices to the category of finite-dimensional vector spaces, and it preserves all of the relevant structure.

The Category of Matrices II

As we consider the category of matrices over the field , we find a monoidal structure.

We define the monoidal product on objects by multiplication — — and on morphisms by using the Kronecker product. That is, if we have an matrix and an matrix , then we get the Kronecker product

Here we have to be careful about what we’re saying. In accordance with our convention, the pair of indices (with and ) should be considered as the single index . It’s clear that this quantity then runs between and . A similar interpretation goes for the index pairs .

Of course, we need some relations for this to be a monoidal structure. Strict associativity is straightforward:

For our identity object, we naturally use , with its identity morphism . Note that the first of these is the object the natural number , while the second is the matrix whose single entry is the field element . Then we can calculate the Kronecker product to find

and so strict associativity holds as well.

The category of matrices also has duals. In fact, each object is self-dual! That is, we set . We then need our arrows and .

The morphism will be a matrix. Specifically, we’ll use , with and both running between and . Again, we interpret an index pair as described above. The symbol is another form of the Kronecker delta, which takes the value when its indices agree and when they don’t.

Similarly, will be an matrix: , using yet another form of the Kronecker delta.

Now we have compatibility relations. Since the monoidal structure is strict, these are simpler than usual:

But now all the basic matrices in sight are various Kronecker deltas! The first equation reads

which is true. You should be able to verify the second one similarly.

The upshot is that we’ve got the structure of a monoidal category with duals on .

The Category of Matrices I

What we’ve been building up to is actually the definition of a category. Given a field we define the category of matrices over .

Most of our other categories have been named after their objects — groups are the objects of , commutative monoids are the objects of , and so on — but not here. In this case, matrices will be the morphisms, and the category of matrices illustrates in a clearer way than any we’ve seen yet how similar categories are to other algebraic structures that are usually seen as simpler and more concrete.

Down to business: the objects of will be the natural numbers , and the morphisms in are the matrices. That is, a morphism is a collection of field elements where runs from to and runs from to .

We compose two morphisms by the process of matrix multiplication. If is an matrix in and is a matrix in , then their product is a matrix in (remember the summation convention).

The category of matrices is actually enriched over the category of vector spaces over . This means that each set of morphisms is actually a vector space over . Specifically, we add matrices of the same dimensions and multiply matrices by scalars component-by-component.

We have yet to speak very clearly about identities. The axioms of an enriched category state that for each object (natural number) there must be a linear function . Because of linearity, this function is completely determined by its value at : . We must pick this matrix so that it acts as an identity for matrix multiplication, and we choose the Kronecker delta for this purpose: . That is, we use an matrix whose entries are if the indices are equal and otherwise. It’s straightforward to check that this is indeed an identity.

Other properties I’ve skipped over, but which aren’t hard to check, are that matrix multiplication is bilinear and associative. Both of these are straightforward once written out in terms of the summation convention; sometimes deceptively so. For example, the associativity condition reads . But remember that there are hidden summation signs in here, so it should really read:

so there’s an implicit change in the order of summation here. Since we’re just doing finite sums, this is no problem, but it’s still worth keeping an eye on.

Category Theory Isn’t Useless After All!

Today on the arXiv, we find a posting of an old paper, which uses spans of “reflexive graphs” to give an algebraic framework for describing partita doppia — double-entry bookkeeping.

Now I need to find a follow-on to this paper and start applying to those financial math jobs.

Drafting a Paper

Long-time readers may remember that back in September I went to a conference at the University of Texas at Tyler. Well, it turns out that the AMS wants to publish a proceedings of the conference. So I’m trying to throw together a paper on the stuff I was talking about.

As I’m doing so, I’m recognizing that one part of my original talk — the whole business about anafunctors — isn’t quite ready for prime-time, and the whole thing hangs together better without it. And this brings up the design philosophy I talked about recently. In this case, writing the smaller paper first is being sort of forced on me by a short deadline.

Still, it’s crunch time, and I’m trying to crank this paper out while also teaching, applying for jobs, and dealing with car troubles you wouldn’t even believe. I don’t really feel like working up the next post in the calculus series today, and so I thought I’d toss up an alpha version of the paper. I’ll keep tweaking it, and replacing the version here as I finish more chunks, until I get to a beta version, which I’ll update here and post to the arXiv.

One particular note on the incompleteness: I haven’t even started writing the introductory section or the abstract yet. I’m finding that I tend to do better if I just dive into the mathematics and then come back later to say what I said.

And finally: it looks like I’ll be talking about this stuff at the University of Pennsylvania on March 19. Mark your calendars!

[UPDATE] 02/26: Still sans abstract and intro, but with all mathematical content there, I present a new version. Bibliography suggestions are particularly appreciated (thanks Scott).

[UPDATE] 03/04: Now with the abstract and introduction, a beta version. Bibliography suggestions would still be appreciated.