Lindström–Gessel–Viennot lemma

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\; =\; \backslash \{\; a\_1,\; \backslash ldots,\; a\_n\; \backslash \}$ and destination vertices $B\; =\; \backslash \{\; b\_1,\; \backslash ldots,\; b\_n\; \backslash \}$, and also assign a weight $\backslash 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 $\backslash 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)\; =\; \backslash sum\_\{P:\; a\; \backslash to\; b\}\; \backslash 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) is 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₁, ..., P_n) of paths in G with the following properties:

• There exists a permutation $\backslash sigma$ of $\backslash left\backslash \{\; 1,\; 2,\; ...,\; n\; \backslash right\backslash \}$ such that, for every i, the path P_i is a path from $a\_i$ to $b\_\{\backslash sigma(i)\}$.
• Whenever $i\; \backslash neq\; j$, the paths P_i and P_j have no two vertices in common (not even endpoints).

Given such an n-tuple (P₁, ..., P_n), we denote by $\backslash sigma(P)$ the permutation of $\backslash 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 = (P₁, ..., P_n) of non-intersecting paths from A to B:

:$\backslash det(M)\; =\; \backslash sum\_\{(P\_1,\backslash ldots,P\_n)\; \backslash colon\; A\; \backslash to\; B\}\; \backslash mathrm\{sign\}(\backslash sigma(P))\; \backslash prod\_\{i=1\}^n\; \backslash 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,\backslash ldots,n)$, given by $P\_i$ taking $a\_i$ to $b\_\{\backslash 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 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.

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

An n-path from an n-tuple $(a\_1,\; a\_2,\; \backslash ldots,\; a\_n)$ of vertices of G to an n-tuple $(b\_1,\; b\_2,\; \backslash ldots,\; b\_n)$ of vertices of G will mean an n-tuple $(P\_1,\; P\_2,\; \backslash ldots,\; P\_n)$ of paths in G, with each $P\_i$ leading from $a\_i$ to $b\_i$. 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 $i\; \backslash neq\; j$. Otherwise, it will be called entangled.

Given an n-path $P\; =\; (P\_1,\; P\_2,\; \backslash ldots,\; P\_n)$, the weight $\backslash omega(P)$ of this n-path is defined as the product $\backslash omega(P\_1)\; \backslash omega(P\_2)\; \backslash cdots\; \backslash omega(P\_n)$.

A twisted n-path from an n-tuple $(a\_1,\; a\_2,\; \backslash ldots,\; a\_n)$ of vertices of G to an n-tuple $(b\_1,\; b\_2,\; \backslash ldots,\; b\_n)$ of vertices of G will mean an n-path from $(a\_1,\; a\_2,\; \backslash ldots,\; a\_n)$ to $\backslash left(b\_\{\backslash sigma(1)\},\; b\_\{\backslash sigma(2)\},\; \backslash ldots,\; b\_\{\backslash sigma(n)\}\backslash right)$ for some permutation $\backslash sigma$ in the symmetric group $S\_n$. This permutation $\backslash sigma$ will be called the twist of this twisted n-path, and denoted by $\backslash sigma(P)$ (where P is the n-path). This, of course, generalises the notation $\backslash sigma(P)$ introduced before.

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

:$$

\begin{array}{rcl}

\det M &= &\sum_{\sigma\in S_{n}}\mathrm{sign}(\sigma)\prod_{i=1}^{n}e(a_{i},b_{\sigma(i)})\\

&= &\sum_{\sigma\in S_{n}}\mathrm{sign}(\sigma)\prod_{i=1}^{n}\sum_{P_{i}:a_{i}\to b_{\sigma(i)}}\omega(P_{i})\\

&= &\sum_{\sigma\in S_{n}}\mathrm{sign}(\sigma)

\sum\{\omega(P):P~\text{an}~n\text{-path from}~\left(a_1,a_2,\ldots,a_n\right)~\text{to}~\left(b_{\sigma(1)}, b_{\sigma(2)}, \ldots, b_{\sigma(n)}\right)\}\\

&= &\sum\{\mathrm{sign}(\sigma(P))\omega(P):P~\text{a twisted}~n\text{-path from}~\left(a_1,a_2,\ldots,a_n\right)~\text{to}~\left(b_1, b_2, ..., b_n\right)\}\\

&= &\sum\{\mathrm{sign}(\sigma(P))\omega(P):P~\text{a non-intersecting twisted}~n\text{-path from}~\left(a_1,a_2,\ldots,a_n\right)~\text{to}~\left(b_1, b_2, ..., b_n\right)\}\\

&&+\sum\{\mathrm{sign}(\sigma(P))\omega(P):P~\text{an entangled twisted}~n\text{-path from}~\left(a_1,a_2,\ldots,a_n\right)~\text{to}~\left(b_1, b_2, ..., b_n\right)\}\\

&= &\sum_{(P_1,\ldots,P_n) \colon A \to B} \mathrm{sign}(\sigma(P))\omega(P)\\

&&+\underbrace{

\sum\{\mathrm{sign}(\sigma(P))\omega(P):P~\text{an entangled twisted}~n\text{-path from}~\left(a_1,a_2,\ldots,a_n\right)~\text{to}~\left(b_1, b_2, ..., b_n\right)\}}_{=0?}\\

\end{array}

It remains to show that the sum of $\backslash mathrm\{sign\}(\backslash sigma(P))\backslash omega(P)$ over all entangled twisted n-paths vanishes. Let $\backslash mathcal\{E\}$ denote the set of entangled twisted n-paths. To establish this, we shall construct an involution$f:\backslash mathcal\{E\}\backslash longrightarrow\backslash mathcal\{E\}$ with the properties $\backslash omega(f(P))=\backslash omega(P)$ and $\backslash mathrm\{sign\}(\backslash sigma(f(P)))=-\backslash mathrm\{sign\}(\backslash sigma(P))$ for all $P\backslash in\backslash mathcal\{E\}$. Given such an involution, the rest-term

:$$

\sum\{\mathrm{sign}(\sigma(P))\omega(P):P~\text{an entangled twisted}~n\text{-path from}~\left(a_1,a_2,\ldots,a_n\right)~\text{to}~\left(b_1, b_2, ..., b_n\right)\}

=

\sum_{P \in \mathcal{E}} \mathrm{sign}(\sigma(P))\omega(P)

in the above sum reduces to 0, since its addends cancel each other out (namely, the addend corresponding to each $P\; \backslash in\; \backslash mathcal\{E\}$ cancels the addend corresponding to $f(P)$).

Construction of the involution: The idea behind the definition of the involution $f$ 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 $P\; =\; \backslash left(P\_1,P\_2,...,P\_n\backslash right)$ be any entangled twisted n-path. Then $f(P)$ is defined as follows. We call a vertex crowded if it belongs to at least two of the paths $P\_1,P\_2,...,P\_n$. The fact that the graph is acyclic implies that this is equivalent to "appearing at least twice in all the paths".If the graph was not acyclic, the "crowdedness" might change after applying $f$ ; this proof would not work, and the lemma would actually become totally false. Since P is entangled, there is at least one crowded vertex. We pick the smallest $i\; \backslash in\; \backslash \{1,2,\backslash ldots,n\backslash \}$ such that $P\_i$ contains a crowded vertex. Then, we pick the first crowded vertex v on $P\_i$ ("first" in sense of "encountered first when travelling along $P\_i$"), and we pick the largest j such that v belongs to $P\_j$. The crowdedness of v implies j > i. Write the two paths $P\_i$ and $P\_j$ as

:$$

\begin{array}{rcl}

P_{i} &\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha-1}\to\overbrace{

\mathbf{u}_{\alpha}\to u_{\alpha+1} \ldots\to u_{r}=b_{\sigma(i)}

}^{\mathrm{tail}~i}\\

