# Algorithm or theory of diagram chasing

One of the standard parts of homological algebra is "diagram chasing", or equivalent arguments with universal properties in abelian categories. Is there a rigorous theory of diagram chasing, and ideally also an algorithm?

To be precise about what I mean, a diagram is a directed graph $D$ whose vertices are labeled by objects in an abelian category, and whose arrows are labeled by morphisms. The diagram might have various triangles, and we can require that certain triangles commute or anticommute. We can require that certain arrows vanish, which can be used to ask that certain compositions vanish. We can require that certain compositions are exact. Maybe some of the arrows are sums or direct sums of other arrows, and maybe some of the vertices are projective or injective objects. Then a diagram "lemma" is a construction of another diagram $D'$, with some new objects and arrows constructed from those of $D$, or at least some new restrictions.

As described so far, the diagram $D$ can express a functor from any category $\mathcal{C}$ to the abelian category $\mathcal{A}$. This looks too general for a reasonable algorithm. So let's take the case that $D$ is acyclic and finite. This is still too general to yield a complete classification of diagram structures, since acyclic diagrams include all acyclic quivers, and some of these have a "wild" representation theory. (For example, three arrows from $A$ to $B$ are a wild quiver. The representations of this quiver are not tractable, even working over a field.) In this case, I'm not asking for a full classification, only in a restricted algebraic theory that captures what is taught as diagram chasing.

Maybe the properties of a diagram that I listed in the second paragraph already yield a wild theory. It's fine to ditch some of them as necessary to have a tractable answer. Or to restrict to the category $\textbf{Vect}(k)$ if necessary, although I am interested in greater generality than that.

To make an analogy, there is a theory of Lie bracket words. There is an algorithm related to Lyndon words that tells you when two sums of Lie bracket words are formally equal via the Jacobi identity. This is a satisfactory answer, even though it is not a classification of actual Lie algebras. In the case of commutative diagrams, I don't know a reasonable set of axioms — maybe they are related to triangulated categories — much less an algorithm to characterize their formal implications.

(This question was inspired by a mathoverflow question about George Bergman's salamander lemma.)

David's reference is interesting and it could be a part of what I had in mind with my question, but it is not the main part. My thinking is that diagram chasing is boring, and that ideally there would be an algorithm to obtain all finite diagram chasing arguments, at least in the acyclic case. Here is a simplification of the question that is entirely rigorous.

Suppose that the diagram $D$ is finite and acyclic and that all pairs of paths commute, so that it is equivalent to a functor from a finite poset category $\mathcal{P}$ to the abelian category $\mathcal{A}$. Suppose that the only other decorations of $D$ are that: (1) certain arrows are the zero morphism, (2) certain vertices are the zero object, and (3) certain composable pairs of arrows are exact. (Actually condition 2 can be forced by conditions 1 and 3.) Then is there an algorithm to determine all pairs of arrows that are forced to be exact? Can it be done in polynomial time?

This rigorous simplification does not consider many of the possible features of lemmas in homological algebra. Nothing is said about projective or injective objects, taking kernels and cokernels, taking direct sums of objects and morphisms (or more generally finite limits and colimits), or making connecting morphisms. For example, it does not include the snake lemma. It also does not include diagrams in which only some pairs of paths commute. But it is enough to express the monomorphism and epimorphism conditions, so it includes for instance the five lemma.

-
Very nice problem! – Gil Kalai Dec 28 '09 at 7:22
Everyone note that the question about the salamander lemma was never answered properly (the bounty forced the answer to be accepted), so if you come up with something relevant to that, you should post it there. – Harry Gindi Dec 28 '09 at 21:26
– sdcvvc Dec 29 '09 at 17:08
Kozen's papers are interesting, but no more than somewhat related. I am interested in algorithms in the shallow sense of symbolic algebra rather than the deeper sense of automated formal proof. – Greg Kuperberg Dec 29 '09 at 17:17
Yes, "is there a computer program", or rather a rigorous algorithm, is a big part of my question. – Greg Kuperberg Dec 29 '09 at 23:51

Here's an attempt, assuming the target category is finite dimensional vector spaces and the diagram is finite acyclic.

1) Fill in the diagram so it's triangulated (that is, add the compositions of all arrows). Add kernels and cokernels to every arrow in the diagram. Add the natural arrows between these new objects (e.g. the kernel of $f$ maps into the kernel of $g\circ f$). Iterate this process until it terminates (which it does, as there are finitely many arrows, and thus only finitely many subquotients of objects they induce).

