How much linear algebra can be done with graphs?

Question

Let G be a finite directed acyclic graph, with sources $A=\{a_1,\ldots,a_n\}$ and sinks $B=\{b_1,\ldots,b_n\}$, with edge weights $w_{ij}$. The weight of a directed path P is the product of weights of edges in P. Set
$e(a,b)= \sum\limits_{P\colon\, a\to b}w(P).$
Then we can form a matrix $M=\left(e(a_i,b_j)\right)_{i,j}$, and the Lindström-Gessel-Viennot(-Karlin-MacGregor) Lemma tells us that the determinant of M is the signed sum of all n-tuples of non-intersecting paths from A to B.
$\det(M)=\sum\limits_{(P_1,\ldots,P_n)\colon\,A\to B} \mathrm{sign}(\sigma(P))\prod\limits_{i=1}^n w(P_i)$.

This is an extremely beautiful result, and indeed, it makes sense to take it as the definition of the determinant (maybe Kasteleyn-Percus is even better). In the context of quantum topology, graphs naturally occur, and it seems to me that determinants appear because we are (or should be) counting n-tuples of weighted non-intersecting paths.
If this is the case, then my question, in some sense, is why we need matrices at all. Finite directed acyclic weighted graphs carry more information than mere matrices, they appear naturally, and it seems a shame to trade them in for puny matrices just in order to do some linear algebra. So I'd like to ask whether I can do all of the linear algebra which I need directly off the graph:

Question 1: The above lemma gives us a graph-theoretical definition of the determinant. Is there a corresponding purely graph-theoretical definition of eigenvalues? Is anything at all known beyond the determinant? Edit: What I really want is the signature and the rank- the rest is just fishing for what is possible.

