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.

Sunday Samples 35

As I wrap up my time in Texas, I feel like pulling out a bit of country. Also, I feel like getting the hell out of here and back to Louisiana, where for some reason there’s not as much mold to bother me. Maybe it’s just that the Ramada is dirty. Anyhow, I was fine for a few days, but now my head is stuffed and achy from clogged sinuses.

So let’s put country music together with that bleary, morning-after feeling. From their 1996 album 12 Golden Country Greats, Ween’s “Help Me Scrape the Mucus Off My Brain”.

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.

Newton Fractals

As soon as I’m done teaching today, I’m heading on the road to scenic Tyler, TX for the Conference on Representation Theory, Quantum Field Theory, Category Theory, Mathematical Physics and Quantum Information Theory. And so something light, that I actually presented to my students last week.

Many of you may be familiar with this from calculus, but at least it’s more interesting than L’Hôpital’s rule. For those who haven’t seen it, this post is outside the main line. Accordingly, I’m willing to leave some of the calculus unmotivated and unexplained.

Newton’s Method is an attempt to find a point where for some function . The basic idea is that we pick a point near where we think there’s a zero of the function and assume that the graph of the function is sort of sloping towards the zero. Functions on their own are sort of hard to work with, but we know how to deal with linear functions pretty well. We’ll try to pretend the function is just linear and work from there.

So if we start at the point we have the point on the graph above it. Then we draw a straight line that just touches the graph at that point. Calculus tells us that this line has the equation . Now we want to find the where this line crosses the -axis. That is: . Some algebra tells us that .

Now I’m not saying that is our desired zero, but hopefully it’s closer. Then we just run this again. If we define we can write . And then we continue by writing , where the exponent means we evaluate the function twice. This goes on, defining an infinite sequence of points , and the hope is that this will zoom in on a zero of the function.

Well, zeroes of the function are fixed points of this map. Indeed, if then . We have other tools that tell us a fixed point of a function will attract nearby points if . And here, . Since , we see that , so near these fixed points the map does indeed pull points closer.

But there’s a problem. What happens when ? Then the function is undefined, and the method breaks down. Almost as bad, near those points the tangent line is almost flat, and so the next point in the sequence ends up very far away, possibly nearer a different zero than the one we were trying to find.

Here’s a picture to show how complicated this can get. In this picture, we’re moving from calculus over the real numbers to calculus over the complex numbers, but the mechanics of Newton’s Method work the same. We consider the function , so we’re trying to find the three points on the complex plane that have cube . We know that one is itself, and the other two are situated a third of a rotation around the unit circle in either direction.

We get the picture by picking a complex number to start with, and running the method until we’re within some very small distance of one of our zeroes, so we know we’re going to get to that one in the limit. If we end up at , we color the point blue. The points which go to the other two zeroes we color green and red, respectively. We color a point darker if it takes longer to get near one of the zeroes.

We’d hope that starting at a given point would land us at the closest of the three zeroes, but borders here are tricky. We can never have a boundary between two of these basins of attraction without having the third one there too. So along the line separating the blue basin from the red one we have a chain of green islands. Similarly, we have red islands between blue and green, and blue islands between red and green. And then along the boundary a green island shares with the big blue basin we have a chain of smaller red islands, and so on. The upshot is that every boundary point looks like the point at where all three basins touch each other, leading to the famous self-similarity that is characteristic of fractal geometries.

More on Kernels and Cokernels

The best-known abelian categories are categories of modules over various rings. And as modules, these objects are structured sets. Now, even though we’re willing to elide the difference between a hom-group and a hom-set, we would at least like to avoid talking about the objects as sets, and the morphisms as functions. So let’s try to focus on studying the morphisms and use them to understand the properties of the category. Luckily, in an abelian category we know a lot about morphisms.

For one thing, let’s consider an object and the set of all the arrows coming into . We can put the structure of a preorder on this set by saying if there is with . It’s straightforward to show that this relation is reflexive and transitive. Then, as usual we can symmetrize this relation to get an equivalence relation: if and only if and . When we pass to the equivalence classes, the preorder becomes a partial order, which we’ll also call . In particular, this includes all monomorphisms, which we know as subobjects.

Similarly, we can construct another preorder of all the arrows leading out of with if there is an with . We can also turn this into a partial order, which includes the partial order of all quotient objects of .

Now for every arrow from pick a kernel and for every to pick a cokernel. Then and live in , while and live in . And we have three equivalent statements:

• 
• 
• 

Now the partial orders and can be considered as categories, as any partial order can be. And the maps and reverse these orders, so they are contravariant functors. So let’s flip the order on ( instead of ) and instead consider them as covariant functors and .

The above equivalence now reads . That is, we have an adjunction. The identities satisfied by the unit and counit read, in this case:

• 
• 

Properties of Ab-Categories

There are a number of things we can say right off about the -categories we defined last time. As is common practice, we’ll blur the distinction between an abelian group and its underlying set.

First of all, any -category has zero morphisms. That is, there’s a special morphism between any two objects that when composed with any other morphism gives the special morphism in the appropriate hom-set. In fact, since each hom-set is an abelian group it has an additive identity . Then for any we have , which composition must send to . The zero morphisms are exactly the zero morphisms!

Given any object the hom-set is already an abelian group. But the composition puts the structure of a monoid onto this set as well, and the linearity condition says these two are compatible, making the endomorphism monoid into an endomorphism ring. In fact, every ring is an endomorphism ring. Way back when we first defined categories we noted that a category with one object was the exact same thing as a monoid. And a ring is just an abelian group with a compatible monoid structure on it. So an -category with a single object is the exact same thing as a ring! In fact, a lot of the study of -categories can be seen as extending ring theory from that special case to the more general one. Incidentally, you should see right off that when we consider rings and as categories like this, a ring homomorphism from to is the same thing as an -functor between the categories.

Remember when we talked about direct sums of modules over a given ring? Well the same thing happens here. We define the “biproduct” of the finite collection of objects to be an object along with two families of arrows:

• 
• 

satisfying the relations

• if
• 
• 

From the same arguments as in our coverage of direct sums we see that a biproduct satisfies the universal properties of both a categorical product and coproduct, and conversely that a categorical product or coproduct implies the existence of the biproduct arrows. Note that we’re making no statement whatsoever that such a biproduct actually exists in our category, but when it does it’s both a product and a coproduct.

As a special case, we can consider the biproduct of an empty collection of objects. This will be both a product and a coproduct of an empty collection of objects, if it exists, and will thus be a zero object. Of course, it may or may not exist.

Even if there is no zero object in our category, we still have the above zero morphisms, and so we can still talk about kernels and cokernels. The kernel of a morphism is the equalizer , and its cokernel is the coequalizer . In fact, life is even better now that we’re enriched over : every equalizer is a kernel and every coequalizer is a cokernel. Indeed, and similarly for coequalizers. Again, we’re saying nothing about whether such kernels or cokernels actually exist.

Together, these facts say a lot about the behavior of limits in -categories. Biproducts tell us about finite products and coproducts, while kernels of morphisms tell us about all different equalizers. And then The Existence Theorem for Limits tells us that every finite limit can be constructed from finite products and equalizers, while every finite colimit can be constructed from finite coproducts and coequalizers. So if our -category has all biproducts, all kernels, and all cokernels, then it has all finite limits whatsoever!

Let’s add one more little property that will simplify our life. We know that kernels are monomorphisms, and that cokernels are epimorphisms. If we assume on top of having all biproducts, kernels, and cokernels that every monomorphism is actually the kernel of some arrow in our category, and that every epimorphism is actually the cokernel of some arrow, then we will call our -category an abelian category.

You should verify that given any ring the category of all left -modules satisfies all these properties, and thus is an abelian category. These are the abelian categories that started the whole theory of homological algebra, which is to a large extent the study of general abelian categories.

Sunday Samples 34 (one day late)

Sorry about getting caught up in other business yesterday.

Saturday night I went out to a club for the first time in forever. It reminded me how annoying going out alone can be (another SS about that another time), but it was good to hit the floor again. Anyhow, it’s got me in an electronic mood…

Somewhere around the turn of the millennium, BT — the professional moniker of Brian Transeau — composed a hardcore breakbeat update of Gil Scott-Heron’s “The Revolution Will Not Be Televised”. As happens so often in electronic music, it wasn’t ever really released on its own, slipping out into the ether through the cracks. It was eventually used on the soundtrack of the Tomb Raider movie, and it made it onto the compilation 10 Years in the Life, which is where I picked it up. There’s no official music video for it either, but a lot of people have composed videos with clips from various sources on YouTube. None of them really grab me, but you can find them to hear the song if you’d like. Or you can just grab that BT compilation and get a lot more good stuff.

And so, BT’s “The Revolution”.

