Return to Answer

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.

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.

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.

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 <a href"http://www.sciencedirect.com/science/article/pii/S0378375801001586">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.

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.