Atlas in the Notices

I just got the latest issue of the Notices of the American Mathematical Society today, and was excited to find in it an article by David Vogan on the Atlas Project. In particular, there’s a lot of information on how the programming and computation ran. I found it sort of interesting, but I know there are people out there who just love tweaking programs and squeezing that extra bit of performance out. Most of the time it really doesn’t matter, but the Kazhdan-Lusztig polynomials for split are one of those few calculations that are just so unbelievably massive that you have to use every trick you can just to get the damn thing to fit in the computer.

Oh, and if any of you code junkies wants to Slashdot that article, I’d appreciate a “heard it on The UM” nod

Diagram Chases Done Right

Blatantly stealing my title from Axler’s (in)famous book, I’m going to take the lemmas from last time and show that we actually can prove things in arbitrary abelian categories using “diagram chases”.

Remember that this technique started in categories of modules where the objects are actually structured sets with elements, but we don’t want to assume that our objects are like this. When we were dealing with enriched categories, we talked about elements of the underlying set by looking at arrows from the monoid identity object, but we don’t have that floating around either, since our abelian category might not be monoidal.

Instead, we’ll generalize even further to “members” of an object. We call any arrow with codomain a member of and write . Now we say that two such arrows are equivalent — and write if there are epimorphisms and with . Clearly the relation is reflexive (use the identity on the source of ) and symmetric. We can see transitivity by considering the following diagram:

We assume that there are epimorphisms and in the upper-right so that , and epimorphisms and in the lower-left so that . Now we can pull back the upper left square to get and , which are epic by the second lemma last time. The compositions and are then the epimorphisms we need to show that .

The members of behave sort of like an abelian group in that we have a “zero” member , and each arrow has a negative in its hom-set. It’s straightforward to show that if then and any zero morphism is equivalent to the zero member. Also, any arrow sends a member to a member , so it behaves like a function on sets.

Now we have the following elementary rules for diagram chases, intended to parallel the rules we’d have if we were actually talking about a category of modules:

• is monic if and only if for all , implies
• is monic if and only if for all , implies
• is epic if and only if for all there is an with
• is zero if and only if for all ,
• Given and , the sequence is exact at if and only if , and for every with there is an with
• Given and with there is a with . Further, any with has and any with has .

The first two rules are just the definition of a monic arrow over again, and the fourth is just the definition of zero morphisms. For the third rule, if is epic then we can pull back along to find and with , which implies . Conversely, if is not epic then the member is not of the form for any .

Rule six seems complicated, but it just replaces subtraction of elements. Since there are epimorphisms so that . Then all the conclusions hold by taking .

Finally, in rule five we can take the canonical factorization . If the sequence is exact at then is the kernel of , so for any with we have . Now we can pull back along to get and with and epic. We see that , so , as desired. Conversely, if this holds for all we can take the kernel of so that . Then there is some with , and thus there are epimorphisms with . This implies that factors through , and thus that as subobjects of . But implies that , and the sequence is exact.

We can use these rules to replace everything we’d normally want to do with elements of modules. Just write everything out as if you were looking at a category of modules so you can take elements and chase them around the diagram. Then replace “element of” with “member of”, “equals” with “equivalent”, and so on. The rules above show that the semantics of membership and equivalence in arbitrary abelian categories are exactly the same as those of elementhood and equality in the category of abelian groups, and so everything carries over.

This approach has a significant advantage over the other major approach, which is to show that every abelian category can be faithfully embedded as a subcategory of a module category. In that case we can work with the image of the embedding functor, where every object is a module and every morphism is a homomorphism, and the naïve semantics of diagram chases applies. However it takes all the machinery of an embedding theorem, which might be a ways off. Here, we don’t have to use anything nearly so fancy. We just say the exact same words as we would in , but give them a different meaning to apply to our different context.

Next time I’ll actually do a diagram chase with the new semantics to illustrate how smoothly it works.

