In mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths. It was proved by Gessel–Viennot in 1985, based on previous work of Lindström published in 1973.
Statement
Let G be a locally finitedirected acyclic graph. This means that each vertex has finite degree, and that G contains no directed cycles. Consider base vertices and destination vertices, and also assign a weight to each directed edgee. These edge weights are assumed to belong to some commutative ring. For each directed pathP between two vertices, let be the product of the weights of the edges of the path. For any two vertices a and b, write e for the sum 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. If one assigns the weight 1 to each edge, then e counts the number of paths from a to b. With this setup, write An n-tuple of non-intersecting paths from A to B means an n-tuple of paths in G with the following properties:
There exists a permutation of such that, for every i, the path Pi is a path from to.
Whenever, the paths Pi and Pj have no two vertices in common.
Given such an n-tuple, we denote by the permutation of 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 = of non-intersecting paths from A to B: 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, given by taking to. In particular, if the only permutation possible is the identity and we take the weights to be 1, then det is exactly the number of non-intersecting n-tuples of paths starting at A and ending at B.
Proof
To prove the Lindström–Gessel–Viennot lemma, we first introduce some notation. An n-path from an n-tuple of vertices of G to an n-tuple of vertices of G will mean an n-tuple of paths in G, with each leading from to. This n-path will be called non-intersecting just in case the paths Pi and Pj have no two vertices in common whenever. Otherwise, it will be called entangled. Given an n-path, the weight of this n-path is defined as the product. A twistedn-path from an n-tuple of vertices of G to an n-tuple of vertices of G will mean an n-path from to for some permutation in the symmetric group. This permutation will be called the twist of this twisted n-path, and denoted by . This, of course, generalises the notation introduced before. Recalling the definition of M, we can expand det M as a signed sum of permutations; thus we obtain It remains to show that the sum of over all entangled twisted n-paths vanishes. Let denote the set of entangled twisted n-paths. To establish this, we shall construct an involution with the properties and for all. Given such an involution, the rest-term in the above sum reduces to Construction of the involution: The idea behind the definition of the involution is to take choose two intersecting paths within an entangled path, and switch their tails after their point of intersection. There are in general several pairs of intersecting paths, which can also intersect several times; hence, a careful choice needs to be made. Let be any entangled twisted n-path. Then is defined as follows. Since is entangled, there exists a minimal in such that and share a common vertex. Choose to be the smallest such indices. The common vertex is necessarily not an endpoint of these paths. Summarising this information we have where,, and the -th vertex along coincides with the th vertex along. Choose to be the smallest possible such positions, concretely and. Now set to coincide with except for components and, which are replaced by It is immediately clear that is an entangled twisted n-path. Going through the steps of the construction, it is easy to see that, and furthermore that and, so that applying again to involves swapping back the tails of and leaving the other components intact. Hence. Thus is an involution. It remains to demonstrate the desired antisymmetry properties: From the construction one can see that coincides with except that it swaps and, thus yielding. To show that we first compute, appealing to the tail-swap Hence. Thus we have found an involution with the desired properties and completed the proof of the Lindström-Gessel-Viennot lemma. Remark. 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 rather than largest appears in the Gessel-Viennot 1989 reference.
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 of n, the Schur polynomial can be defined as: where the sum is over all semistandard Young tableauxT 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 is. where hi are the complete homogeneous symmetric polynomials. For instance, for the partition, the corresponding determinant is To prove the equivalence, given any partition λ as above, one considers the r starting points and the r ending points, as points in the lattice, 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 , one gets the corresponding 4-tuple On the other hand, the matrixM is exactly the matrix written above for D. This shows the required equivalence.
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
Talaska's formula
The acyclicity of G is an essential assumption in the Lindström–Gessel–Viennot lemma; it guarantees that the sums are well-defined, and it advects into the proof. Nevertheless, Kelli Talaska's 2012 paper establishes a formula generalizing the lemma to arbitrary digraphs. The sums 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.