2) In this new diagram, tabulate all exact paths. (This step seems to me to have high time and space complexity, unfortunately.) By exact path, I mean an infinite long exact sequence, for which all but finitely many objects are zero.

3) Given an exact path $$0\to A_1\to \cdots \to A_i\to \cdots \to A_n\to 0$$ write the equation $$\sum_{i=1}^n (-1)^i \dim~ A_i=0.$$

4) Solve the resulting linear system for the $\dim~ A_i$'s.

Since we've added kernels and cokernels, solving the system tells us about injectivity and surjectivity of all the arrows. Furthermore, as far as I can tell any (non-negative) solution to this linear system is realizable as a diagram, so this algorithm gives us any information we could get by diagram chasing.

Greg has given a good summary of this method in his answer below--he takes me to task about my assertion that any non-negative integer solution to this linear system is realizable, so I will sketch an argument (again requiring the diagram to be finite acyclic). We also assume the diagram is "complete" in the sense that step 1) has been completed.

Partially order the objects in the diagram by saying $A\leq B$ iff $A$ is a subquotient of $B$; inductively, this is the same as saying that $B\leq B$ and $A\leq B$ if there exists $C\leq B$ such that $A$ injects into $C$ or $C$ surjects onto $A$ in this diagram. We identify isomorphic objects; this is a poset by acyclicity. We proceed by induction on the number of objects in the diagram. The one-object diagram is easy, so we do the induction step.

By finiteness the diagram contains a longest chain; choose such a chain and consider its minimal element $X$. All maps into or out of $X$ are surjections or injections, respectively, so split $X$ off of every object that maps onto it or that it maps into as a direct summand. The diagram with $X$ removed gives the induction step.

-
It seems we can do a bit better by adding images to the diagram as well; then we need only consider short exact sequences in steps 2 and 3. – Daniel Litt Jun 21 '10 at 14:15
I'll have to think about it some more because it's a telegraphic answer (for me at least), but I think that it could be a good answer in the special case that there are no commutative triangles. Certainly you're taking the question in the way that I intended it. That said, commutative triangles are where the fun begins. – Greg Kuperberg Jun 21 '10 at 16:46
I'm not familiar with the phrase "telegraphic answer"; if as I am guessing you mean that the answer is overly brief, I agree--I think there's a lot to be proven before what I wrote is at all rigorous. This does work to prove, say, the nine lemma though. By the way, can you give an example of an easy diagram chase with commutative triangles? I am having trouble coming up with one to play around with off the top of my head. – Daniel Litt Jun 21 '10 at 17:16
I don't understand how it proves the nine lemma. Where does your algorithm use the fact that the diagram of the nine lemma has commutative squares? My point about commutative triangles is that pair of commuting paths in a diagram, such as a commutative square, decomposes into commutative triangles if you add extra edges. (And yes, your answer is too brief for me to understand it. I can fill in many of the points of rigor myself, but only once I really know what you're saying.) – Greg Kuperberg Jun 21 '10 at 22:13
Edited--the issue you're worried about is in step 1. Sorry I was unclear about this. Commutativity is used to construct the natural maps. As for the nine lemma--simply write out every short exact sequence in sight and solve the system I describe. – Daniel Litt Jun 21 '10 at 23:54

I'm not sure this is what you are looking for, but if you look at Gelfand and Manin's Methods of Homological Algebra, the end of Section II.5, they make the following definition:

Let $Y$ be an object of an abelian category. An element of $Y$ is a pair $(X,h)$, with $h: X \to Y$, modulo the equivalence relation that $(X,h) \sim (X',h')$ if we can complete the square

$$\begin{matrix} Z & \to & X' \\ \downarrow & & \downarrow \\ X & \to & Y \end{matrix}$$

so that the maps $Z \to X$ and $Z \to X'$ are surjective.

The map sending an object $Y$ to its elements, $E(Y)$, is clearly a functor from our Abelian category to PointedSetsWithAnInvolution, where the labelled point of $E(Y)$ is the zero map $0 \to Y$ and the involution is $(X,h) \mapsto (X,-h)$. (It seems to me that $(X,h)$ and $(X,-h)$ are always equivalent, but G+M sometimes use notation which seems to distinguish the elements $e$ and $-e$, so I am following them.) Gelfand and Manin state as exercises:

• A map $f: Y_1 \to Y_2$ is a monomorphism iff $E(f)^{-1}(0) =0$ iff $E(f)$ is injective.
• A map $f: Y_1 \to Y_2$ is a epimorphism iff $E(f)$ is surjective.
• A map $f: Y_1 \to Y_2$ is zero iff $E(f)$ is zero.
• A sequence $Y_1 \to Y_2 \to Y_3$ is exact iff, for $e \in E(Y_2)$, the element $e$ is taken to the element $0 \in E(Y_3)$ if and only if it is in the image of $E(Y_1)$.
• If $y_1$ and $y_2 \in E(Y)$ then there is an element $z \in E(Y)$ such that, for any $f: Y \to Y'$ with $f(y_i)=0$, we have $f(z)=(-1)^i f(y_{1-i})$. Moreover, if $g: Y \to X$ is any map such that $g(y_1) = g(y_{2})$, we can take $z$ such that $g(z)=0$. (So $z$ acts like $y-y'$. Note that there is not claimed to be a unique $z$ which works.)

G and M then give several examples to demonstrate that most diagram chasing arguments can be rewrittten using the $E$ construction.

-
That is more or less equivalent to MacLane's 'members'. – Mariano Suárez-Alvarez Dec 29 '09 at 19:54
I think that what Greg wants is an algorithm (or something...) which given (i) a commutative diagram shape $D$ decorated with additional conditions (exactnesses, maybe something else) and (ii) a functorial construction that from each instance of a diagram of shape $D$ constructs a diagram of another shape $D'$, and (iii) a set $C$ of additional conditions applicable to diagrams of shape $D'$, decides whether the derived diagram $D'$ always satisfies the conditions $C$ or not. (As long as the diagramas are small, it is enough to consider the category of abelian groups) – Mariano Suárez-Alvarez Dec 29 '09 at 20:08

This answer is a response to Daniel Litt's answer above. First, let me distill his point. Given a diagram of finite-dimensional vector spaces, every term $A$ has a dimension which is a non-negative integer. In addition, every morphism $f:A \to B$ has a non-negative rank which is at most $\min(\dim A,\dim B)$. If a pair of morphisms $$A \stackrel{f}{\longrightarrow} B \stackrel{g}{\longrightarrow} C,$$ then you get a linear relation $$\mathrm{rank}\ f + \mathrm{rank}\ g = \dim B.$$ Thus, there is an integer programming problem to express whether the dimensions and ranks are feasible. Since such an integer programming problem is homogeneous, you can instead treat it as a rational linear programming problem and later clear denominators. There is an algorithm to determine feasibility, even a polynomial time algorithm. As Daniel points out, this is enough to establish the nine lemma in the special case of finite-dimensional vector spaces. The argument/algorithm even works in many categories other than finite-dimensional vector spaces. For instance it works for finite abelian groups. On the other hand, the algorithm doesn't use the fact that any polygons in the diagram commute (see below), other than perhaps a preprocessing stage in which commutative polygons are filled in by commutative triangles.