Short Exact Sequences

Last time we defined a short exact sequence in an abelian category to be an exact sequence of the form . These are the objects of a category , whose morphisms are triples of arrows , , making the two squares commute in the diagram:

The category is clearly enriched over .

As a first step into this category, we show that if and are both monic, then is monic as well. First let’s see how to do this in . We want to show that if for that . Now , but we assumed to be monic, so — . Since the top row is exact this means , and so there’s an so that . Now , but both and are monic. Thus , and as well.

That’s the normal way to proceed, and we call it a “diagram chase”. Just start with an element on the diagram at and “chase” it around the diagram. But this only works if is made up of structured sets, and we haven’t assumed that at all! We need to work a tiny bit more abstractly and look only at the arrows.

So let’s take . Now . Since is monic, we have . And thus factors uniquely through as . Now . Since and are assumed monic, , and so and is monic.

Either way, we can dualize the whole theorem to say that if and are epic, then is epic too. Together, these results are called the “short five lemma”.

Here’s another lemma, based on this diagram:

The square on the right is a pullback, and I say that if is epic then is too. On the left is the kernel of , and I say that it factors through the kernel of to make the diagram commute.

Let’s just skip the chase and go directly to the general picture. As usual, pullbacks can be defined by products and equalizers. We get the product as , which then has two arrows to : and . And we find their equalizer by taking the kernel of their difference: . Then and .

Now under the assumption on , we know that is epic. Indeed, if then . But since is assumed epic, . Supposing now that , we see that , so factors through the cokernel of , which is . That is, , and so . Since is epic, , and so . Thus is epic.

As for the other assertion, the pair of arrows and satisfy , and so there is a unique arrow by the universal property of the pullback. In particular, . On the other hand, given any other with we have , so factors uniquely through as . Then and . But since the arrow factoring through a pullback is unique we must have . So really is the kernel of , as asserted.

Images, Coimages, and Exactness

By the first isomorphism theorem, we know that any morphism in an abelian category factorizes as with , and is epic. Since is monic, exactly when . That is, the kernel of is isomorphic to the kernel of . Then since is epic, . So there’s a sort of a symmetry here between the monic and the epic in the factorization of .

Now let’s consider another morphism and a pair of morphisms so that . Then we can factorize each of and as above to find . Then there is a unique such that and .

To see this, set . Then so . Thus factors uniquely through as . Then . And so since is epic we have .

Now, we’ll regard and as objects in the arrow category . Then the pair is a morphism from to . Similarly, the triangle is an object of , and the triple is a morphism in this category.

What the above proof shows is that any object in can be assigned an object in , and that any morphism in can be assigned one in . Clearly this assignment amounts to a functor. In particular, if we start with the identity pair we must have an isomorphism for , and thus any two factorizations are isomorphic.

Now, given this unique (up to isomorphism) factorization, we can define the image and coimage of as and . Thus as expected the image of is a subobject of its target, and the coimage is a quotient object of its source.

Now that we have defined images and coimages we can define what it means for a composable sequence of morphisms to be exact. Let’s say we have and . Both and are subobjects of , and we say that the pair is exact at when . We say that a longer string of composable arrows is exact if it is exact at each object inside the string.

As a special case, we say the sequence is short exact if it is exact. That is, if we let the two outer arrows be the unique such, let , and let , then the sequence is short exact if , , and . If we drop the left we call the sequence short right exact, and short left exact sequences are defined similarly.

Now the factorization of gives rise to two short exact sequences: and . Then because the objects of the coimage and the image are isomorphic, we can weave these two sequences together at that point. In fact, we did something just like this back when we talked about exact sequences of groups!

An -functor is called left exact when it preserves all finite limits. In particular it preserves kernels — that is, left exact sequences. Since any -functor preserves biproducts, preserving kernels is enough to preserve all finite limits. Similarly, a right exact functor is one which preserves all finite colimits, or equivalently all cokernels — right exact sequences. Finally, a functor is exact if it is both left and right exact.

