A mystery about graphs and matrices

This is the story of a question I’ve been pondering off and on for about a decade now. I’m writing this down mostly because it makes for some enjoyable pondering, but it would be nice if someone has an interesting answer that I’ve missed.

Definitions

For the purposes of this post, when I say “graph”, I’m going to mean a finite directed graph, which is allowed to have multiple parallel edges and self-loops (edges from a vertex back to itself). This is sometimes called a quiver, if you’re picky about your words, but I’m just going to say graph because it’s what I’m accustomed to.

A graph has an adjacency matrix, which is just a square matrix with a row and column for each vertex, where the entry in row i and column j is the number of edges from vertex i to vertex j. For the graph above, if the vertices are x, y, and z in that order, the adjacency matrix is

    [ 0 1 1 ]
A = [ 0 1 1 ]
    [ 0 1 1 ]

This matrix is often called A (for “adjacency”). It turns out that another matrix that comes up a lot for quivers is I - A, the identity matrix minus the adjacency matrix. For the graph above, again, this matrix is

        [ 1 0 0 ]   [ 0 1 1 ]   [  1 -1 -1 ]
I - A = [ 0 1 0 ] - [ 0 1 1 ] = [  0  0 -1 ]
        [ 0 0 1 ]   [ 0 1 1 ]   [  0 -1  0 ]

The question I have is this one: What does the determinant of the matrix I - A really mean?

If you compute the determinant for the example above, you get -1. But why? What does that -1 tell us about the graph?

I know a few answers to this question. None of them are entirely satisfying, but I’ll state them because it sheds some light on ways to think about the question.

Answer #1: It’s the size of the Bowen-Franks Group.

The first answer is that the determinant tells us the number of elements in the Bowen-Franks group, which is the cokernel of I - A. Okay, that was just a lot of terminology, so let me explain. Here’s that graph again.

Here’s a game you can play. Place some number of tokens on each of the vertices of the graph to start. As a move in this game, you can remove a token from any vertex, and in exchange place a new token at the end of each edge leaving that vertex. For instance, if you picked up a token from y, the two edges leaving y are b and e, they point to y again, and z. So you would add a token back to y as well as a token to z. I’ll also let you do this in reverse, so you can remove a token each from y and z, and replace a token on y.

Your goal in this game is reach some target state. Can you do it? Well, maybe, or maybe not, depending on the graph and the starting state and the goal!

(There’s one reason you might not be able to do it which we won’t care about, and that’s that you just don’t have enough tokens. For instance, if I give you no tokens to start with, by the rules above, you cannot do anything. Let’s agree to fix that by letting you go in token-debt, so long as you can replace the missing tokens later. So if there are no tokens on y, you can still apply the same rule above to remove a token from y, leaving -1 tokens there; but then you’ll add tokens back to y and z, leaving you with 0 tokens on y again, but an extra token on z.)

If we allow token-debt as I described above, I claim you can always accomplish any goal from any starting point, with the graph above. And I know that because the determinant of I - A is -1. (Okay, I also know it because I see a strategy: To add or remove tokens at y or z, just apply or reverse the rule at the other one. To add or remove a token at x, do it at both y and z, then use the rule at x.)

But there are definitely some impossible versions of this puzzle. Suppose I give you this graph instead.

If we label the vertices from left to right as x, y, and z, the first two exchange rules in our game tell us that we can exchange an x for both a y and a z, and we can exchange a y for a z. By doing both, we can exchange an x for two z’s. So you need only worry about how many z’s you have: any x or y can be traded in for an equivalent number of z’s. But the third rule tells you that a z can be exchanged for an x, a y, and a z, which adds up to four z’s worth of tokens.

An interesting conclusion you can reach is this. No matter what you do, if you start with tokens worth some multiple of three z’s, it will stay that way. So there is no way to start with 3 z’s, and end up with 2 z’s. That version of this puzzle simply cannot be done!

I didn’t have to work so hard, though. All I really needed to do was this calculation:

    [ 0 1 1 ]
A = [ 0 0 1 ]
    [ 1 1 1 ]
        [ 1 0 0 ]   [ 0 1 1 ]   [  1 -1 -1 ]
I - A = [ 0 1 0 ] - [ 0 0 1 ] = [  0  1 -1 ]
        [ 0 0 1 ]   [ 1 1 1 ]   [ -1 -1  0 ]
det(I - A) = -3

Because the determinant of I - A is -3, I know there are three different states you can be stuck in, with no way in the game to get from one of these states to another. Those three states are described by the remainder when you divide you your number of z’s by 3.

Gene Abrams, at the University of Colorado at Colorado Springs, likes to describe these kinds of puzzles as “mad veterinarian” problems, where a mad veterinarian invents a machine for turning one animal into some collection of other animals. Like our rules above, the machine works both forward and backward, and the veterinarian can always borrow an animal as long as they can replace it in the end.

