= Lindström-Gessel-Viennot lemma
{c}
{title2=$\det(M_{ij})$}
= Lindström-Gessel-Viennot theorem
{c}
{synonym}
Let a finite <directed acyclic graph> have weighted edges, sources $a_1,\ldots,a_r$ and sinks $b_1,\ldots,b_r$. Let $M_{ij}$ be the sum of products of edge weights over directed <paths> from $a_i$ to $b_j$. The <Lindström-Gessel-Viennot lemma> says that $\det M$ is the signed weighted sum of vertex-disjoint path families, with sign given by the <permutation> pairing sources to sinks. Expand the <determinant>: families with an intersection cancel by exchanging the tails of two paths at the first shared vertex, a sign-reversing <involution>. In planar arrangements where only the identity pairing can be disjoint, the <determinant> directly counts disjoint <lattice paths>.
Back to article page
