Lindström–Gessel–Viennot lemma

In Mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths, or, more generally, paths on a directed graph. It was proved by Gessel–Viennot in 1985, based on previous work of Lindström published in 1973.
Statement.
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 formula_1 and destination vertices formula_2, and also assign a weight formula_3 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 formula_4 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 formula_5 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 formula_6 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
An "n"-tuple of non-intersecting paths from "A" to "B" means an "n"-tuple ("P"1, ..., "P""n") of paths in "G" with the following properties:
Given such an "n"-tuple ("P"1, ..., "P""n"), we denote by formula_13 the permutation of formula_8 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" = ("P"1, ..., "P""n") 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 formula_16, given by formula_17 taking formula_18 to formula_19.
In particular, if the only permutation possible is the identity (i.e., every "n"-tuple of non-intersecting paths from "A" to "B" takes "a""i" to "b""i" 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.
To prove the Lindström–Gessel–Viennot lemma, we first introduce some notation.
An "n"-path from an "n"-tuple formula_20 of vertices of "G" to an "n"-tuple formula_21 of vertices of "G" will mean an "n"-tuple formula_22 of paths in "G", with each formula_23 leading from formula_10 to formula_25. This "n"-path will be called non-intersecting just in case the paths "P""i" and "P""j" have no two vertices in common (including endpoints) whenever formula_12. Otherwise, it will be called entangled.
Given an "n"-path formula_27, the weight formula_28 of this "n"-path is defined as the product formula_29.
A twisted "n"-path from an "n"-tuple formula_20 of vertices of "G" to an "n"-tuple formula_21 of vertices of "G" will mean an "n"-path from formula_20 to formula_33 for some permutation formula_8 in the symmetric group formula_35. This permutation formula_8 will be called the twist of this twisted "n"-path, and denoted by formula_13 (where "P" is the "n"-path). This, of course, generalises the notation formula_13 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 formula_40 over all entangled twisted "n"-paths vanishes. Let formula_41 denote the set of entangled twisted "n"-paths. To establish this, we shall construct an involutionformula_42 with the properties formula_43 and formula_44 for all formula_45. Given such an involution, the rest-term
in the above sum reduces to 0, since its addends cancel each other out (namely, the addend corresponding to each formula_47 cancels the addend corresponding to formula_48).
Construction of the involution: The idea behind the definition of the involution formula_49 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 formula_50 be any entangled twisted "n"-path. Then formula_48 is defined as follows. We call a vertex crowded if it belongs to at least two of the paths formula_52. The fact that the graph is acyclic implies that this is equivalent to "appearing at least twice in all the paths". Since "P" is entangled, there is at least one crowded vertex. We pick the smallest formula_53 such that formula_23 contains a crowded vertex. Then, we pick the first crowded vertex "v" on formula_23 ("first" in sense of "encountered first when travelling along formula_23"), and we pick the largest "j" such that "v" belongs to formula_57. The crowdedness of "v" implies "j" &gt; "i". Write the two paths formula_23 and formula_57 as
where formula_61, and where formula_62 and formula_63 are chosen such that "v" is the formula_62-th vertex along formula_23 and the formula_63-th vertex along formula_57 (that is, formula_68). We set formula_69 and formula_70 and formula_71 and formula_72. Now define the twisted "n"-path formula_48 to coincide with formula_74 except for components formula_75 and formula_76, which are replaced by
It is immediately clear that formula_48 is an entangled twisted "n"-path. Going through the steps of the construction, it is easy to see that formula_79, formula_80 and furthermore that formula_81 and formula_82, so that applying formula_49 again to formula_48 involves swapping back the tails of formula_85 and leaving the other components intact. Hence formula_86. Thus formula_49 is an involution. It remains to demonstrate the desired antisymmetry properties:
From the construction one can see that formula_88 coincides with formula_61 except that it swaps formula_90 and formula_91, thus yielding formula_44. To show that formula_43 we first compute, appealing to the tail-swap
Hence formula_95.
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 (unequal to "i") rather than largest appears in the Gessel-Viennot 1989 reference (proof of Theorem 1).
Applications.
Schur polynomials.
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 formula_96 of "n", the Schur polynomial formula_97 can be defined as:
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 "x""i" indexed by the entries "i" of "T". For instance, the weight of the tableau
is formula_99.
where "h""i" are the complete homogeneous symmetric polynomials (with "h""i" understood to be 0 if "i" is negative). For instance, for the partition (3,2,2,1), the corresponding determinant is
To prove the equivalence, given any partition "λ" as above, one considers the "r" starting points formula_102 and the "r" ending points formula_103, as points in the lattice formula_104, 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 "x""i", 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 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.
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 (in reasonable situations) that the sums formula_105 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 formula_105 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.