Ab-Categories

Now that we’ve done a whole lot about enriched categories in the abstract, let’s look at the very useful special case of categories enriched over — the category of abelian groups.

We know that is a monoidal category, with the tensor product of abelian groups as its monoidal structure and the free abelian group as the monoidal identity. Even better, it’s symmetric, and even closed. That is, for any two abelian groups and we have an isomorphism , and there is a natural abelian group structure on the set of homomorphisms satisfying the adjunction .

Further, is complete and cocomplete. All together, this means it’s a great candidate as a base category on which to build enriched categories. Of course, these will be called -categories.

So let’s read the definitions. An -category has a collection of objects, and between objects and there is an abelian hom-group .

For each object we have a homomorphism of abelian groups which picks out the “identity morphism” from to itself at the level of the underlying sets. Remember that we’re no longer thinking of an abelian group as having elements — only its underlying set has elements anymore, and the underlying set of an abelian group is the set of abelian group homomorphisms .

Given three objects we have a “composition” arrow in : . This is associative and the identity morphism acts as an identity in the sense that the appropriate diagrams commute. Of course, since the composition arrows are morphisms in they are linear functions in each input.

An -functor between -categories and is defined by a function from the objects of to the objects of , and for each pair of objects a homomorphism of abelian groups . Two diagrams are required to commute, saying that these linear functions preserve the composition and identity functions.

An -natural transformation is one of two forms. In one we’re given two -functors and . Then a natural is a collection of linear functions making one diagram commute. In the other we’re given an object and a bifunctor . Then is a collection of linear functions making another diagram commute.

Together, -categories, -functors between them, and -natural transformations (of the first kind) form a 2-category. We can pair off -categories and to get the product category (in fact we already did once above) and we can take the opposite category . Thus -categories form a symmetric monoidal 2-category with a duality involution.

There’s a whole lot of structure here, but ultimately it boils down to “the hom-sets all have the structure of abelian groups, and everything in sight is -linear”. And that’s the usual definition given, that I decided to forgo back when I started in on enriched categories.

Free Enriched Categories

Now we’re going to assume that our monoidal category is also cocomplete. In particular, we’ll assume that it has all small coproducts.

This is enough to ensure that the “underlying set” functor has a left adjoint that sends a set to the coproduct of a bunch of copies of indexed by . The adjunction says that is naturally isomorphic to . That is, a function from to the underlying set of is the same as an -indexed collection of elements of the underlying set of .

It’s straightforward from here to verify that this adjunction interchanges the cartesian product on and the monoidal structure on . That is, and .

And now the 2-functor has a left 2-adjoint . Starting with an ordinary category (with hom-sets) we get the “free -category” with the same objects as , and with the hom-objects given by . Compositions and identities for this -category are induced by the above exchange of cartesian and monoidal structures. The actions of this 2-functor on functors and natural transformations are straightforwardly defined.

For example, when , we just replace each hom-set by the free abelian group on . We extend the composition and identity maps from the ordinary category by linearity. In particular, if has only one object — if it’s a monoid — then is the free ring on .

To finish off, let be a small category, so is a small -category. Then we can define functor categories and functor -categories. Verify that by the above 2-adjunction.

The Strong Yoneda Lemma

We gave a weak, “half-enriched” version of the Yoneda Lemma earlier. Now it’s time to pump it up to a fully-enriched version.

Given a -functor and an object , then the functor defines a -natural map . We also have the (ordinary) adjunction

and under this adjunction we find corresponding to a -natural transformation . Now the strong form of the Yoneda Lemma says that this family is actually the counit of the end , so by the definition of the functor category we have an isomorphism in :

So, how do we verify that is the end in question? Consider any other -natural family . Now we run the above adjunction backwards to get a -natural family . But this is now a -natural transformation from the functor represented by to the functor , and so the weak form of the Yoneda Lemma tells us that for a unique . Running this back through the adjunction says that , and the universal property is satisfied.

Let’s hit this isomorphism with the underlying set functor to get a bijection . This sends an arrow to , which is a -natural family with components given by . But this is exactly the bijection asserted by the weak form of the Yoneda Lemma, so the weaker form is implied by the stronger one.

If we consider the special case where our functor is representable, we find that

When exists, we can convert the functor to a functor by the exponential adjunction in . By the case of representable functors given above, this Yoneda embedding is fully faithful. From this -functor we can establish that the Yoneda isomorphism is -natural in and .