The Unapologetic Mathematician

Mathematics for the interested outsider

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 E_8 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 ūüėČ


September 29, 2007 Posted by | Atlas of Lie Groups | Leave a comment

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 x with codomain A a member of A and write x\in_mA. Now we say that two such arrows are equivalent — and write x\equiv y if there are epimorphisms u and v with x\circ u=y\circ v. Clearly the relation is reflexive (use the identity on the source of x) and symmetric. We can see transitivity by considering the following diagram:
Transitivity Diagram for Equivalence of Members
We assume that there are epimorphisms t and u in the upper-right so that x\equiv y, and epimorphisms v and w in the lower-left so that y\equiv z. Now we can pull back the upper left square to get u' and v', which are epic by the second lemma last time. The compositions t\circ u' and w\circ v' are then the epimorphisms we need to show that x\equiv z.

The members of A behave sort of like an abelian group in that we have a “zero” member \mathbf{0}\rightarrow A, and each arrow has a negative -x in its hom-set. It’s straightforward to show that if x\equiv y then -x\equiv -y and any zero morphism 0:B\rightarrow A is equivalent to the zero member. Also, any arrow f:A\rightarrow B sends a member x\in_mA to a member (f\circ x)\in_mB, 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:

  • f:A\rightarrow B is monic if and only if for all x\in_mA, f\circ x\equiv0 implies x\equiv0
  • f:A\rightarrow B is monic if and only if for all x,x'\in_mA, f\circ x\equiv f\circ x' implies x\equiv x'
  • f:A\rightarrow B is epic if and only if for all y\in_mB there is an x\in_mA with f\circ x\equiv y
  • f:A\rightarrow B is zero if and only if for all x\in_mA, f\circ x\equiv0
  • Given f:A\rightarrow B and g:B\rightarrow C, the sequence A\rightarrow B\rightarrow C is exact at B if and only if g\circ f=0, and for every y\in_mB with g\circ y\equiv0 there is an x\in_mA with f\circ x\equiv y
  • Given f:A\rightarrow B and x,y\in_mA with f\circ x\equiv f\circ y there is a z\in_mA with f\circ z\equiv0. Further, any g:A\rightarrow C with g\circ x\equiv0 has g\circ y\equiv g\circ z and any h:A\rightarrow D with h\circ y\equiv0 has h\circ x\equiv -h\circ z.

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 f is epic then we can pull back y along f to find f' and x with f\circ x=y\circ f', which implies y\equiv f\circ x. Conversely, if f is not epic then the member 1_B\in_mB is not of the form f\circ x\equiv1_B for any x\in_mA.

Rule six seems complicated, but it just replaces subtraction of elements. Since f\circ x\equiv f\circ y there are epimorphisms u,v so that f\circ x\circ u=f\circ y\circ v. Then all the conclusions hold by taking z=y\circ v-x\circ u\in_mA.

Finally, in rule five we can take the canonical factorization f=m\circ e. If the sequence is exact at B then m is the kernel of g, so for any y with g\circ y=0 we have y=m\circ y'. Now we can pull back y' along e to get e' and x\in_mA with y'\circ e'=e\circ x and e' epic. We see that y\circ e'=f\circ x, so y\equiv f\circ x, as desired. Conversely, if this holds for all y\in_mB we can take k\in_mB the kernel of g so that g\circ k\equiv0\in_mC. Then there is some x\in_mA with f\circ x\equiv k, and thus there are epimorphisms u,v with k\circ u=m\circ e\circ x\circ v. This implies that k factors through m, and thus that \mathrm{Ker}(g)\leq\mathrm{Im}(f) as subobjects of B. But g\circ f=0 implies that \mathrm{Im}(f)\leq\mathrm{Ker}(g), 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 \mathbf{Ab}, 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.

September 28, 2007 Posted by | Category theory | 7 Comments

Short Exact Sequences

Last time we defined a short exact sequence in an abelian category \mathcal{C} to be an exact sequence of the form \mathbf{0}\rightarrow A\rightarrow B\rightarrow C\rightarrow\mathbf{0}. These are the objects of a category \mathbf{Ses}(\mathcal{C}), whose morphisms are triples of arrows f:A\rightarrow A', g:B\rightarrow B', h:C\rightarrow C' making the two squares commute in the diagram:
The Short Five Lemma Diagram
The category is clearly enriched over \mathbf{Ab}.

