THE FOLD / GRIND / BACKPROP / THE LINDSTRÖM–GESSEL–VIENNOT
THE LINDSTRÖM–GESSEL–VIENNOT
non-crossing paths counted by a determinant
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Lindström–Gessel–Viennot lemma counts families of non-crossing paths with a single determinant. Place sources A1…Am and sinks B1…Bm on a grid; let Mij be the number of lattice paths from Ai to Bj. Then det(M) equals the signed count of families of paths, one Ai→Bσ(i), that are vertex-disjoint. In the common planar arrangement where only the identity matching can avoid crossings, the determinant counts exactly the non-intersecting families — a bridge between linear algebra and path combinatorics.
LIT verified live: for planar source/sink placements, det(M) (built from binomial path counts) equals a brute-force enumeration of vertex-disjoint path families, for both 2-source and 3-source configurations (window.__lgv). FIG no framing; a determinant vs an explicit non-crossing count.
LIT verified live: for planar source/sink placements, det(M) (built from binomial path counts) equals a brute-force enumeration of vertex-disjoint path families, for both 2-source and 3-source configurations (window.__lgv). FIG no framing; a determinant vs an explicit non-crossing count.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at backprop — the same shape as a computation graph: value flows along paths, and the total is a signed sum over path families; here the crossing paths cancel and only the disjoint families survive, read off as a determinant. That path-sum is the backprop kinship. AVAN (AI) built the instrument: the binomial path-count matrix, its determinant, and the brute-force count of vertex-disjoint families.
Credit as content: Bernt Lindström (1973); Ira Gessel & Gérard Viennot (1985). The weave: David names backprop; I fill the matrix of path counts between sources and sinks, take its determinant, and confirm it equals the number of non-crossing path families — the crossings cancelling in the determinant’s signed sum.
Credit as content: Bernt Lindström (1973); Ira Gessel & Gérard Viennot (1985). The weave: David names backprop; I fill the matrix of path counts between sources and sinks, take its determinant, and confirm it equals the number of non-crossing path families — the crossings cancelling in the determinant’s signed sum.
3 ONE DIMENSION
Two sources, two sinks. M = [[#A₁→B₁, #A₁→B₂],[#A₂→B₁, #A₂→B₂]]. det(M) = (paths that don’t cross) — the crossing pairs cancel in the signed sum.
4 TWO DIMENSIONS · INTERACTIVE
The grid, sources and sinks, the path-count matrix and its determinant; the non-crossing count checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: non-crossing paths from a determinant.
AVAN’s addition (the inverse-companion): count non-crossing path families not by enumerating them, but by a determinant of path counts — the crossing families cancel in pairs, leaving exactly the disjoint ones. The inverse of ‘list every vertex-disjoint family’ is ‘take one determinant and the crossings cancel themselves.’ Magenta is the brute enumeration; green is the determinant. Crossings cancelled by a sign.
LIT Genuine Lindström–Gessel–Viennot lemma (Bernt Lindström, 1973; Ira Gessel & Gérard Viennot, 1985). Verified live: for planar source/sink placements the determinant of the binomial path-count matrix equals a brute-force count of vertex-disjoint path families, for both a 2-source and a 3-source configuration (window.__lgv.matches, with det2/count2 and det3/count3 shown).
FIG No framing: the binomial path-count matrix, its determinant, and the brute-force enumeration of vertex-disjoint families all run in-browser and agree. The AVAN inverse is honest — counting non-crossing path families by a determinant (rather than enumerating them) works because crossing families cancel in pairs in the signed sum, leaving exactly the disjoint ones; magenta is the brute enumeration, green the determinant. Crossings cancelled by a sign.
FIG No framing: the binomial path-count matrix, its determinant, and the brute-force enumeration of vertex-disjoint families all run in-browser and agree. The AVAN inverse is honest — counting non-crossing path families by a determinant (rather than enumerating them) works because crossing families cancel in pairs in the signed sum, leaving exactly the disjoint ones; magenta is the brute enumeration, green the determinant. Crossings cancelled by a sign.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of BACKPROP · David Lee Wise (ROOT0), with AVAN