The First Isomorphism Theorem (for Abelian Categories)

We had versions of the first isomorphism theorem for groups, rings, and modules. Now we’ll do it in a more general setting. We’re going to use it in our study of abelian categories, but it works in all three of the above cases.

As we said last time we talked about abelian categories, we really just use that our categories all have a zero object, kernels, and cokernels. We’ll work with that for now, and note that these properties hold in particular for abelian categories.

Now, if is a category with a zero object, kernels, and cokernels, then any arrow of has a factorization , where . This holds because , and by the universal property of kernels there is a unique with .

On the other hand, if we have another factorization with also a kernel, then we have a unique so that the following diagram commutes.

That is, the canonical factorization described above is in some sense the universal such factorization. Furthermore, if has equalizers and every monic in is a kernel, then is epic. In particular, these hypotheses are all satisfied for abelian categories. This is the isomorphism theorem — that every arrow factorizes essentially uniquely as the composition of an epic and a monic .

We prove this by considering the following diagram:

We draw . Since is itself a kernel, we see that . We also draw . Now , so . By the universal property of , there is a unique so that . And then , so factors uniquely through — there is a unique with . Furthermore, , and so since is monic we have . This proves that the first diagram given above commutes.

Now we have to show that is epic under the additional hypotheses. Let’s say that we have a parallel pair of arrows and with . then factors uniquely through the equalizer — for some unique . Then . Now is monic, so (by the new hypotheses) it’s a kernel. By the first part of the theorem we have a unique with , and thus . Since the monic has a right inverse, it’s an isomorphism. Since was picked as the equalizer of and , . And so is epic.

Problems with Ordered Linear Spaces — Solved!

Okay, there’s some sort of problem with these things. I defined the category , showed some properties, and tried to prove a theorem. Here I want to collect what I’m sure about and what I’m not sure about.

The biproduct, exponential, and monoidal product structures are all correct. We have something natural defined by , which seems sort of like a categorical dual, but maybe not.

What I tried to prove is that in general is not isomorphic to . But as Todd pointed out, if is a dual then we have an adjunction

but the definition of an exponential is an adjunction

and functors with the same left adjoint are naturally isomorphic.

So, if is a categorical dual, then is naturally isomorphic to , and there’s something wrong with the proof I offered that it isn’t.

On the other hand, if is not naturally isomorphic to , then is not a categorical dual. I haven’t found an example of a cone that has no positive basis with a positive dual basis, and I’m losing faith in the example I thought I’d sketched that even had one positive basis whose dual basis was not positive.

So one of these “proofs” is wrong — which is it?

[UPDATE]: Well, I figured it out. There’s a problem with the duals.

Start with any cone , and pick a positive basis in the cone. Now we can simplify our lives by moving to a cone with a particularly nice positive basis. We know that there’s a linear isomorphism taking the vector space to the free vector space , and taking our chosen basis of to the canonical basis of . We induce a cone on by saying if and only if . So without loss of generality our positive basis consists of the “coordinate vectors” , and the dual basis consists of the coordinate projections.

Now these vectors cut out a classical subcone of , and the positive vectors are exactly those in the positive orthant. If is not exactly this classical cone, then there exists some positive vector in outside the positive orthant. That is, some component of will be negative. But then that coordinate projector will send to a negative number, and so cannot be a positive linear functional. Thus the dual basis of a positive basis can only itself be positive if is classical.

So what does this mean? Just that is only the categorical dual to when is classical. Thus only in this case do we have an adjunction , and so only in this case do we find naturally in .

What happens for non-classical cones? Well, is a right adjoint, and so its evaluation transformation is couniversal. Since we also have a natural transformation (evaluate the second factor on the first) it must factor through the couniversal. That is, there is an arrow , which is the one we earlier calculated explicitly. But it’s not generally an isomorphism.

New Blath!