As a first step into this category, we show that if f and h are both monic, then g is monic as well. First let’s see how to do this in \mathbf{Ab}. We want to show that if g(b)=0 for b\in B that b=0. Now h(e(b))=e'(g(b))=0, but we assumed h to be monic, so e(b)=0b\in\mathbf{Ker}(e). Since the top row is exact this means b\in\mathrm{Im}(m), and so there’s an a\in A so that m(a)=b. Now m'(f(a))=g(m(a))=g(b)=0, but both m' and f are monic. Thus a=0, and m(a)=b=0 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 B and “chase” it around the diagram. But this only works if \mathcal{C} 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 k:\mathrm{Ker}(g)\rightarrow B. Now h\circ e\circ k=e'\circ g\circ k=0. Since h is monic, we have e\circ k=0. And thus k factors uniquely through m=\mathrm{Ker}(e) as k=m\circ k'. Now 0=g\circ k=g\circ m\circ k'=m'\circ f\circ k'. Since m' and f are assumed monic, k=0, and so \mathrm{Ker}(g)=\mathbf{0} and g is monic.

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

Here’s another lemma, based on this diagram:
Pullback Lemma Diagram
The square on the right is a pullback, and I say that if f is epic then f' is too. On the left is the kernel k of f, and I say that it factors through the kernel k' of f' 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 B\oplus D, which then has two arrows to C: f\circ\pi_1 and g\circ\pi_2. And we find their equalizer by taking the kernel of their difference: m:S\rightarrow B\oplus D. Then g'=\pi_1\circ m and f'=\pi_2\circ m.

Now under the assumption on f, we know that f\circ\pi_1-g\circ\pi_2 is epic. Indeed, if h\circ(f\circ\pi_1-g\circ\pi_2)=0 then 0=h\circ(f\circ\pi_1-g\circ\pi_2)\circ\iota_1=h\circ f. But since f is assumed epic, h=0. Supposing now that u\circ f'=0, we see that u\circ\pi_2\circ m=0, so u\pi_2 factors through the cokernel of m, which is f\circ\pi_1-g\circ\pi_2. That is, u\circ\pi_2=u'\circ(f\circ\pi_1-g\circ\pi_2), and so u'\circ f=u'\circ(f\circ\pi_1-g\circ\pi_2)\circ\iota_1=u\circ\pi_2\circ\iota_1=0. Since f is epic, u'=0, and so u=u\circ\pi_2\circ\iota_2=u'\circ(f\circ\pi_1-g\circ\pi_2)=0. Thus f' is epic.

As for the other assertion, the pair of arrows k:A\rightarrow B and 0:A\rightarrow D satisfy f\circ k=g\circ0=0, and so there is a unique arrow k':A\rightarrow S by the universal property of the pullback. In particular, f'\circ k'=0:A\rightarrow D. On the other hand, given any other v with f'\circ v=0 we have f\circ g'\circ v=g\circ f'\circ v=0, so g'\circ v factors uniquely through k as g'\circ v=k\circ v'. Then g'\circ v=g'\circ(k'\circ v') and f'\circ v=0=f'\circ(k'\circ v'). But since the arrow factoring through a pullback is unique we must have v=k'\circ v'. So k' really is the kernel of f', as asserted.

September 27, 2007 Posted by | Category theory | 5 Comments

Images, Coimages, and Exactness

By the first isomorphism theorem, we know that any morphism f in an abelian category \mathcal{C} factorizes as f=m\circ e with m=\mathrm{Ker}(\mathrm{Cok}(f)), and e is epic. Since m is monic, f\circ t=m\circ e\circ t=0 exactly when e\circ t=0. That is, the kernel of f is isomorphic to the kernel of e. Then since e is epic, e=\mathrm{Cok}(\mathrm{Ker}(e))=\mathrm{Cok}(\mathrm{Ker}(f)). So there’s a sort of a symmetry here between the monic and the epic in the factorization of f.

Now let’s consider another morphism f' and a pair of morphisms (g,h) so that h\circ f=f'\circ g. Then we can factorize each of f and f' as above to find h\circ m\circ e=m'\circ e'\circ g. Then there is a unique k such that e'\circ g=k\circ e and m'\circ k=h'\circ m.

To see this, set u=\mathrm{Ker}(f)=\mathrm{Ker}(e). Then 0=h\circ f\circ u=m'\circ e'\circ g\circ u so e'\circ g\circ u=0. Thus e'\circ g factors uniquely through e=\mathrm{Cok}(u) as e'\circ g=k\circ e. Then m'\circ k\circ e=m'\circ e'\circ g=h\circ m\circ e. And so since e is epic we have m'\circ k=h'\circ m.

