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.

Version: v1 · 2026-09-28 · History
Domain-specific #: 10408
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Enumerative Combinatorics, Algebraic Combinatorics → Mathematics
Aliases: LGV lemma, Lindström lemma, Gessel–Viennot lemma

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.

Structural Signature¶

Sig role-phrases:

Directed acyclic graph — Provides finite path sums and an order for cancellation. It is combinatorial domain. Counterfactual: Cycles can make unrestricted path sums nonfinite or require formal extensions.
Source tuple — Indexes matrix rows and path starts. It is boundary data. Counterfactual: Unordered sources obscure permutation signs.
Destination tuple — Indexes matrix columns and path ends. It is boundary data. Counterfactual: Mismatched endpoints change the determinant.
Edge weights — Multiply along paths and add across alternatives. It is algebraic weight. Counterfactual: Noncommutative weights invalidate the ordinary determinant argument.
Path matrix — Collects all source-to-destination path sums. It is algebraic bridge. Counterfactual: A generic adjacency matrix is not the required matrix.
Sign-reversing involution — Cancels intersecting path families. It is proof mechanism. Counterfactual: Without cancellation the determinant includes unwanted intersections.

What It Is Not¶

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.
Closest near-miss. 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.

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.

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.

Examples¶

Canonical¶

In a finite directed acyclic lattice, matrix entries count weighted paths from each start to each end; the determinant cancels intersecting pairs and leaves signed nonintersecting path systems.

Mapped back: graph → weighted DAG; matrix → path sums; families → vertex-disjoint; result → signed determinant.

Applied / In Practice¶

Taking the determinant of the graph's adjacency matrix does not count the required path families because its entries encode one-step edges rather than all source-to-destination paths.

Mapped back: matrix → adjacency; path sums → absent; verdict → wrong matrix.

Structural Tensions¶

T1 — Signed Identity versus Positive Enumeration. Determinants naturally attach permutation signs, while counting applications often want nonnegative totals.

Diagnostic: What ordering eliminates or controls nonidentity pairings?

T2 — General Weights versus Finite Path Sums. Algebraic flexibility depends on acyclicity or another convergence/formal-series framework.

Diagnostic: Why is every matrix entry well-defined?

Structural–Framed Character¶

Lindström–Gessel–Viennot Lemma is structural as determinant expansion plus cancellation of intersecting path families and framed by algebraic combinatorics. The path matrix is the bridge between graph enumeration and linear algebra.

Structural Core vs. Domain Accent¶

The general core is signed cancellation through an involution. Combinatorics supplies paths, sources, sinks, vertex intersections, and multiplicative weights; determinant theory supplies permutations and signs.

This entry presupposes Directed Acyclic Graph.

Approved unparented root. No reviewed parent entails this determinant identity for disjoint paths.
Related — matrix-tree and disjoint-path theorems. They also connect graphs to algebra but count different objects or answer existence rather than weighted enumeration.

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 (54^th 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

Not to Be Confused With¶

Matrix-tree theorem. Tell: Counts spanning trees from Laplacian determinants.
Menger's theorem. Tell: Relates disjoint paths to separators rather than weighted enumeration.
Adjacency-matrix powers. Tell: Count fixed-length walks, including intersections.
Karlin–McGregor formula. Tell: Is a related determinant for noncolliding stochastic paths under additional structure.

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma (revision 1362849243).
Preserved source candidate: http://contscience.xavierviennot.org/xavier/articles_files/determinant_89.pdf
Preserved source candidate: https://web.archive.org/web/20170417154800/https://contscience.xavierviennot.org/xavier/articles_files/determinant_89.pdf
Preserved source candidate: http://jlmartin.faculty.ku.edu/CombinatoricsNotes.pdf

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.