But what does this have to do with the matrix I - A? To answer this, imagine I have a collection of animals to run through the machine (or tokens to exchange for other tokens). I can write down how many I have of each type in a vector v. What will I get out of the exchange? The answer is Av, the result of multiplying the matrix A by the vector v. You’re losing the originals, so the net proceeds of the exchange will be Av - v, also known as (A - I) v. Running this in reverse nets you (I - A) v. So there’s that I - A matrix! In fact, to compute the groups of equivalent states you could get stuck in, you can just answer this question: if we assumed that a change of (I - A) times any vector in tokens is unimportant (that is, equivalent to zero), what structure is left? That’s called the cokernel of I - A.

I don’t know an easy argument off the top of my head for why the absolute value of the determinant always gives you the size of the cokernel, but it’s true. If the determinant is zero, then there are infinitely many distinct states; but otherwise, its absolute value is the number of distinct states. That’s why a determinant of -1 told me there are no impossible puzzles with the first graph above. If there’s only 1 state, then you can get from anything to anything else. But a determinant of -3 told me there are impossible puzzles with the second graph. If there are three unconnected states, then the puzzle is impossible if the starting point is chosen from a different state than the goal.

This is actually a great answer to my question. Indeed, something like this exchange game can be directly seen in settings where this determinant matters. In ring theory applications, for instance, this exchange game corresponds directly to isomorphisms between finitely generated projective modules. But this answer doesn’t tell us anything at all about the sign of the determinant. Regardless of whether the determinant is a positive or negative 3, the same three disconnected states exist in the exchange game. It’s interpreting the sign of the determinant where things get more puzzling.

(Note that above I - A seemed to be specifically connected to reversing the exchange rules, while A - I was the relevant matrix for doing the exchange rules in the forward direction. These matrices will always have the same absolute value of their determinant, but they will sometimes have different signs. So the sign may have something to do with the direction of exchange in the game? Incidentally, the determinant of A - I is definitely not as interesting, at least in the ways that I - A is. See the last section for the motivation here.)

Answer #2: It’s about vertex-disjoint sets of circuits

Let’s go back to the original question. What does the determinant (in particular, its sign) tell us about the graph? The token games (or mad veterinarian puzzles) above don’t seem to have anything to tell us about the sign. So we need to look elsewhere.

A long time ago, I managed to find another interpretation for the determinant, in terms of what I called vertex-disjoint sets of circuits in the graph.

A cycle in a graph is just a path you can follow from some vertex through a distinct set of other vertices, and end up back where you started. Here’s one of those graphs again:

There are four cycles in this graph:

• The edge b is a cycle by itself
• The edge f is a cycle by itself
• The path ce (that is, c followed by e) is a cycle
• Annoyingly, ec is a different cycle. You might think this is the same cycle as ce; but the standard terminology is that it’s not.

For the rest of this section, I really need ce and ec to be the same thing, so I’m going to define (and as far as I know this is not particularly standard terminology) a circuit to be the set of edges in a cycle, without regard to order. So the graph above has four cycles, but it has only three circuits.

Then I can ask this question: consider all possible subsets of the circuits in the graph. Furthermore, restrict to those that don’t reuse any vertices. Then how many of these subsets have an even number of circuits, and how many have an odd number? This graph has:

• The empty set, which has even size.
• The singleton sets: { b }, { f }, and { ce }, which are odd-sized. (Remember that as circuits, ce and ec are the same.)
• The set { b, f }, which is even-sized.

That’s all, since if you try to combine ce with either of b or f, you’re forced to reuse a vertex, which isn’t allowed. So this graph has two even-sized vertex-disjoint sets of circuits, and three odd-sized vertex-disjoint sets of circuits.

About ten years ago, I was able to write down a proof (though an ugly one) that the determinant of I - A is equal to the number of even-sized vertex-disjoint sets of circuits, minus the number of odd-sized vertex-disjoint sets of circuits.

The problem here is that I don’t really know how to interpret this difference as anything interesting. Why do even-sized or odd-sized sets of circuits matter anyway? What do that really say about the graph?

An interesting and trivial result that sheds some light on the interpretation is this: for any non-empty set, its number of even-sized subsets is always the same as its number of odd-sized subsets. (Quick proof: Choose any x in the set S, and let R = S \ {x}. The odd-sized subsets of S consist of precisely the odd-sized subsets of R, as well as the even-sized subsets of R with x added, so there are just as many of them as there are subsets of R in total. The opposite argument for the even-sized subsets of S, so there are also just as many of them as subsets of R.) So if you drop the vertex-disjoint requirement in this interpretation, then the answer is always zero! Then this interpretation tells us something about the ways that different circuits share vertices.

