Lindström–Gessel–Viennot Lemma¶
A determinant identity equating path-matrix minors in a weighted directed acyclic graph with a signed sum of vertex-disjoint path families between chosen sources and destinations.
Core Idea¶
LGV builds a matrix whose entries are complete weighted path sums between ordered sources and destinations. Its determinant expands into signed tuples of paths, one tuple for each endpoint permutation.
Intersecting tuples cancel in weight-preserving, sign-reversing pairs obtained by exchanging path tails at an intersection. What survives is the signed enumeration of vertex-disjoint families; special endpoint orderings can make that determinant a direct positive count.
Scope of Application¶
- Lattice-path enumeration. Counts nonintersecting path ensembles.
- Determinantal identities. Proves formulas for minors and symmetric functions.
- Plane partitions and tableaux. Builds bijective enumerations through path encodings.
- Total positivity. Interprets matrix minors using positive path weights.
Clarity¶
State graph, acyclicity or convergence assumptions, coefficient ring, edge weights, source and sink order, path intersection convention, and endpoint permutations. Explain why any desired family has positive sign and why unwanted families cancel. Inclusion test: Require a suitable weighted directed graph, ordered source and destination sets, path-sum matrix, and vertex-disjoint family interpretation with determinant signs tracked. Exclusion test: Exclude arbitrary determinants, edge-disjoint variants asserted without modification, cyclic graphs with divergent path sums, and unsigned counts when nonidentity endpoint permutations contribute. Nearest boundary: The matrix-tree theorem also uses determinants to count graph structures, but it enumerates spanning trees through Laplacian minors rather than disjoint source–destination paths. Exit condition: The result leaves the standard lemma when weights do not commute, path sums are ill-defined, or the nonintersection condition differs without a revised proof. Common misclassifications: The relevant matrix is not merely the adjacency matrix. Nonintersecting ordinarily means vertex-disjoint, including endpoints as specified. A determinant may be signed rather than an unsigned count. Directed cycles require care because path sums may not be finite. Nearest named distinctions: Matrix-tree theorem: Counts spanning trees from Laplacian determinants. Menger's theorem: Relates disjoint paths to separators rather than weighted enumeration. Adjacency-matrix powers: Count fixed-length walks, including intersections. Karlin–McGregor formula: Is a related determinant for noncolliding stochastic paths under additional structure.
Manages Complexity¶
The lemma compresses exponentially many path tuples into one determinant by exploiting an involution rather than enumerating them directly. Its elegance depends on precise synchronization of graph topology, algebraic weights, endpoint ordering, and the chosen nonintersection notion.
Abstract Reasoning¶
- Choose a directed graph, source order, destination order, and commutative weights.
- Verify finiteness of relevant path sums, commonly through acyclicity.
- Form the matrix of total path weights.
- Identify vertex-disjoint families and their endpoint permutations.
- Apply the sign-reversing involution and justify any conversion from signed to unsigned count.
Knowledge Transfer¶
The determinant–path method transfers when objects can be encoded as vertex-disjoint paths with well-defined multiplicative weights. Edge-disjointness, cycles, noncommutative weights, or unmatched endpoint order require a modified theorem rather than casual reuse.
Relationships to Other Abstractions¶
Current abstraction Lindström–Gessel–Viennot Lemma Domain-specific
Parents (1) — more general patterns this builds on
-
Lindström–Gessel–Viennot Lemma presupposes Directed Acyclic Graph Prime
Lindström–Gessel–Viennot Lemma presupposes Directed Acyclic Graph because its weighted path matrix and vertex-disjoint families are defined on a directed acyclic graph.
Hierarchy path (1) — routes to 1 parentless root
- Lindström–Gessel–Viennot Lemma → Directed Acyclic Graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance
Neighborhood in Abstraction Space¶
Lindström–Gessel–Viennot Lemma sits in a moderately populated region (54th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Structures & Algorithms (24 abstractions)
Nearest neighbors
- Geodetic Graph — 0.87
- Prism graph — 0.86
- Graph Power — 0.86
- Prim’s Algorithm — 0.85
- Utility graph — 0.85
Computed from structural-signature embeddings · 2026-10-08