Now, we’ll regard f and f' as objects in the arrow category \mathcal{C}^\mathbf{2}. Then the pair (g,h) is a morphism from f to f'. Similarly, the triangle f=m\circ e is an object of \mathcal{C}^\mathbf{3}, and the triple (g,k,h) is a morphism in this category.

What the above proof shows is that any object in \mathcal{C}^\mathrm{2} can be assigned an object in \mathcal{C}^\mathcal{3}, and that any morphism in \mathcal{C}^\mathbf{2} can be assigned one in \mathcal{C}^\mathcal{3}. Clearly this assignment amounts to a functor. In particular, if we start with the identity pair (1,1) we must have an isomorphism for k, and thus any two factorizations are isomorphic.

Now, given this unique (up to isomorphism) factorization, we can define the image and coimage of f=m\circ e:A\rightarrow B as \mathrm{Im}(f)=m and \mathrm{Coim}(f)=e. Thus as expected the image of f 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 f:A\rightarrow B and g:B\rightarrow C. Both \mathrm{Im}(f) and \mathrm{Ker}(g) are subobjects of B, and we say that the pair (f,g) is exact at B when \mathrm{Im}(f)=\mathrm{Ker}(g). 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 \mathbf{0}\rightarrow A\rightarrow B\rightarrow C\rightarrow\mathbf{0} is short exact if it is exact. That is, if we let the two outer arrows be the unique such, let f:A\rightarrow B, and let g:B\rightarrow C, then the sequence is short exact if \mathrm{Ker}(f)=\mathbf{0}, \mathrm{Im}(g)=\mathbf{0}, and \mathrm{Ker}(g)=\mathrm{Im}(f). If we drop the left \mathbf{0} we call the sequence short right exact, and short left exact sequences are defined similarly.

Now the factorization of f:A\rightarrow B gives rise to two short exact sequences: \mathbf{0}\rightarrow\mathrm{Ker}(f)\rightarrow A\rightarrow\mathrm{Coim}(f)\rightarrow\mathbf{0} and \mathbf{0}\rightarrow\mathrm{Im}(f)\rightarrow B\rightarrow\mathrm{Cok}(f)\rightarrow\mathbf{0}. 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 \mathbf{Ab}-functor T:\mathcal{C}\rightarrow\mathcal{D} is called left exact when it preserves all finite limits. In particular it preserves kernels — that is, left exact sequences. Since any \mathbf{Ab}-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.

September 26, 2007 Posted by | Category theory | 4 Comments

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 \mathcal{C} is a category with a zero object, kernels, and cokernels, then any arrow f of \mathcal{C} has a factorization f=m\circ q, where m=\mathrm{Ker}(\mathrm{Cok}(f)). This holds because \mathrm{Cok}(f)\circ f=0, and by the universal property of kernels there is a unique q with f=m\circ q.

On the other hand, if we have another factorization f=m'\circ q' with m' also a kernel, then we have a unique t so that the following diagram commutes.
Universality Diagram for Canonical Factorization
That is, the canonical factorization described above is in some sense the universal such factorization. Furthermore, if \mathcal{C} has equalizers and every monic in \mathcal{C} is a kernel, then q 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 q and a monic m.

