One of my favorite results in algebraic combinatorics is a surprisingly useful lemma which allows a combinatorial interpretation of the determinant of certain integer matrices. One of its more popular uses is to prove an equivalence between three other definitions of the Schur functions (none of which I have given yet), but I find its other applications equally endearing.
Let 
be a locally finite directed acyclic graph, i.e. it has a not necessarily finite vertex set 
with finitely many edges between each pair of vertices such that no collection of edges forms a cycle. For example, could be 
with edges 
and 
, which we’ll denote the acyclic plane. Assign a weight 
to each edge and assign to a path the product of the weights of its edges. Given two vertices 
let 
denote the sum of the weights of the paths from 
to 
. Hence even if there are infinitely many such paths this sum is well-defined formally, and if there are only finitely many paths between two vertices then setting each weight to 
gives a well-defined non-negative integer.
Let 
and 
be a collection of vertices called sources and vertices called sinks. We are interested in 
-tuples of paths, hereafter to be referred to as -paths, sending each source to a distinct sink. Let 
be the 
matrix such that 
. Then the permanent of counts the number of -paths, but this is not interesting as permanents are hard to compute.
A -path is called non-intersecting if none of the paths that make it up share a vertex; in particular, each 
is sent to distinct 
. A non-intersecting path determines a permutation 
of the vertices; let the sign of a non-intersecting -path be the sign of this permutation.
Lemma (Lindström, Gessel-Viennot): 
is the signed sum of the weights of all non-intersecting -paths.
Corollary: If the only possible permutation is 
(i.e. is non-permutable), then is the sum of the weights of all non-intersecting -paths.
Proof
The idea of the proof is straightforward: one defines a sign-reversing (weight-preserving) involution on -paths so that in the signed sum only the fixed points survive and the others cancel. (This is more or less equivalent to a use of inclusion-exclusion, but in many cases in combinatorics it is more natural to define the involution directly.) The involution is roughly as follows: if a path is non-intersecting, fix it (of course). Otherwise, there is some vertex 
that two paths share as a vertex. Flip the part of the paths after , which changes the sign of the induced permutation.
The only difficulty is to make sure this is really an involution, i.e. that the same portion of path gets flipped if one applies the map twice. To ensure this, let 
be the smallest index such that the path from intersects another path and let 
be the largest index of a path which intersects the above path. These indices remain unchanged after the involution, so the vertex also remains unchanged. If you want the full details, there is a nice introduction by Benjamin and Cameron in the AMM, Vol. 112, No. 6. Benjamin and Cameron describe a nice application to the evaluation of a determinant of Catalan numbers, so I won’t describe it; it makes more sense with the diagram anyway.
Applications
Gessel and Viennot’s original motivation was precisely an application to the acyclic plane, and indeed the lemma is sometimes stated for the plane only. Let 
and 
be strictly increasing sequences of non-negative integers and define sources 
and sinks 
. The number of paths from to 
is readily verified to be 
, so is the binomial determinant
Apparently these determinants have something to do with Chern classes. When either the or the are consecutive integers, this binomial determinant has a product formula (for example, see this AoPS thread), which Gessel and Viennot prove combinatorially using their lemma.
The lemma (more or less) can be used to prove the matrix-tree theorem. I am told that this proof is in Aigner.
The lemma immediately implies that determinants are multiplicative. Actually, it implies an even stronger result, the Cauchy-Binet formula. Consider now three sets 
of vertices and construct two matrices 
, one for paths 
and the other for paths 
. Note that are not necessarily square, but 
is a square matrix counting paths 
which pass through some -vertices. Then 
counts nonintersecting paths which must therefore pass through distinct -vertices. If 
, there are no such paths. Otherwise, for every subset 
of 
of size , every -path factors as a product of -paths 
, and the signs multiply in the expected way. Letting 
denote the matrices counting such paths, it follows that
.
As a special case, if 
, then we obtain the identity
.
This identity implies that the square of the volume of a parallelpiped in 
with vertices given by the entries of is equal to the sum of the squares of the volumes of its projections to the standard copies of 
obtained by ignoring some of the coordinates. This is a high-dimensional generalization of the Pythagorean theorem, and it can also be used to prove the matrix-tree theorem. In fact, since the minors of a matrix to which Gessel-Viennot applies have almost exactly the same combinatorial interpretation as the full determinant, we even know that matrices of the form 
are positive-semidefinite. (More generally, this is true for any matrix coming from a nonpermutable graph.)
The lemma implies that non-intersecting random walks are a determinantal process, which connects them to many other mysterious processes. I wish I knew what to make of this.
Conjecture
Over the summer I conjectured that the lemma could be used to prove the identity
for 
the adjacency matrix of a finite graph . My idea was that one could construct a “blowup” 
of with the property that Gessel-Viennot applied, and Joel Lewis and I tried a few constructions that looked something like this: for each non-negative integer 
, has vertices 
where is a vertex of . For each edge 
of , has edges 
of weight 
. Finally, add the vertices 
and edges 
for each finite of weight .
Now it follows that a walk from 
to 
is precisely a walk of some length from 
to 
on of weight 
, hence 
is precisely equal to the 
entry of 
. So let the vertices be sources and the vertices be sinks.
Unfortunately, as constructed is not non-permutable. It’s possible one might be able to define a second sign-reversing involution on non-intersecting -paths in this setup, but I would really like it if could be modified to be nonpermutable. In all honesty I haven’t given this problem much thought since the summer, so it could be that the proof is relatively straightforward from here.
Like this:
Like Loading...
Related
Annoying Precision 
I’m a little confused about the idea of G being non-permutable. Is that really a property of $G$, and not a property if G,{a_i},{b_i}? It seems what $\pi$ are possible is determined by $G$ and the sources and sinks, not just G.
Yes, sorry, that was a mild abuse of notation. You need the data of the sources and sinks.
Sorry, meant “you want the sources and sinks to be…”
I think you want the sinks to be $(0,-a_i)$ and $(b_j,-b_j)$.
Yes, that sounds right. Thanks for the correction!
I’m confused by the directed plane example – if $(x,y)\to(x+1,y)$ or $(x,y+1)$ if there is a path from $(x,y)$ to $(u,v)$ then $x\leq u$ and $y\leq v$. But then there can’t be any paths from $(0,-a_i)$ to $(-b_j,-b_j)$ unless $b_j\leq 0$.
[…] 2. We will give a combinatorial proof using the Lindström-Gessel-Viennot lemma. Consider the following locally finite directed acyclic graph : the vertices are the set of pairs […]
“The lemma immediately implies that determinants are multiplicative.”
No, it doesn’t. You would have to know that (almost) all determinants can be realized as nonpermutable path configurations.
“Immediately” was a bit of an overstatement. The argument I had in mind is that the multiplicativity of the determinant is a polynomial identity in
variables and that Lindstrom-Gessel-Viennot supplies enough cases of this identity to prove it, although this isn’t obvious and ought to require some work.
Dear Qiaochu,
my apology for the mistaken heading of my comment- maybe you can correct that.
–Yuval
Terry,
The lemma you ascribe to Lindstrom, Gessel and Viennot has many wonderful applications, some of which were discovered by these authors. However, the lemma itself was discovered earlier, in great generality, by Karlin and McGregor in their two celebrated papers
MR0114248 (22 #5072) Karlin, Samuel; McGregor, James Coincidence probabilities. Pacific J. Math. 9 1959 1141–1164.
MR0114247 (22 #5071) Karlin, Samuel; McGregor, James Coincidence properties of birth and death processes. Pacific J. Math. 9 1959 1109–1140.
Except for the difference in Language (probability versus combinatorics) the theorem is essentially the same
as in Lindstrom (1973) and Gessel-Viennot (1985) but a lot earlier. We present a special case of the Karlin-McGregor result in page 54 of our book http://www.ams.org/bookstoregetitem/item=ulect-51 available online at http://stat-www.berkeley.edu/~peres/GAF_book.pdf .
We also sketch there an alternative analytic argument that we learned from S.R.S Varadhan. In a 1989 follow-up to their 1985 paper http://people.brandeis.edu/~gessel/homepage/papers/pp.pdf
Gessel and Viennot acknowledged priority to Lindstrom, and mentioned Karlin and McGregor for “related results”, perhaps without realizing that Karlin and McGregor already knew the
whole story. –Yuval
Interesting, but not entirely surprising. In my opinion this is a fundamental property of the determinant.