Feeds:
Posts

## The Lindström-Gessel-Viennot lemma

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 $G$ be a locally finite directed acyclic graph, i.e. it has a not necessarily finite vertex set $V$ with finitely many edges between each pair of vertices such that no collection of edges forms a cycle. For example, $G$ could be $\mathbb{Z}^2$ with edges $(x, y) \to (x, y + 1)$ and $(x, y) \to (x + 1, y )$, which we’ll denote the acyclic plane. Assign a weight $w(e)$ to each edge and assign to a path the product of the weights of its edges. Given two vertices $a, b$ let $e(a, b)$ denote the sum of the weights of the paths from $a$ to $b$. 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 $1$ gives a well-defined non-negative integer.

Let $a_1, ... a_n$ and $b_1, ... b_n$ be a collection of vertices called sources and vertices called sinks. We are interested in $n$-tuples of paths, hereafter to be referred to as $n$-paths, sending each source to a distinct sink. Let $\mathbf{M}$ be the $n \times n$ matrix such that $\mathbf{M}_{ij} = e(a_i, b_j)$. Then the permanent of $\mathbf{M}$ counts the number of $n$-paths, but this is not interesting as permanents are hard to compute.

A $n$-path is called non-intersecting if none of the paths that make it up share a vertex; in particular, each $a_i$ is sent to distinct $b_i$. A non-intersecting path determines a permutation $\pi$ of the vertices; let the sign of a non-intersecting $n$-path be the sign of this permutation.

Lemma (Lindström, Gessel-Viennot): $\det \mathbf{M}$ is the signed sum of the weights of all non-intersecting $n$-paths.

Corollary: If the only possible permutation is $\pi = 1$ (i.e. $G$ is non-permutable), then $\det \mathbf{M}$ is the sum of the weights of all non-intersecting $n$-paths.

Proof

The idea of the proof is straightforward: one defines a sign-reversing (weight-preserving) involution on $n$-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 $v$ that two paths share as a vertex. Flip the part of the paths after $v$, 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 $i$ be the smallest index such that the path from $a_i$ intersects another path and let $j$ be the largest index of a path which intersects the above path. These indices remain unchanged after the involution, so the vertex $v$ 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 $0 \le a_1 < ... < a_k$ and $0 \le b_1 < ... < b_k$ be strictly increasing sequences of non-negative integers and define sources $(0, -a_i)$ and sinks $(b_i, -b_i)$. The number of paths from $(0, -a_i)$ to $(b_j, -b_j)$ is readily verified to be ${a_i \choose b_j}$, so $\det \mathbf{M}$ is the binomial determinant

$\displaystyle \det \left( {a_i \choose b_j} \right)_{1 \le i, j \le k}.$

Apparently these determinants have something to do with Chern classes. When either the $a_i$ or the $b_i$ 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 $a_1, ... a_n, b_1, ... b_m, c_1, ... c_n$ of vertices and construct two matrices $\mathbf{M}, \mathbf{N}$, one for paths $a \to b$ and the other for paths $b \to c$. Note that $\mathbf{M}, \mathbf{N}$ are not necessarily square, but $\mathbf{MN}$ is a square matrix counting paths $a \to c$ which pass through some $b$-vertices. Then $\det \mathbf{MN}$ counts nonintersecting paths $a \to c$ which must therefore pass through distinct $b$-vertices. If $m < n$, there are no such paths. Otherwise, for every subset $S$ of $\{ 1, 2, ... m \}$ of size $n$, every $n$-path $a \to c$ factors as a product of $n$-paths $a \to b_S, b_S \to c$, and the signs multiply in the expected way. Letting $\mathbf{M}_S, \mathbf{N}_S$ denote the matrices counting such paths, it follows that

$\displaystyle \det \mathbf{MN} = \sum_S \det \mathbf{M}_S \det \mathbf{N}_S$.

As a special case, if $\mathbf{N} = \mathbf{M}^T$, then we obtain the identity

$\displaystyle \det \mathbf{MM}^T = \sum_S \left( \det \mathbf{M}_S \right)^2$.

This identity implies that the square of the volume of a parallelpiped in $\mathbb{R}^m$ with vertices given by the entries of $\mathbf{M}$ is equal to the sum of the squares of the volumes of its projections to the standard copies of $\mathbb{R}^n$ 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 $\mathbf{MM}^T$ 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

$\displaystyle \det (\mathbf{I} - \mathbf{A} t)^{-1} = \sum_{n \ge 0} \left( \text{tr Sym}^n \mathbf{A} \right) t^n$

for $\mathbf{A}$ the adjacency matrix of a finite graph $G$. My idea was that one could construct a “blowup” $G'$ of $G$ 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 $k$, $G'$ has vertices $(v, k)$ where $v$ is a vertex of $G$. For each edge $u \to v$ of $G$, $G'$ has edges $(u, k) \to (v, k+1)$ of weight $t$. Finally, add the vertices $(v, \infty)$ and edges $(v, k) \to (v, \infty)$ for each finite $k$ of weight $1$.

Now it follows that a walk from $(v_i, 0)$ to $(v_j, \infty)$ is precisely a walk of some length $k$ from $v_i$ to $v_j$ on $G$ of weight $t^k$, hence $e((v_i, 0), (v_j, \infty))$ is precisely equal to the $ij$ entry of $(\mathbf{I} - \mathbf{A} t)^{-1}$. So let the vertices $(v_i, 0)$ be sources and the vertices $(v_j, \infty)$ be sinks.

Unfortunately, as constructed $G'$ is not non-permutable. It’s possible one might be able to define a second sign-reversing involution on non-intersecting $n$-paths in this setup, but I would really like it if $G'$ 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.

### 12 Responses

1. 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.

2. Dear Qiaochu,
my apology for the mistaken heading of my comment- maybe you can correct that.
–Yuval

3. “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 $2n^2$ 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.

4. […] 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 […]

5. on July 29, 2013 at 7:08 am | Reply Thomas Andrews

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$.

6. on July 29, 2013 at 7:09 am | Reply Thomas Andrews

I think you want the sinks to be $(0,-a_i)$ and $(b_j,-b_j)$.

• Yes, that sounds right. Thanks for the correction!

7. on July 29, 2013 at 7:28 am | Reply Thomas Andrews

Sorry, meant “you want the sources and sinks to be…”

8. on July 29, 2013 at 7:33 am | Reply Thomas Andrews

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.