Well, as today’s main post sort of died, I really should post some good news. Jeff Morton has started a weblog! It’s a great coincidence, because just yesterday I was mentioning his use of spans in categorifying the quantum harmonic oscillator during my talk. I see good things coming from this.

Ordered Linear Spaces III

[UPDATE]: This whole post is badly-founded as it stands, because on further reflection it seems that does not have duals. See the post in the first link and its update for an explanation.

We’re on a roll with our discussion of ordered linear spaces. So I want to continue past just describing these things and prove a very interesting theorem that Howard and I hit upon. It may have been known before, but what I’ll say here is original work to the two of us.

Whenever we have a (symmetric) monoidal closed category with duals, we have an arrow . Indeed, we have an arrow

where we use symmetry on the left, the counit of the dual in the middle, and the left unit isomorphism on the right. By the closure adjunction, this arrow from to corresponds to an arrow from to .

Sometimes this arrow is an isomorphism. In the category of finite-dimensional vector spaces over a field, for instance, this property holds. It’s nice when this happens because then we can get a good understanding of every morphism in . But it turns out that it doesn’t hold in , even though ordered linear spaces are built on finite-dimensional vector spaces. And the exact way it fails is very interesting.

Let’s take a positive element of . This is a finite sum , where the are positive vectors in and the are positive linear functionals on . I’m writing the index as a superscript for a technical reason some of you might know, but it’s not important if you don’t. Anyhow, recall that a linear functional is positive if for all . Then if we feed a positive element of , we evaluate to find , which is a linear combination of positive vectors in with positive coefficients, and thus is positive. So corresponds to a positive map as it should. This is just the arrow described above, now in the special case of .

But let’s see what this means for the image of the function described by . The vectors are all inside the positive cone in , and so they span a classical subcone of . Then the image of must be inside this subcone. This imposes an extremely strong condition on and , which turns out to also be sufficient: if and only if the positive image of every positive function from to is contained in a classical subcone!

I think that we can push on from here to show that this implies that either or is classical, but I don’t know of a proof of this conjecture yet.

Okay, so we don’t have duals. So this day’s not a total loss I’ll throw this out to the group:

The construction we gave obviously exists and is natural in some sense. We define a “dual” cone as before. That is, a linear functional is considered positive if it sends the whole positive cone from to the positive ray in . Now the question is, in what sense is this a “dual”?

Ordered Linear Spaces II

Since I was a little slow posting things at the end of last week due to the conference, I’ll continue my discussion of ordered linear spaces with this observation: because each ordered linear space is a vector space with extra structure, the category inherits a lot from the category of vector spaces.

For one thing, given a pair of vector spaces and , we can take their direct sum . Now if each of them has an identified cone of positive vectors, we can set up a cone on the direct sum by insisting that the structural maps , , , and are positive. Let’s write these as logical statements and see what they imply:

• If then .
• If then .
• If then .
• If then .

The projections tell us that if a pair is positive in , then each of its components is positive in its respective vector space. On the other hand, the injctions tell us that if each component of a pair is positive, then each of their images in must be positive, and so the sum of the images — the pair itself — must be positive. That is, a pair is positive if and only if each of its components is positive. This uniquely specifies the cone on the direct sum so as to make it a biproduct in .

This category is also monoidal closed. There are various natural monoidal structures we could use, so we’ll start with the exponential this time. Now, in we have an exponential — is the vector space of all -linear maps from to . Is there a natural cone in this vector space? Indeed there is! It’s just the cone of all positive maps! That is, if and only if implies .

So what’s the tensor product? Well, we start with the vector space tensor product and try to find a cone. This should give an adjunction . So let’s read this as another logical statement. A linear map is positive (and thus in ) if

Expanding this condition on , we get that is positive if