We prove this by considering the following diagram:
Diagram for the Proof of the Isomorphism Theorem
We draw p'=\mathrm{Cok}(m'). Since m' is itself a kernel, we see that m'=\mathrm{Ker}(p'). We also draw p=\mathrm{Cok}(m)=\mathrm{Cok}(f). Now p'\circ m'=0, so p'\circ f=p'\circ m'\circ q'=0. By the universal property of p , there is a unique w so that p'=w\circ p. And then p'\circ m=w\circ p\circ m=0, so m factors uniquely through m' — there is a unique t with m=m'\circ t. Furthermore, m'\circ q'=m\circ q=m'\circ t\circ q, and so since m' is monic we have q'=t\circ q. This proves that the first diagram given above commutes.

Now we have to show that q is epic under the additional hypotheses. Let’s say that we have a parallel pair of arrows r and s with r\circ q=s\circ q. then q factors uniquely through the equalizer \mathrm{Equ}(r,s)q=e\circ q' for some unique q'. Then f=m\circ q=m\circ e\circ q'. Now m'=me is monic, so (by the new hypotheses) it’s a kernel. By the first part of the theorem we have a unique t with m=m'\circ t=m\circ e\circ t, and thus 1=e\circ t. Since the monic e has a right inverse, it’s an isomorphism. Since e was picked as the equalizer of r and s, r=s. And so q is epic.

September 25, 2007 Posted by | Category theory | 8 Comments

Problems with Ordered Linear Spaces — Solved!

Okay, there’s some sort of problem with these things. I defined the category \mathcal{O}rd\mathcal{L}in, 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 \hat{V}=\hom_{\mathcal{O}rd\mathcal{L}in}(V,\mathbb{F}), which seems sort of like a categorical dual, but maybe not.

What I tried to prove is that in general \hat{V}\otimes W is not isomorphic to W^V. But as Todd pointed out, if \hat{V} 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 \hat{V} is a categorical dual, then W^V is naturally isomorphic to \hat{V}\otimes W, and there’s something wrong with the proof I offered that it isn’t.

On the other hand, if \hat{V}\otimes W is not naturally isomorphic to W^V, then \hat{V} 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 V, 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 g taking the vector space V to the free vector space \mathbb{F}^n, and taking our chosen basis of V to the canonical basis of \mathbb{F}^n. We induce a cone on \mathbb{F}^n by saying (x_1,...,x_n)\geq0 if and only if g^{-1}(x_1,...,x_n)\geq_V0. So without loss of generality our positive basis consists of the “coordinate vectors” (0,...,0,1,0,...,0), and the dual basis consists of the coordinate projections.

Now these vectors cut out a classical subcone of V, and the positive vectors are exactly those in the positive orthant. If V is not exactly this classical cone, then there exists some positive vector v in V outside the positive orthant. That is, some component of v will be negative. But then that coordinate projector will send v 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 V is classical.

So what does this mean? Just that \hat{V}=\hom_{\mathcal{O}rd\mathcal{L}in}(V,\mathbb{F}) is only the categorical dual to V when V is classical. Thus only in this case do we have an adjunction V\otimes\underline{\hphantom{X}}\dashv\hat{V}\otimes\underline{\hphantom{X}}, and so only in this case do we find \hat{V}\otimes W\cong W^V naturally in W.

What happens for non-classical cones? Well, (\underline{\hphantom{X}})^V is a right adjoint, and so its evaluation transformation \epsilon_W:V\otimes W^V\rightarrow W is couniversal. Since we also have a natural transformation V\otimes\hat{V}\otimes W\rightarrow W (evaluate the second factor on the first) it must factor through the couniversal. That is, there is an arrow \hat{V}\otimes W\rightarrow W^V, which is the one we earlier calculated explicitly. But it’s not generally an isomorphism.

September 25, 2007 Posted by | Category theory | 1 Comment

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.

September 25, 2007 Posted by | Uncategorized | 2 Comments

Ordered Linear Spaces III

[UPDATE]: This whole post is badly-founded as it stands, because on further reflection it seems that \mathcal{O}rd\mathcal{L}in 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 A^*\otimes B\rightarrow B^A. Indeed, we have an arrow
A^*\otimes B\otimes A\cong A^*\otimes A\otimes B\rightarrow\mathbf{1}\otimes B\cong B
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 A^*\otimes B\otimes A to B corresponds to an arrow from A^*\otimes B to B^A.

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 B^A. But it turns out that it doesn’t hold in \mathcal{O}rd\mathcal{L}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 A^*\otimes B. This is a finite sum f=\sum_{i=1}^n\alpha^i\otimes b_i, where the b_i are positive vectors in B and the \alpha^i are positive linear functionals on A. 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 \alpha_i(a)\geq_\mathbb{F}0 for all a\geq_A0. Then if we feed f a positive element of A, we evaluate to find f(a)=\sum_{i=1}^n\alpha^i(a)b_i, which is a linear combination of positive vectors in B with positive coefficients, and thus is positive. So f corresponds to a positive map as it should. This is just the arrow described above, now in the special case of \mathcal{O}rd\mathcal{L}in.

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

I think that we can push on from here to show that this implies that either A or B 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 \hat{V}=\hom_{\mathcal{O}rd\mathcal{L}in}(V,\mathbb{F}) as before. That is, a linear functional is considered positive if it sends the whole positive cone from V to the positive ray in \mathbb{F}. Now the question is, in what sense is this a “dual”?

September 24, 2007 Posted by | Category theory | 3 Comments

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 \mathcal{O}rd\mathcal{L}in inherits a lot from the category of vector spaces.

For one thing, given a pair of vector spaces {V} and W, we can take their direct sum V\oplus W. 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 \pi_V, \pi_W, \iota_V, and \iota_W are positive. Let’s write these as logical statements and see what they imply:

  • If (v,w)\geq_{V\oplus W}0 then \pi_V(v,w)=v\geq_V0.
  • If (v,w)\geq_{V\oplus W}0 then \pi_W(v,w)=w\geq_W0.
  • If v\geq_V0 then \iota_V(v)=(v,0)\geq_{V\oplus W}0.
  • If w\geq_W0 then \iota_W(w)=(0,w)\geq_{V\oplus W}0.

The projections tell us that if a pair (v,w) is positive in V\oplus W, 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 V\oplus W 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 \mathcal{O}rd\mathcal{L}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 \mathbf{FinVect}_\mathbb{F} we have an exponential — {W^V} is the vector space of all \mathbb{F}-linear maps from {V} to W. Is there a natural cone in this vector space? Indeed there is! It’s just the cone of all positive maps! That is, f\geq_{W^V}0 if and only if v\geq_V0 implies f(v)\geq_W0.

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 \hom_{\mathcal{O}rd\mathcal{L}in}(U\otimes V,W)\cong\hom_{\mathcal{O}rd\mathcal{L}in}(U,W^V). So let’s read this as another logical statement. A linear map \mu:U\rightarrow W^V is positive (and thus in \hom_{\mathcal{O}rd\mathcal{L}in}(U,W^V)) if
Expanding this condition on \mu (u), we get that \mu is positive if
But (u,v)\mapsto[\mu(u)](v) 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 U\otimes V to W to correspond to exactly one \mu in just this way. Thus the cone on U\otimes V that makes the tensor product for \mathcal{O}rd\mathcal{L}in into a left adjoint to the exponential is that of all finite sums of tensor pairs of positive elements. That is, if x=\sum_{i=1}^n u_i\otimes v_i with all the u_i and v_i positive in their respective cones. As an exercise, verify that this tensor product is also symmetric.

The monoidal identity has the base field \mathbb{F} as its underlying vector space. For its cone, take the positive ray. It’s straightforward to check that V\otimes\mathbb{F}\cong V. As usual, we use the tensor identity to represent the “underlying set” functor. That is, we define the underlying set of a cone {V} by {\hom_{\mathcal{O}rd\mathcal{L}in}(\mathbb{F},V)}. Such a positive map f is a linear map from \mathbb{F} to {V} that picks out a positive point f(1)\geq_V, and there is exactly one such map for each positive point in {V}. That is, the underlying set is exactly the set of points in the positive cone of {V}. As a check, note that this means the underlying set of {W^V} is the set \hom_{\mathcal{O}rd\mathcal{L}in}(V,W).

As if that weren’t enough, \mathcal{O}rd\mathcal{L}in has duals! Indeed, we have a cone in the dual vector space defined by {\lambda\geq_{V^*}0} if and only if {\lambda(v)\geq_\mathbb{F}0} for all v\geq_V0. Or in other words, \lambda\in\hom_{\mathcal{O}rd\mathcal{L}in}(V,\mathbb{F}). We just need natural maps \epsilon_V:V\otimes V^*\rightarrow\mathbb{F} and \eta:\mathbb{F}\rightarrow V^*\otimes V to make this really a categorical dual. The first of these is evaluation — \epsilon(v,\lambda)=\lambda(v). The second one picks out an identified element in V^*\otimes V. How can we do this?

Well, in a vector space we can pick a basis \{e_i\} of {V} and get a dual basis \{f_i\} of V^* defined so that f_j(e_i) is 1 if i=j and {0} otherwise. Then we can sum up \sum_{i=1}^nf_i\otimes e_i. 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 {V}.

Now if {V} 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 \sum_{i=1}^nf_i\otimes e_i is always in the positive cone of V^*\otimes V, 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 \eta and \epsilon satisfy the two required equations, making V^* the dual of {V}.

[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, \mathcal{O}rd\mathcal{L}in does not in general have duals.

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

September 24, 2007 Posted by | Category theory | 6 Comments

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 \mathcal{O}rd\mathcal{L}in of “ordered linear spaces” by starting with a totally ordered field \mathbb{F}. 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 \mathbf{FinVect}_\mathbb{F} of finite-dimensional vector spaces over \mathbb{F} and \mathbb{F}-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 {0}. Then v\geq w exactly when v-w\geq0. We require that if v\geq0 then so is each \lambda v with \lambda\geq0 in the field \mathbb{F}. From this we can tell that if u=\lambda v+(1-\lambda)w with v\geq0, w\geq0, and 0\leq\lambda\leq1, then u\geq0 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 \mathcal{O}rd\mathcal{L}in. 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 f:V\rightarrow W “positive” if whenever v\geq0 in V then f(v)\geq0 in W. 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 \mathbf{FinSet} of finite sets to \mathcal{O}rd\mathcal{L}in. 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 \mathcal{O}rd\mathcal{L}in.

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

September 23, 2007 Posted by | Category theory | 4 Comments