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_{1}-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."?

A Combinatorial Approach to Matrix Theory and its Applications, although I haven't looked at it very thoroughly. $\endgroup$ – Qiaochu Yuan Jun 17 '11 at 23:46