Lindström--Gessel--Viennot lemma

2026-07-09 Improve this page

#The Lindström–Gessel–Viennot lemma

The following result was first proved by B. Lindström [Lin73] and later rediscovered by I. Gessel and X. Viennot [GV89]. It gives a combinatorial interpretation of certain determinants as weighted sums over sets of nonintersecting lattice paths. For early applications to binomial determinants, hook length formulae, and plane partitions, see [GV85, GV89]. For a survey of lattice path enumeration with determinant methods, see [Kra15]. Bera gives a graph-theoretic proof of Cramer’s rule using the Gessel–Viennot–Lindström lemma [Ber25].

Let $R$ be a commutative ring, let $G=(V,E)$ be a finite directed acyclic graph, and let $w : E \to R$ be a weight function.

Given two vertices $u, v \in V,$ a path in $G$ from $u$ to $v$ is a sequence of vertices $\omega = (u = v_0, v_1, \dotsc, v_k = v)$ such that $(v_i, v_{i+1}) \in E$ for all $0 \le i \lt{} k.$ We denote this by $\omega : u \to v.$ The weight of the path $\omega$ is defined to be: \[w(\omega) = \prod_{i=0}^{k-1} w(v_i, v_{i+1}).\]

Definition (Crossing paths and crossing condition).

Two paths $\omega = (u_0, \dotsc, u_k)$ and $\eta = (v_0, \dotsc, v_l)$ are said to cross if they share a vertex, that is, if $u_i = v_j$ for some indices $i, j.$ A family of paths is nonintersecting if no two paths in the family cross.

Given a graph $G=(V,E),$ a weight function $w,$ and vertices $A_1, \dotsc, A_n$ and $B_1, \dotsc, B_n,$ we say that the crossing condition is satisfied if, for any indices $1 \le i \lt j \le n$ and $1 \le i' \lt j' \le n,$ any path $\omega : A_i \to B_{j'}$ and any path $\eta : A_j \to B_{i'}$ must cross.

Fix vertices $A_1, \dotsc, A_n$ and $B_1, \dotsc, B_n$ in $V,$ and define an $n \times n$ matrix $M = (m_{ij})$ by \[m_{ij} \coloneqq \sum_{\omega : A_i \to B_j} w(\omega),\] where the sum runs over all paths from $A_i$ to $B_j.$

Theorem (Lindström–Gessel–Viennot lemma).

Assume that the crossing condition holds. Then the determinant of the matrix $M$ is given by \[\det(M) = \sum_{(\omega_1, \dotsc, \omega_n)} w(\omega_1) \cdots w(\omega_n),\] where the sum runs over all $n$-tuples $(\omega_1, \dotsc, \omega_n)$ of pairwise nonintersecting paths such that $\omega_i : A_i \to B_i.$

#Semistandard tableaux

Semistandard Young tableaux can be put in correspondence with sets of nonintersecting lattice paths, and this allows us to prove the two Jacobi–Trudi identities, by using the Lindström–Gessel–Viennot lemma [Lin73, GV89].

Let $T \in \SSYT(\lambda/\mu)$ where the entries are bounded by $m.$

Row bijection: Each row $i$ of $T$ is mapped to a lattice path $P_i,$ with steps in the set $\{ (0,1), (1,0)\}.$ The starting vertex of $P_i$ is $(-i + \mu_i,1),$ the ending vertex is $(-i + \lambda_i, m),$ and its number of horizontal steps on $y$-coordinate $j$ is given by the number of entries in row $i$ equal to $j.$ The length of path $P_i$ is $m-1 + \lambda_i-\mu_i.$ This bijection can be used to prove the first Jacobi–Trudi identity.

Column bijection: Each column of $T$ is mapped to a path $P'_i,$ with steps in the set $\{ (-1,1), (1,1)\}.$ The starting vertex of $P'_i$ is given by $(2i - 2\mu'_i, 0),$ the ending vertex is $(2i - 2\lambda'_i + m, m)$ and the $j$th step of $P'_i$ is $(-1,1)$ if $j$ is present in column $i,$ otherwise it is $(1,1).$ Each path has length $m.$ This bijection can be used to prove the second Jacobi–Trudi identity.

Example (Bijection to lattice paths).

Consider the following skew semistandard Young tableau $T.$

$1$ $1$ $2$ $2$ $3$ $4$ $6$ $1$ $2$ $2$ $3$ $4$ $5$ $5$ $2$ $3$ $4$ $4$ $5$ $6$ $6$ $1$ $1$ $3$ $5$ $5$ $6$ $2$ $3$ $4$ $6$ $4$ $5$ $6$ $6$