In the context in which I am most interested, the weights are valued in a non-commutative (skew-power-series) ring. Is the Lindström-Gessel-Viennot Lemma valid in this context? Are there any references? (My naive search on Zentralblatt and MathSciNet didn't turn anything up).

Question 2: Over a skew-power-series ring (or over some more general nice class of noncommutative rings), does the signed sum of all n-tuples of non-intersecting paths from A to B recover the K₁-class of M?

Finally, to understand the big picture a little bit better, is there a reference for what Qiaochu said about the meaning of the (Lindström-Gessel-Viennot) determinant, as coming from some sort of quantum mechanics picture, where "the entries of the matrix describe transition amplitudes and that the determinant is an alternating sum over transition amplitudes in which "histories" of n particles can constructively or destructively interfere."? Does it make (physical?) sense to say something like "Graph G is a Feynman diagram. Shine light through the sources. The determinant is the amount of light you see at the sinks."?

Answer 1

I will try to contribute a partial answer. First I want to comment on the Lindstrom-Gessel-Viennot determinant coming from quantum mechanics stuff, in physics this is known as the Slater determinant, giving the formula for the wavefunction of a multi-fermionic system. This gives a nice picture to think of LGV as yet another instance of the Boson-Fermion correspondence. In the boson case, one allows all paths and obtains the total number as the permanent of the LGV matrix (this is obvious from the definition of the permanent), and in the fermion case one gets a system with states counted by the determinant of the LGV matrix. Of course the non-intersecting part comes into play because fermions in addition satisfy the Pauli exclusion principle, therefore they cannot occupy the same site at the same time.

Now, LGV and related results have an interesting history even in fields other than combinatorics. Fisher, in "Walks Walls, Wetting and Melting" 1984, considered the vicious walkers model in statistical mechanics, which considers mutually avoiding directed lattice paths. From this perspective it is interesting to look at some configurations which aren't solved by the usual LGV theorem, for instance when the paths are allowed to intersect at vertices but not edges, or when two paths are allowed to intersect in at most 2 consecutive vertices (the terminology for this classification is $n$-friendly walkers, see here). Viennot and others considered such variants after the relation between the combinatorics of lattice paths and statistical mechanics was established, it turns out that some of these models also have determinantal formulas associated to them. One main article is "From the Bethe Ansatz to the Gessel-Viennot Theorem" by R. Brak, J. W. Essam, and A. L. Owczarek, the point here is that LGV related results can be proven using transfer matrix methods as well, which is a powerful point of view in light of the models I mentioned above where the usual LGV fails (i.e. outside of the six vertex model).

Now if you need something more rigorous relating LGV matrices to fermion models, this can be done, but it doesn't seem to have been written nicely anywhere. Sometimes this is mentioned in the literature in the case of graphs like $\mathbb Z^2$, see for example "Domino tilings and the six-vertex model at its free fermion point" by P.L. Ferrari and H. Spohn, but I believe there should be a more general setting to talk about this. If you take the point of view that Greg Kuperberg mentioned in his answer to this previous MO question, that Kasteleyn-Percus matrices are essentially equivalent to LGV matrices, then I believe there is more literature on interpreting these as models of Majorana fermions living on the graph. The article I'm thinking of is "Dimer Models, Free Fermions and Super Quantum Mechanics" by Dijkgraaf, Orlando and Reffert.

As a last note, I wanted to say that I don't fully understand your motivation to want to identify every occurrence of the determinant with a LGV (or Kasteleyn-Percus) context, given that even within graph theory there are families of objects (even paths or random walks, as mentioned above) which are counted by determinants of a different sort of flavor. As to the question about non-commutative weights to LGV, I can't offer any insight, except perhaps to suggest looking at previous work on non-commutative extensions of the LGV theorem, such as the extension proved in "Noncommutative Schur Functions and their Applications" by Fomin and Greene (available from Fomin's website). But this is probably not very useful since even in their case the ring is almost commutative.

---

With regard to your question on rank and signature, there is a lot one could explore. As a start, if you look at the Laplacian matrix associated to a graph, then the rank has a clear combinatorial meaning, it measures the number of connected components of the graph (well, the maximum number of edges in an acyclic spanning subgraph, to be more precise), but there is not much to say about the signature since all eigenvalues of the Laplacian are nonnegative. When it comes to the adjacency matrix of the graph, the connection to combinatorial quantities gets even weaker (but it is an area of research), for example the rank of the adjacency matrix was conjectured to have something to do with the chromatic number of the graph, but the relation can not be so nice as was shown by Alon and Seymour. There has been some work on interpreting the signature of the adjacency matrix as well, with some early articles by Torgasev (for example here), but it is of similar nature. One can compute rank and signature easily by linear algebra methods and therefore hopes to use these to bound graph-theoretic quatities, but apparently not the other way around.

Answer 2

Well, unlike the determinant, the eigenvalues of an integer matrix aren't integers, so I don't know how much to expect here as far as a direct combinatorial interpretation of any kind. However, there is always the following: if $A$ is the adjacency matrix of a finite graph, then $\text{tr } A^n$ is the number of closed walks of length $n$, and it is also the sum of the $n^{th}$ powers of the eigenvalues. So knowing this sequence is equivalent to knowing the multiset of eigenvalues, and both of these are equivalent to knowing what I think is called the "path zeta function" $\frac{1}{\det(I - At)}$ of the graph (which I've written a little about here and here). I don't know exactly what you want eigenvalues for so I'm not sure if this is helpful.

Answer 3

To answer your first question, you can always interprete vectors as weights on the vertices. In this case, $\lambda$ is an eigenvalue with eigenvector $v$ if for each vertex, the sum of the weights of the neighbouring vertices is the product of the weight of the vertex and the eigenvalue.

$$\lambda v_i = \sum_{j \text{ neighbour of } i} v_j$$

There is only so much knowledge about the eigenvalues of graphs. We have a good understanding of the largest eigenvalue (the Perron-Frobenius one) and understanding the second largest relates to the notion of expansion, but as far as I know, all of this is done using linear algebra and not the other way around.