But so what? In general, in any graph where there are a lot of circuits, there are huge (exponentially) numbers of these subsets, and the arithmetic seems to come out right almost by accident.

Here’s an example of the kind of reasoning that pops out of this. There’s a trick for changing the sign of det(I - A) for a graph, known as the Cuntz splice.

Basically, you pick any vertex of a graph (called v in the diagram) and attach a new subgraph there, with two extra vertices and four extra circuits. So, can we justify that the Cuntz splice really flips the sign on the determinant of I - A? Here’s how I’d proceed using this result. Looking just at the original graph, let:

• A = the even-sized vertex-disjoint sets of circuits that use the vertex v.
• B = the even-sized vertex-disjoint sets of circuits that don’t use v.
• C = the odd-sized vertex-disjoint sets of circuits that use the vertex v.
• D = the odd-sized vertex-disjoint sets of circuits that don’t use v.

Then for the original graph, this result shows that det(I - A) = |A| + |B| - |C|- |D|. But what about the new graph? Let’s label the four new circuits from left to right as x, y, z, and w (so y and w are the two loops). Then we can find the following even-sized sets of circuits:

• Everything in A and B. Count: |A| + |B|
• Everything in A and B, but with y and w added. Count: |A| + |B|
• Everything in B, but with x and w added. Count: |B|
• Everything in C and D, but with y, z, or w added. Count: 3|C| + 3|D|
• Everything in D, but with x added. Count: |D|
• Total: 2|A| + 3|B| + 3|C| + 4|D|

And here are the odd-sized sets of circuits:

• Everything in C and D. Count: |C| + |D|
• Everything in C and D, but with y and w added. Count: |C| + |D|
• Everything in D, but with x and w added. Count: |D|
• Everything in A and B, but with y, z, or w added. Count: 3|A| + 3|B|
• Everything in B, but with x added. Count: |B|
• Total: 3|A| + 4|B| + 2|C| + 3|D|

Subtracting the latter from the former gives: -|A| - |B| + |C| + |D|. This does, indeed, flip the sign of the determinant. But I don’t have any more intuition why than I did before I wrote all that down. This doesn’t shed any light at all on what the Cuntz splice is doing, or what sort of orientation it’s changing in this graph.

It’s interesting to note that circuits play some role in the first answer, as well. In the exchange game described in the first answer, any circuit leads to a sum of tokens that is equivalent to no tokens at all. One just takes the “exits” (edges that leave some vertex of the circuit, but are not in the circuit), and adds up the vertices at the end of each exit. In some sense, these are the most interesting equivalences. (If a vertex is not part of a circuit, it doesn’t change the structure of the cokernel at all; it just adds a new vertex name that is always equivalent to existing vertices that do belong to circuits.) So there’s some hope to relate the two concepts.

Why do I care?

This isn’t just idle speculation. There are several mathematical systems we can construct from such a graph. In particular, there are three such systems:

1. The edge shift of the graph, which is a dynamical system.
2. The graph C* algebra of the graph, which is an operator algebra on a Hilbert space.
3. The Leavitt path algebra of the graph, which is an abstract algebra over an arbitrary field (or even commutative ring).

All three of the structures I described above that you can build from these graphs have some notion of equivalence (respectively: flow equivalence, sgtable isomorphism, and Morita equivalence). And in all three cases, people have asked a similar classification question: When do two graphs produce equivalent structures, and when do they produce different structures?

And, here’s where it gets really interesting: they have found very similar answers!

Let’s focus on a certain interesting set of simple graphs, called non-trivial and irreducible. They are the graphs where it’s possible to get from any vertex to any other vertex (that’s irreducible), but the graph isn’t just all one big circuit (that’s non-trivial). For these graphs, we get the following answers:

1. Edge shifts are flow equivalent precisely when they agree on both the cokernel of I - A, and the sign of the determinant of I - A. (Remember, the absolute value of the determinant is just the size of the cokernel.)
2. Graph C* algebras are stably isomorphic precisely when they agree on the cokernel of I - A, regardless of the sign of the determinant.
3. Leavitt path algebras are definitely Morita equivalent if they agree on both the cokernel of I - A and the sign of the determinant of I - A. We also know that the cokernel is definitely an invariant. However, it is an open question whether the sign of the determinant is an invariant or not.

Perhaps the situation with Leavitt path algebras matches edge shifts, and the sign of that determinant is an invariant. (That’s where my money is, and there’s some strong evidence suggesting that such an equivalence, if it exists, will be a weird one.) Perhaps they match graph C* algebras, and the sign is irrelevant. Or, perhaps the sign matter sometimes, but not others. (I hope not!)

To answer that question, it sure would be nice to have some better intuition for what the sign of that determinant really means.