Lindström–Gessel–Viennot lemma

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths.

Statement[edit]

Let G be a locally finite directed acyclic graph. This means that each vertex has finite degree, and that G contains no directed cycles. Consider base vertices  A = \{ a_1, \ldots, a_n \} and destination vertices  B = \{ b_1, \ldots, b_n \}, and also assign a weight \omega_{e} to each directed edge e. These edge weights are assumed to belong to some commutative ring. For each directed path P between two vertices, let  \omega(P) be the product of the weights of the edges of the path. For any two vertices a and b, write e(a,b) for the sum e(a,b) = \sum_{P: a \to b} \omega(P) over all paths from a to b. This is well-defined if between any two points there are only finitely many paths; but even in the general case, this can be well-defined under some circumstances (such as all edge weights being pairwise distinct formal indeterminates, and e(a,b) being regarded as a formal power series). If one assigns the weight 1 to each edge, then e(a,b) counts the number of paths from a to b.

With this setup, write

 M = \begin{pmatrix} e(a_1,b_1) & e(a_1,b_2) & \cdots & e(a_1,b_n) \\ e(a_2,b_1) & e(a_2,b_2) & \cdots & e(a_2,b_n) \\ \vdots & \vdots & \ddots & \vdots \\ e(a_n,b_1) & e(a_n,b_2) & \cdots & e(a_n,b_n) \end{pmatrix} .

An n-tuple of non-intersecting paths from A to B means an n-tuple (P1, ..., Pn) of paths in G with the following properties:

  • There exists a permutation \sigma of \left\{ 1, 2, ..., n \right\} such that, for every i, the path Pi is a path from a_i to b_{\sigma(i)}.
  • Whenever i \neq j, the paths Pi and Pj have no two vertices in common (not even endpoints).

Given such an n-tuple (P1, ..., Pn), we denote by \sigma(P) the permutation of \sigma from the first condition.

The Lindström–Gessel–Viennot lemma then states that the determinant of M is the signed sum over all n-tuples P = (P1, ..., Pn) of non-intersecting paths from A to B:

 \det(M) = \sum_{(P_1,\ldots,P_n) \colon A \to B} \mathrm{sign}(\sigma(P)) \prod_{i=1}^n \omega(P_i).

That is, the determinant of M counts the weights of all n-tuples of non-intersecting paths starting at A and ending at B, each affected with the sign of the corresponding permutation of (1,2,\ldots,n), given by  P_i taking  a_i to  b_{\sigma(i)} .

In particular, if the only permutation possible is the identity (i.e., every n-tuple of non-intersecting paths from A to B takes ai to bi for each i) and we take the weights to be 1, then det(M) is exactly the number of non-intersecting n-tuples of paths starting at A and ending at B.

Proof[edit]

To prove the Lindström–Gessel–Viennot lemma, we first introduce some notation.

An n-path from an n-tuple (a_1, a_2, ..., a_n) of vertices of G to an n-tuple (b_1, b_2, ..., b_n) of vertices of G will mean an n-tuple (P_1, P_2, ..., P_n) of paths in G, with each P_i leading from a_i to b_i. This n-path will be called nonintersecting if the paths Pi and Pj have no two vertices in common (not even endpoints) whenever i \neq j.

Given an n-path P = (P_1, P_2, ..., P_n), the weight \omega(P) of this n-path is defined as the product \omega(P_1) \omega(P_2) \cdots \omega(P_n).

A twisted n-path from an n-tuple (a_1, a_2, ..., a_n) of vertices of G to an n-tuple (b_1, b_2, ..., b_n) of vertices of G will mean an n-path from (a_1, a_2, ..., a_n) to \left(b_{\sigma(1)}, b_{\sigma(2)}, ..., b_{\sigma(n)}\right) for some permutation \sigma in the symmetric group S_n. This permutation \sigma will be called the twist of this twisted n-path, and denoted by \sigma(P) (where P is the n-path). This, of course, generalizes the notation \sigma(P) introduced before.

Recalling the definition of M, we can expand det M as a signed sum of permutations; thus we obtain

 \det M = \sum_{\sigma\in S_n} \mathrm{sign}(\sigma) \cdot e\left(a_1,b_{\sigma(1)}\right) e\left(a_2,b_{\sigma(2)}\right) \cdots e\left(a_n,b_{\sigma(n)}\right)