Like me, Daniel asked to restrict to acyclic diagrams. However, I realized that this restriction is ineffectual for my entire question. (Thus, his algorithm can't need it.) You can convert any diagram into an acyclic one using the fact that $$0 \longrightarrow A \stackrel{\phi}{\longrightarrow} A' \longrightarrow 0$$ makes $\phi$ into an isomorphism. If $\mathcal{D}$ is a diagram, you should first triangulate all commutative polygons in to make commutative triangles. Then make three copies $A, A', A''$ of each object $A \in \mathcal{D}$ together with isomorphisms $$A \stackrel{\phi}{\longrightarrow} A' \stackrel{\phi'}{\longrightarrow} A'.$$ Then a homomorphism $f:A \to B$ in $\mathcal{D}$ can be expressed acyclically as this commutative square: $$\begin{matrix} A & \stackrel{f}{\longrightarrow} & B' \\ \downarrow && \downarrow \\ A' & \stackrel{f'}{\longrightarrow} & B'' \end{matrix}$$ Finally, a commutative triangle $h = f \circ g$ can be expressed as a commutative square $h' \circ \phi = f' \circ g$. Or if $f$ and $g$ are an exact pair, you can require that $f'$ and $g$ make an exact pair.

Daniel also says without explanation that if there is a solution to the dimension and rank equations, then there are ways to fill in all of the maps. But without a lot more work, I don't think that this inference is reasonable. The hard part is satisfying commutative triangles. It is certainly not true that there is simply a canonical choice for each map using a skeleton $\{k^n\}$ of the category of finite-dimensional vector spaces. Because, if $f$ and $g$ each have some rank, then their composition $f \circ g$ might also have some desired rank, and that rank depends on the choices of $f$ and $g$. One interesting remark here is that $$\mathrm{rank}\ f \circ g \le \min(\mathrm{rank}\ f,\mathrm{rank}\ g),$$ and there is a similar inequality on the other side. However, I think that there is more going on than that.

Finally, it is worth giving a simple example to show that feasibility in finite-dimensional vector spaces is not the same as feasibility in vector spaces. Given the exact sequence $$0 \longrightarrow A \longrightarrow A \longrightarrow A \longrightarrow 0,$$ you can conclude (using the dimension equations that Daniel suggests) that $A = 0$ if it is finite-dimensional. But if it is infinite-dimensional, then there are non-trivial solutions.

-
This is exactly what I had in mind! That said, I think there are some problems with other parts of your answer. First, I'm not convinced this works in finite Abelian groups; there orders multiply, so the problem is a "multilinear programming problem", which I at least know nothing about (can we do this?). Second, your acyclicity reduction does not work as far as I can tell--you've managed to separate all the objects, but the number of maps can still be unbounded. E.g. there might be a nilpotent map $A\to A$ which can have unbounded order. – Daniel Litt Jun 24 '10 at 13:15
Two more issues--as for polynomial time, I believe this if we are given a "complete" diagram already--I'm not so sure about the time complexity of the first step in my answer. I actually think that the realizability of solutions is not too hard; I'll sketch a solution in my answer in a bit. This is a very nice explanation by the way. – Daniel Litt Jun 24 '10 at 13:18
(1) For finite abelian groups it's the same linear programming problem over and over again for each prime $p$. (2) I hadn't thought through the acyclic conversion, so my explanation was inadequate, but I managed to work it out. (3) In my version of your proposal, everything is clearly a polynomial amount of work. It's neither necessary nor helpful to write down all exact paths in the diagram. – Greg Kuperberg Jun 24 '10 at 15:10
Hmm---how do you deal with the possibility of an unbounded number of maps? E.g. triangulating the polygon $A\to A$ can add an unlimited number of maps. Anyway, the reason I add in all images, cokernels etc. is for the feasability argument I sketch above. (I also am surprised your version of this argument can prove the nine lemma--I couldn't do it without adding in certain "natural maps" bewteen images.) For example, how do you prove that the composition of the two maps in the last row is zero? – Daniel Litt Jun 24 '10 at 15:44
Also, your linear programming argument for $p$-th powers is very clever! Can we find some transfer theorem that says "in X circumstances, a theorem holding in $Vect(k)$ holds in all Abelian categories"? Your $0\to A\to A\to A\to 0$ example is an obstacle, but it would be nice to have this algorithm be useful in the general Abelian category case. – Daniel Litt Jun 25 '10 at 14:15

This was originally going to be a rather different post, but I realized that my argument could perhaps be adapted into an (ineffective) algorithm, if it's possible to patch up the hole. At the very least, I should say some things which might be obvious but wasn't to me until I saw it, and so might not be obvious to someone else either.

Let's fix the abelian category to be the category of finite-dimensional vector spaces over GF(2). We have a decorated diagram of the type Greg describes. Then it's easy to see that the non-exactness of two composable arrows is in RE -- we can have a prover just give us a counterexample, and since everything's finite-dimensional, we're good. So the "diagram chasing decision problem" is in coRE.

If we could effectively bound the dimensions of the vector spaces in a counterexample, of course, we'd have that the problem was recursive. At least for finite-dimensional vector spaces over a finite field. But I don't know how this is possible. My question, though: is it possible to get around the need for an effective bound somehow? I think you can get a complexity-theoretic improvement by letting the prover compute everything as a black box and "checking for honesty" on logarithmic-sized subspaces, but I might be misremembering. Is there some extraordinarily clever way to do something like this for computability? (I'm thinking about results like the necklace reconstruction problem, or problem B6 on this year's Putnam exam, although in both of those cases the "uniform bound" hides a lot of information that doesn't seem to have anyplace to go in this scenario...)

Actually, I guess really the only scenario to worry about would be if the dimensions in the smallest counterexample to exactness of some pair grew faster than any computable function of the size of the diagram, right? Otherwise we have that the problem is in co-NSPACE(BigFunction(n)), and so it's in NSPACE(BigFunction(n)). That kind of growth rate seems implausible, but again I have no idea how to prove it's impossible.

-
One reasonable interpretation is bounds on both sides, as you suggest. (And you have to do this to match the rigorous question that I posted.) But another solution would be something like an equational theory that puts the diagram in a canonical form, without necessarily obtaining all logical truths. – Greg Kuperberg Dec 30 '09 at 8:26