Linstrom-Gessel-Viennot theorem

Statement

Let $G = (V, E)$ be an acyclic, planar directed graph with edge weights $x_{e}$ for all $e \in E$ .
Select vertices $A_{1}, \dots, A_{n}$ and $B_{1}, \dots, B_{n}$ .

Let $C = (c_{i j})_{1 \leq i, j \leq n}$ be the $n \times n$ matrix such that

c_{i j} = \sum_{p : A_{i} \to B_{j}} wt (p)

where $p$ ranges over all paths $A_{i} \to B_{j}$ .

The number of noncrossing $n$ -tuples of paths counted with weights $(P_{1}, \dots, P_{n})$ such that $P_{i}$ connects $A_{i}$ to $B_{i}$ , $\sum_{(p_{1}, \dots, p_{n})} wt (p_{i})$ is equal to the determinant of the matrix $C = (c_{i j})$ .

Proof

We know that

\begin{aligned} det C & = \sum_{w_{1}, \dots, w_{n} \in S_{n}} (- 1)^{sign (w)} c_{1 w_{1}} c_{2 w_{2}} \dots c_{n w_{n}} \\ = \sum_{w \in S_{n}} \sum_{(p_{1}, \dots, p_{n}), p_{i} : A_{i} \to B_{w_{i}}} (- 1)^{sign (w)} \prod_{i} wt (P_{i}) \end{aligned}

we would like to show that the tuples of paths that cross cancel each other out. This can be done by exhibiting a sign-changing involution on these paths.

Given a tuple of path $(p_{1}, \dots, p_{n})$ that have a crossing,

find the smallest $i$ such that $p_{i}$ has a crossing with another path
Let $c$ be the first vertex of $p_{i}$ that intersects another path
Find the minimal $j \neq i$ that intersects $p_{i}$ at $c$
Take the tails of both paths (ie. the part of the path after $c$ ) and swap the two.
Note that this process yields another tuple of paths, where $w_{i}$ and $w_{j}$ are swapped. Thus, the sign of this permutation is swapped, and so these pairs of paths cancel out, leaving only the noncrossing paths.

Example

Pasted image 20260506123747.png