But is the usual closure adjunction in the category of vector spaces, turning a function-valued function of one variable into a vector-valued function of two variables. And we want every positive map from to to correspond to exactly one in just this way. Thus the cone on that makes the tensor product for into a left adjoint to the exponential is that of all finite sums of tensor pairs of positive elements. That is, if with all the and positive in their respective cones. As an exercise, verify that this tensor product is also symmetric.

The monoidal identity has the base field as its underlying vector space. For its cone, take the positive ray. It’s straightforward to check that . As usual, we use the tensor identity to represent the “underlying set” functor. That is, we define the underlying set of a cone by . Such a positive map is a linear map from to that picks out a positive point , and there is exactly one such map for each positive point in . That is, the underlying set is exactly the set of points in the positive cone of . As a check, note that this means the underlying set of is the set .

As if that weren’t enough, has duals! Indeed, we have a cone in the dual vector space defined by if and only if for all . Or in other words, . We just need natural maps and to make this really a categorical dual. The first of these is evaluation — . The second one picks out an identified element in . How can we do this?

Well, in a vector space we can pick a basis of and get a dual basis of defined so that is if and otherwise. Then we can sum up . It’s well-known (though I haven’t shown it yet) that this sum doesn’t depend on which basis we picked! That is, it’s just a property of the vector space .

Now if has a cone, we know we can find a positive basis. And then it turns out the dual basis will be positive in the dual cone. Putting these together, it turns out that the above element is always in the positive cone of , even if we didn’t start by picking a positive basis! All we need is the fact that this sum can be written as a sum of positive tensor pairs.

From here, it’s an easy calculation to verify that and satisfy the two required equations, making the dual of .

[UPDATE]: Okay, that last bit doesn’t seem to work. The dual basis is not in general positive. That was a fact that I quoted from my conversation with Howard, so I think he made a mistake there. It’s my own fault for not verifying it, but now I’ve found an example where it fails. I’m working on finding an example where it fails for all positive bases. As it stands, does not in general have duals.

Them’s the breaks when you’re working on the edge of what you know.

Ordered Linear Spaces I

I saw a really great talk today by Howard Barnum of the Los Alamos National Laboratory. It dovetails wonderfully with what I’ve been talking about here, and I think I can help him by bringing my categorical inclination to bear on his subjects. I’ll omit the motivation he was using because I can’t really explain the background, but it makes for a great example of a category.

We define the category of “ordered linear spaces” by starting with a totally ordered field . If you know what the real numbers are (I still haven’t defined them here) use them, but otherwise you can get away for now with rational numbers. We consider the category of finite-dimensional vector spaces over and -linear maps between them.

Now an ordered linear space is a finite-dimensional vector space equipped with a certain partial order, compatibly with the linear structure. We can do this by specifying a “cone” of vectors to consider as being bigger than . Then exactly when . We require that if then so is each with in the field . From this we can tell that if with , , and , then by the transitive property of partial orders. That is, the cone contains the line segment between any two of its points. In this situation we say it is a “convex set”. Finally, we require that we can find a positive basis of our vector space — one consisting of positive vectors. This is an ordered linear space, which is an object of . Because the order is specified by its cone, we often call such a space a “cone”.

A morphism in our category is just a linear function from one ordered linear space to another that preserves the partial order. That is, we call a linear function “positive” if whenever in then in . In other words, it sends the one cone into the other. An isomorphism is an isomorphism of vector spaces which identifies the two cones — the must be the “same shape”, up to a linear transformation. A subcone — the image of a monomorphism — works out to be exactly what it seems like it should be: a convex cone that fits inside another cone.

There’s a functor from the category of finite sets to . We start with a finite set and construct the free vector space on it. We define the cone to be all those vectors with all components positive. For reasons related to our motivation, we call these cones — and any cone equivalent to one of them — “classical”. The linear transformation induced by a function between finite sets is clearly positive, and so this is indeed a functor. It’s not hard to see that the image of any morphism from a classical cone is again classical, and thus the classical cones form a full subcategory of .

There’s a lot more to be said about these things, but I’ll leave it here for now.