= \sum_{\sigma\in S_n} \mathrm{sign}(\sigma) \cdot \sum_{P\text{ is an }n\text{-path from } \left(a_1,a_2,...,a_n\right) \text{ to } \left(b_{\sigma(1)}, b_{\sigma(2)}, ..., b_{\sigma(n)}\right)} \omega(P)

(since every factor e\left(a_i,b_{\sigma(i)}\right) is a sum over paths a_i \to b_{\sigma(i)}, and thus the product e\left(a_1,b_{\sigma(1)}\right) e\left(a_2,b_{\sigma(2)}\right) \cdots e\left(a_n,b_{\sigma(n)}\right) is a sum over n-paths from (a_1, a_2, ..., a_n) to \left(b_{\sigma(1)}, b_{\sigma(2)}, ..., b_{\sigma(n)}\right), with the summands being precisely the weights of these n-paths). Using the notion of a twisted n-path, we can simplify the right hand side of this to

\sum_{P\text{ is a twisted }n\text{-path from } \left(a_1,a_2,...,a_n\right) \text{ to } \left(b_1, b_2, ..., b_n\right)} \mathrm{sign}(\sigma(P)) \omega(P).

Now, we have to prove that this is equal to

\sum_{(P_1,\ldots,P_n) \colon A \to B} \mathrm{sign}(\sigma(P)) \prod_{i=1}^n \omega(P_i)
=\sum_{P\text{ is a nonintersecting twisted }n\text{-path from } \left(a_1,a_2,...,a_n\right) \text{ to } \left(b_1, b_2, ..., b_n\right)} \mathrm{sign}(\sigma(P)) \omega(P).

In other words, we have to prove that the sum of the terms \mathrm{sign}(\sigma(P)) \omega(P) over all twisted n-paths from \left(a_1,a_2,...,a_n\right) to \left(b_1, b_2, ..., b_n\right) equals the same sum but only over nonintersecting n-paths. This clearly is equivalent to proving that the sum of \mathrm{sign}(\sigma(P)) \omega(P) over all twisted n-paths from \left(a_1,a_2,...,a_n\right) to \left(b_1, b_2, ..., b_n\right) which are not nonintersecting vanishes.

To establish this vanishing, we will use an involution on the set of all twisted n-paths from \left(a_1,a_2,...,a_n\right) to \left(b_1, b_2, ..., b_n\right) which are not nonintersecting. This involution will have the property that it flips the sign \mathrm{sign}(\sigma(P)) (as a consequence, it has no fixed points), while leaving \omega(P) invariant. Hence, the sum of \mathrm{sign}(\sigma(P)) \omega(P) over all twisted n-paths from \left(a_1,a_2,...,a_n\right) to \left(b_1, b_2, ..., b_n\right) will have to be 0, because the involution splits it into pairs of mutually cancelling summands.

It remains to construct the involution, which we call f. Let P = \left(P_1,P_2,...,P_n\right) be any twisted n-path from \left(a_1,a_2,...,a_n\right) to \left(b_1, b_2, ..., b_n\right) which is not non-intersecting. The idea behind the definition of f is to take two intersecting paths P_i and P_j, and switch their tails after their point of intersection. However, there are (in general) several pairs of intersecting paths, which can also intersect several times; hence, a choice needs to be made (and f might fail to be an involution if this choice is done badly). We choose the following precise definition: Let i be the smallest index such that the path Pi (recall that this is the path starting at ai) contains an intersection; let m be the first (along Pi) of the points where Pi intersects other paths; and then let j be the largest index such that m lies on Pj. Then we define f(P) to be the same as P, but with the tails of the two paths Pi and Pj (that is, the parts of these two paths starting at m) switched. Clearly, f(P) is a twisted n-path, whose twist \sigma(f(P)) differs from \sigma(P) by a transposition of \sigma(i) and \sigma(j); hence, \mathrm{sign}(\sigma(f(P))) = - \mathrm{sign}(\sigma(P)). Moreover, f(P) has the same total multiset of edges as P; thus, \omega(f(P)) = \omega(P). Furthermore, it is easy to see that f is, in fact, an involution; this is because in f(P), the smallest index corresponding to an intersecting path will again be i, its first point of intersection will again be m, and the largest index of a path containing m will again be j. So we have found an involution with the desired properties, and thus proven the Lindström-Gessel-Viennot lemma.