P_{j} &\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta-1}\to\underbrace{

\mathbf{v}_{\beta}\to v_{\beta+1} \ldots\to v_{s}=b_{\sigma(j)}

}_{\mathrm{tail}~j}\\

\end{array}

where $\backslash sigma=\backslash sigma(P)$, and where $\backslash alpha$ and $\backslash beta$ are chosen such that v is the $\backslash alpha$-th vertex along $P\_i$ and the $\backslash beta$-th vertex along $P\_j$ (that is, $v\; =\; u\_\{\backslash alpha\}\; =\; v\_\{\backslash beta\}$). We set $\backslash alpha\_P\; =\; \backslash alpha$ and $\backslash beta\_P\; =\; \backslash beta$ and $i\_\{P\}\; =\; i$ and $j\_\{P\}\; =\; j$. Now define the twisted n-path $f(P)$ to coincide with $P$ except for components $i$ and $j$, which are replaced by

:$$

\begin{array}{rcl}

P'_{i} &\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha-1}\to\overbrace{

v_{\beta_{P}}\to v_{\beta_{P}+1}\ldots\to v_{s}=b_{\sigma(j)}

}^{\mathrm{tail}~j}\\

P'_{j} &\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta-1}\to\underbrace{

u_{\alpha_{P}}\to u_{\alpha_{P}+1}\ldots\to u_{r}=b_{\sigma(i)}

}_{\mathrm{tail}~i}\\

\end{array}

It is immediately clear that $f(P)$ is an entangled twisted n-path. Going through the steps of the construction, it is easy to see that $i\_\{f(P)\}=i\_\{P\}$, $j\_\{f(P)\}=j\_\{P\}$ and furthermore that $\backslash alpha\_\{f(P)\}=\backslash alpha\_\{P\}$ and $\backslash beta\_\{f(P)\}=\backslash beta\_\{P\}$, so that applying $f$ again to $f(P)$ involves swapping back the tails of $f(P)\_\{i\},f(P)\_\{j\}$ and leaving the other components intact. Hence $f(f(P))=P$. Thus $f$ is an involution. It remains to demonstrate the desired antisymmetry properties:

From the construction one can see that $\backslash sigma(f(P))$ coincides with $\backslash sigma=\backslash sigma(P)$ except that it swaps $\backslash sigma(i)$ and $\backslash sigma(j)$, thus yielding $\backslash mathrm\{sign\}(\backslash sigma(f(P)))=-\backslash mathrm\{sign\}(\backslash sigma(P))$. To show that $\backslash omega(f(P))=\backslash omega(P)$ we first compute, appealing to the tail-swap

:$$

\begin{array}{rcl}

\omega(P'_{i})\omega(P'_{j})

&= &\left(\prod_{t=0}^{\alpha-1}\omega(u_{t},u_{t+1})\cdot \prod_{t=\beta}^{s-1}\omega(v_{t},v_{t+1})\right)

\cdot\left(\prod_{t=0}^{\beta-1}\omega(v_{t},v_{t+1})\cdot \prod_{t=\alpha}^{r-1}\omega(u_{t},u_{t+1})\right)\\

&= &\prod_{t=0}^{r-1}\omega(u_{t},u_{t+1})\cdot\prod_{t=0}^{s-1}\omega(v_{t},v_{t+1})\\

&= &\omega(P_{i})\omega(P_{j}).\\

\end{array}

Hence $\backslash omega(f(P))=\backslash prod\_\{k=1\}^\{n\}\backslash omega(f(P)\_\{k\})=\backslash prod\_\{k=1,~k\backslash neq\; i,j\}^\{n\}\backslash omega(P\_\{k\})\backslash cdot\; \backslash omega(P\text{'}\_\{i\})\backslash omega(P\text{'}\_\{j\})=\backslash prod\_\{k=1,~k\backslash neq\; i,j\}^\{n\}\backslash omega(P\_\{k\})\backslash cdot\; \backslash omega(P\_\{i\})\backslash omega(P\_\{j\})=\backslash prod\_\{k=1\}^\{n\}\backslash omega(P\_\{k\})=\backslash omega(P)$.

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

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 $\backslash lambda\; =\; \backslash lambda\_1\; +\; \backslash cdots\; +\; \backslash lambda\_r$ of n, the Schur polynomial $s\_\backslash lambda(x\_1,\backslash ldots,x\_n)$ can be defined as:

• $s\_\backslash lambda(x\_1,\backslash ldots,x\_n)\; =\; \backslash 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 x_i indexed by the entries i of T. For instance, the weight of the tableau

Image:RSK example result.svg

is $x\_1\; x\_3\; x\_4^3\; x\_5\; x\_6\; x\_7$.

• $s\_\backslash lambda(x\_1,\; \backslash ldots,\; x\_n)\; =\; \backslash det\; \backslash left\; (\; (h\_\{\backslash lambda\_i\; +j-i\}\; )\_\{i,j\}^\{r\; \backslash times\; r\}\; \backslash right\; ),$

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 $a\_i\; =\; (r+1-i,1)$ and the r ending points $b\_i\; =\; (\backslash lambda\_i\; +\; r+1-i,\; n)$, as points in the lattice $\backslash 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 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

Image:RSK example result.svg,

one gets the corresponding 4-tuple

Image: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.)

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

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.

• Matrix tree theorem

{{reflist}}

• {{Citation | last1=Gessel | first1=Ira M. | author1-link=Ira Gessel | last2=Viennot | first2=Xavier G. | author2-link=Xavier G. Viennot | title=Determinants, Paths and Plane Partitions | year=1989 | url=http://contscience.xavierviennot.org/xavier/articles_files/determinant_89.pdf |archive-url=https://web.archive.org/web/20170417154800/https://contscience.xavierviennot.org/xavier/articles_files/determinant_89.pdf |archive-date=2017-04-17 }}
• {{Citation | last1=Lindström | first1=Bernt | title=On the vector representations of induced matroids | year=1973 | doi=10.1112/blms/5.1.85 }}
• {{Citation | last1=Sagan | first1=Bruce E. | author1-link=Bruce Sagan | title=The symmetric group | year=2001 | publisher=Springer }}
• {{Citation | last1=Stanley | first1=Richard P. | author1-link=Richard P. Stanley | title=Enumerative Combinatorics, volume 2 | year=1999 | publisher=CUP }}
• {{Citation | last1=Talaska | first1=Kelli | title=Determinants of weighted path matrices | year=2012 | arxiv=1202.3128v1 }}
• {{Citation | last1=Martin | first1=Jeremy | title=Lecture Notes on Algebraic Combinatorics | year=2012 | url=http://jlmartin.faculty.ku.edu/CombinatoricsNotes.pdf }}
• {{Citation | last1=Fulmek | first1=Markus | title= Viewing determinants as nonintersecting lattice paths yields classical determinantal identities bijectively | year=2010 | arxiv=1010.3860v1 }}

{{DEFAULTSORT:Lindstrom-Gessel-Viennot lemma}}

Category:Lemmas

Category:Combinatorics

Category:Theorems in combinatorics