The rows give rise to the following set of nonintersecting lattice paths, where the topmost row in $T$ corresponds to the rightmost path.

SSYT rows as lattice paths.

The columns in $T$ give rise to the following set of nonintersecting lattice paths, where the leftmost column corresponds to the leftmost path.

SSYT columns as lattice paths.

The following theorem is proved using lattice paths.

Theorem (See [McD23]).

Let $A$ and $B$ be subsets of $\{0,1,\dotsc,n\}$ of equal size, and let $A^c,$ $B^c$ be their complements. Then \[\det \left[ \completeH_{b-a}(x_1,x_2,\dotsc,x_{a+1}) \right]_{a \in A, b \in B} = \det \left[ \elementaryE_{a'-b'}(x_1,x_2,\dotsc,x_{a'}) \right]_{a' \in A^c, b' \in B^c}.\] Moreover, this is related to C. A. Aitken’s identity; \[\det \left[ \completeH_{b-a}(\xvec) \right]_{a \in A, b \in B} = \det \left[ \elementaryE_{a'-b'}(\xvec) \right]_{a' \in A^c, b' \in B^c}.\]

See also [Ste90] for background on counting lattice paths with Pfaffians. The Weyl alternant formula can also be proved by the Lindström–Gessel–Viennot lemma [Xio20]. For a video introduction to one extension of the theorem, see the GOCC talk [Com23].

#Plane partitions as lattice paths

See [Thm. 10.7.1, Kra15] and [Eq. (6), SP02] for the following application of the Lindström–Gessel–Viennot lemma.

Theorem

Let $\lambda$ and $\mu$ be partitions with at most $r$ parts such that $\lambda/\mu$ defines a skew shape, and let $c \geq \lambda_1.$ Then the number of lattice paths contained in $\lambda / \mu$ equals \[\det \left[ \binom{\lambda_i - \mu_j+1}{i-j+1} \right]_{1\leq i,j \leq r}.\]

For non-skew shapes, we can also interpret such partitions $\nu$ as lattice points in Stanley–Pitman polytopes [SP02]. This is also the number of plane partitions of skew shape $\lambda/\mu,$ with binary entries, or the number of nonnesting rook placements on the Ferrers board of shape $\lambda / \mu.$ There is also an interpretation of these quantities using certain linear extensions, see [AJ24].

With a weighted count, this determinant has a natural refinement.

#Lattice paths and matroid bases

Let $\lambda/\mu$ be as above, contained in an $r \times c$ rectangle. We use the conventional labeling where the path corresponding to a partition $\nu$ with $\mu \subseteq \nu \subseteq \lambda$ has North-step labels \[p_i = i+c-\nu_i,\qquad 1 \leq i \leq r.\] Equivalently, these labels satisfy \[i+c-\lambda_i \leq p_i \leq i+c-\mu_i,\qquad p_1 \lt p_2 \lt \dotsb \lt p_r.\] We then define \[F_{\lambda/\mu}(\xvec) \coloneqq \sum_{P} \prod_{i \in N(P)} x_i,\] where the sum is over all paths contained in $\lambda/\mu$ and $N(P)$ is the set of North-step labels of $P.$ Equivalently, $F_{\lambda/\mu}(\xvec)$ is the basis-generating polynomial of the corresponding lattice path matroid.

The weighted version of the determinant above is \[F_{\lambda/\mu}(\xvec) = \det\left[ \completeH_{i-j+1} \bigl(x_{i+c-\lambda_i},x_{i+c-\lambda_i+1},\dotsc,x_{j+c-\mu_j}\bigr) \right]_{1\leq i,j \leq r},\] where $\completeH_k$ denotes the complete homogeneous symmetric function, with $\completeH_0=1$ and $\completeH_k=0$ for $k \lt 0.$ The matrix entry has degree $i-j+1,$ and \[\completeH_{i-j+1}(1^{\lambda_i-\mu_j-i+j+1}) = \binom{\lambda_i-\mu_j+1}{i-j+1}.\] This is the one-column case of the flagged Jacobi–Trudi identity. Indeed, the column entries of a flagged semistandard tableau of shape $1^r$ record precisely the North-step labels of the path.

Remark (Caveat).

The appearance of $\completeH$ may look slightly unnatural at first, since $F_{\lambda/\mu}(\xvec)$ is square-free. The point is that the single-path generating functions in the LGV matrix are complete homogeneous functions; the determinant cancels the monomials with repeated North-step labels and leaves only the strictly increasing choices.

In particular, \[F_{\lambda/\mu}(1,1,\dotsc) = \det \left[ \binom{\lambda_i-\mu_j+1}{i-j+1} \right]_{1\leq i,j \leq r}.\] The principal specialization also has a closed form: \[F_{\lambda/\mu}(1,q,q^2,\dotsc) = \det\left[ q^{(i-j+1)(i+c-\lambda_i-1)} \qbinom{\lambda_i-\mu_j+1}{i-j+1}_q \right]_{1\leq i,j \leq r}.\] Here the entries with $i-j+1 \lt 0$ are again interpreted as zero. This specialization records the sum of the North-step labels, shifted by $-1$ on each North step.

There is also a shape-dependent specialization to the $W$-Eulerian polynomial of a width-two poset. Suppose that the spine-path bijection applies to $\lambda/\mu$; this includes straight shapes, and more generally connected $332/1$-avoiding skew shapes [AJ24]. Let $S_{\lambda/\mu}\subseteq [r+c]$ be the set of North-step labels which, under this bijection, correspond to rooks. Equivalently, if $L_\rho$ is the path corresponding to the non-nesting rook placement $\rho,$ then \[|N(L_\rho)\cap S_{\lambda/\mu}|=|\rho|.\] The set $S_{\lambda/\mu}$ depends only on the shape. Hence \[\left. F_{\lambda/\mu}(\xvec) \right|_{x_i=t\text{ for }i\in S_{\lambda/\mu},\, x_i=1\text{ otherwise}} = \sum_{\rho\in \mathrm{NN}(\lambda/\mu)} t^{|\rho|} = \sum_{\sigma\in \mathcal{L}(P_{\lambda/\mu})} t^{\des(\sigma)}.\] Here $P_{\lambda/\mu}$ is the naturally labeled width-two poset associated with the shape.

J. P. Hamre, B. Schröter, L. Vecchi, and E. Verkama study Chow classes of matroids in the Grassmannian [HSVV25]. For snake matroids, the Poincaré dual is identified with a ribbon Schur function, and the Schubert-basis coefficients count standard Young tableaux with prescribed descent set. The valuation extension gives formulas for arbitrary matroids and recovers volume formulas for lattice path matroids.

Bibliography

[AJ24]Per Alexandersson and Aryaman Jal. Rook matroids and log-concavity of ${P}$-Eulerian polynomials. arXiv:2410.00127, 2024.

.bib

@article{AlexanderssonJal2024x,
Author = {Per Alexandersson and Aryaman Jal},
Title = {Rook matroids and log-concavity of ${P}$-{E}ulerian polynomials},
Year = {2024},
Eprint = {2410.00127},
  url = {https://arxiv.org/abs/2410.00127},
journal = {arXiv e-prints}
}

[Ber25]Sudip Bera. A graph theoretic proof of Cramer’s rule. arXiv:2509.04789, 2025.

.bib

@article{Bera2025x,
  author = {Sudip Bera},
  title = {A graph theoretic proof of {C}ramer's rule},
  year = {2025},
  eprint = {2509.04789},
  url = {https://arxiv.org/abs/2509.04789},
  journal = {arXiv e-prints},
  journalref = {Communications in Combinatorics and Optimization, 2025},
  doi = {10.22049/cco.2025.30706.2586}
}

[Com23]GOCC Combinatorics. GOCC 10/4/2023 “an extension of the lindstrom–gessel–viennot theorem”. 2023. Video lecture

.bib

@misc{GOCC2023LGVExtension,
  author = {{GOCC Combinatorics}},
  title = {{GOCC} 10/4/2023 ``An Extension of the
           Lindstrom--Gessel--Viennot Theorem''},
  year = {2023},
  url = {https://www.youtube.com/watch?v=H1wEiEIznaA},
  note = {Video lecture}
}

[GV85]Ira Gessel and Gérard Viennot. Binomial determinants, paths, and hook length formulae. Advances in Mathematics, 58(3):300–321, December 1985.

.bib

@article{GesselViennot1985,
  doi = {10.1016/0001-8708(85)90121-5},
  url2 = {https://doi.org/10.1016/0001-8708(85)90121-5},
  year = {1985},
  month = dec,
  publisher = {Elsevier {BV}},
  volume = {58},
  number = {3},
  pages = {300--321},
  author = {Ira Gessel and G{\'{e}}rard Viennot},
  title = {Binomial determinants,  paths, and hook length formulae},
  journal = {Advances in Mathematics}
}

[GV89]I. M. Gessel and X. G. Viennot. Determinants, paths, and plane partitions. 1989. Preprint

.bib

@misc{GesselViennot1989,
	author = {I. M. Gessel and X. G. Viennot},
	title = {Determinants, Paths, and Plane Partitions},
	year = {1989},
	note ={Preprint},
	url = {https://people.brandeis.edu/~gessel/homepage/papers/pp.pdf}
}

[HSVV25]Jon Pål Hamre, Benjamin Schröter, Lorenzo Vecchi and Emil Verkama. Chow classes of matroids and standard Young tableaux. arXiv:2511.01711, 2025.

.bib

@article{HamreSchroterVecchiVerkama2025x,
  author = {Jon P{\aa}l Hamre and Benjamin Schr{\"o}ter and Lorenzo Vecchi
    and Emil Verkama},
  title = {Chow classes of matroids and standard {Y}oung tableaux},
  year = {2025},
  eprint = {2511.01711},
  url = {https://arxiv.org/abs/2511.01711},
  journal = {arXiv e-prints}
}

[Kra15]Christian Krattenthaler. Lattice path enumeration. Handbook of enumerative combinatorics:589–670, March 2015.

.bib

@incollection{Krattenthaler2015,
  doi = {10.1201/b18255-14},
  url2 = {https://doi.org/10.1201/b18255-14},
  year = {2015},
  month = mar,
  publisher = {Chapman and Hall/{CRC}},
  pages = {589--670},
  author = {Christian Krattenthaler},
  title = {Lattice Path Enumeration },
  booktitle = {Handbook of Enumerative Combinatorics}
}

[Lin73]Bernt Lindström. On the vector representations of induced matroids. Bulletin of the London Mathematical Society, 5(1):85–90, March 1973.

.bib

@article{Lindstrom1973,
  title = {On the Vector Representations of Induced Matroids},
  volume = {5},
  ISSN = {0024-6093},
  url = {http://dx.doi.org/10.1112/blms/5.1.85},
  DOI = {10.1112/blms/5.1.85},
  number = {1},
  journal = {Bulletin of the London Mathematical Society},
  publisher = {Wiley},
  author = {Lindstr\"{o}m,  Bernt},
  year = {1973},
  month = mar,
  pages = {85–90}
}

[McD23]Eoghan McDowell. Flagged Schur polynomial duality via a lattice path bijection. The Electronic Journal of Combinatorics, 30(1), January 2023.

.bib

@article{McDowell2023,
  title = {Flagged {S}chur Polynomial Duality via a Lattice Path Bijection},
  volume = {30},
  ISSN = {1077-8926},
  url = {http://dx.doi.org/10.37236/11200},
  DOI = {10.37236/11200},
  number = {1},
  journal = {The Electronic Journal of Combinatorics},
  publisher = {The Electronic Journal of Combinatorics},
  author = {McDowell,  Eoghan},
  year = {2023},
  month = jan 
}

[SP02]Richard P. Stanley and Jim Pitman. A polytope related to empirical distributions, plane trees, parking functions, and the associahedron. Discrete Computational Geometry, 27(4):603–602, January 2002.

.bib

@article{StanleyPitman2002,
  doi = {10.1007/s00454-002-2776-6},
  url2 = {https://doi.org/10.1007/s00454-002-2776-6},
  year = {2002},
  month = jan,
  publisher = {Springer Science and Business Media {LLC}},
  volume = {27},
  number = {4},
  pages = {603--602},
  author = {Richard P. Stanley and Jim Pitman},
  title = {A Polytope Related to Empirical Distributions,  Plane Trees,  Parking Functions,  and the Associahedron},
  journal = {Discrete Computational Geometry}
}

[Ste90]John R. Stembridge. Nonintersecting paths, pfaffians, and plane partitions. Advances in Mathematics, 83(1):96–131, September 1990.

.bib

@article{Stembridge1990,
  doi = {10.1016/0001-8708(90)90070-4},
  url2 = {https://doi.org/10.1016/0001-8708(90)90070-4},
  year = {1990},
  month = sep,
  publisher = {Elsevier {BV}},
  volume = {83},
  number = {1},
  pages = {96--131},
  author = {John R. Stembridge},
  title = {Nonintersecting paths,  pfaffians,  and plane partitions},
  journal = {Advances in Mathematics}
}

[Xio20]Rui Xiong. Schur polynomials through Lindström Gessel Viennot lemma. arXiv:2003.09215, 2020.

.bib

@article{Xiong2020x,
  Author  = {Rui Xiong},
  Title   = {Schur Polynomials through {L}indström {G}essel {V}iennot Lemma},
  Year    = {2020},
  journal = {arXiv e-prints},
  Eprint  = {2003.09215},
  url = {https://arxiv.org/abs/2003.09215},
}