Arguments similar to the one above appear in several sources, with variations regarding the choice of which tails to switch. A version with j smallest (unequal to i) rather than largest appears in the Gessel-Viennot 1989 reference (proof of Theorem 1).

Applications[edit]

Schur polynomials[edit]

The Lindström–Gessel–Viennot lemma can be used to prove the equivalence of the following two different definitions of Schur polynomials. Given a partition  \lambda = \lambda_1 + \cdots + \lambda_r of n, the Schur polynomial s_\lambda(x_1,\ldots,x_n) can be defined as:

  •  s_\lambda(x_1,\ldots,x_n) = \sum_T w(T),

where the sum is over all semistandard Young tableaux T of shape λ, and the weight of a tableau T is defined as the monomial obtained by taking the product of the xi indexed by the entries i of T. For instance, the weight of the tableau RSK example result.svg is  x_1 x_3 x_4^3 x_5 x_6 x_7 .

  •  s_\lambda(x_1, \ldots, x_n) = \det \left ( (h_{\lambda_i +j-i} )_{i,j}^{r \times r} \right ),

where hi are the complete homogeneous symmetric polynomials (with hi understood to be 0 if i is negative). For instance, for the partition (3,2,2,1), the corresponding determinant is

 s_{(3,2,2,1)} = \begin{vmatrix} h_3 & h_4 & h_5 & h_6 \\ h_1 & h_2 & h_3 & h_4 \\ 1 & h_1 & h_2 & h_3 \\ 0 & 0 & 1 & h_1 \end{vmatrix}.

To prove the equivalence, given any partition λ as above, one considers the r starting points  a_i = (r+1-i,1) and the r ending points  b_i = (\lambda_i + r+1-i, n), as points in the lattice  \mathbb{Z}^2 , which acquires the structure of a directed graph by asserting that the only allowed directions are going one to the right or one up; the weight associated to any horizontal edge at height i is xi, and the weight associated to a vertical edge is 1. With this definition, r-tuples of paths from A to B are exactly semistandard Young tableaux of shape λ, and the weight of such an r-tuple is the corresponding summand in the first definition of the Schur polynomials. For instance, with the tableau RSK example result.svg, one gets the corresponding 4-tuple

Schur lattice paths.svg

On the other hand, the matrix M is exactly the matrix written above for D. This shows the required equivalence. (See also §4.5 in Sagan's book, or the First Proof of Theorem 7.16.1 in Stanley's EC2, or §3.3 in Fulmek's arXiv preprint, or §9.13 in Martin's lecture notes, for slight variations on this argument.)

The Cauchy–Binet formula[edit]

One can also use the Lindström–Gessel–Viennot lemma to prove the Cauchy–Binet formula, and in particular the multiplicativity of the determinant.

Generalizations[edit]

Talaska's formula[edit]

The acyclicity of G is an essential assumption in the Lindström-Gessel-Viennot lemma; it guarantees (in reasonable situations) that the sums e(a, b) are well-defined, and it advects into the proof (if G is not acyclic, then f might transform a self-intersection of a path into an intersection of two distinct paths, which breaks the argument that f is an involution). Nevertheless, Kelli Talaska's 2012 paper establishes a formula generalizing the lemma to arbitrary digraphs. The sums e(a, b) are replaced by formal power series, and the sum over nonintersecting path tuples now becomes a sum over collections of nonintersecting and non-self-intersecting paths and cycles, divided by a sum over collections of nonintersecting cycles. The reader is referred to Talaska's paper for details.

See also[edit]

Matrix tree theorem

Cauchy–Binet formula

References[edit]

  • Talaska, Kelli (2012), Determinants of weighted path matrices, arXiv:1202.3128v1 
  • Fulmek, Markus (2010), Viewing determinants as nonintersecting lattice paths yields classical determinantal identities bijectively, arXiv:1010.3860v1