The Unapologetic Mathematician

Mathematics for the interested outsider

Sunday Samples 36

I’ve just picked up the 2005 album by Lemon Jelly, entitled ‘64-’95. It definitely strikes a darker note than their earlier works like “Spacewalk” (which you may have heard in a recent cat food ad).

Each track on the album picks a song released between 1964 and 1995 as its conceptual basis, and most sample that song extensively. The closing track, though, is only inspired by Lorne Green’s 1964 spoken-word ballad “Ringo”, and is musically constructed out of whole cloth. But who could possibly replace a Canadian 1960s-era spoken-word recording artist and science-fiction television actor?

Enter William Shatner, turning in another excellent performance in Lemon Jelly’s “‘64 aka Go”. Side note: the section in the middle is all but incomprehensible, more meant to be experienced than parsed. Watch the video and you’ll understand.

Read more »

September 30, 2007 Posted by John Armstrong | Sunday Samples | | 1 Comment

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 John Armstrong | Atlas of Lie Groups | | No Comments

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 John Armstrong | Category theory | | 3 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)=0 — b\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 John Armstrong | Category theory | | 3 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 John Armstrong | Category theory | | 2 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 John Armstrong | Category theory | | 2 Comments

A Class More Undergraduates Would Appreciate

Courtesy of Cat and Girl.

September 25, 2007 Posted by John Armstrong | Uncategorized | | 1 Comment

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
V\otimes\underline{\hphantom{X}}\dashv\hat{V}\otimes\underline{\hphantom{X}}
but the definition of an exponential is an adjunction
V\otimes\underline{\hphantom{X}}\dashv(\underline{\hphantom{X}})^V
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 John Armstrong | 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 John Armstrong | 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 John Armstrong | Category theory | | 3 Comments

« Previous Entries