Lindström–Gessel–Viennot lemma

Remarks

Expand the determinant by the Leibniz formula: it is a signed sum over all families of paths $P_i$ from $a_i$ to $b_{\sigma(i)}$, disjoint or not. On the families that meet, define an involution as follows. Take the smallest $i$ such that $P_i$ meets another path, and the first vertex $v$ on $P_i$ that lies on another path. Take the smallest $j \ne i$ with $v \in P_j$, and swap the parts of $P_i$ and $P_j$ after $v$. The involution keeps the product of weights and changes the sign of $\sigma$, so these terms cancel.

Often the vertices are placed so that only $\sigma = \id$ admits disjoint paths. Then $\det M$ is the weighted number of families of disjoint paths from $a_i$ to $b_i$.

Example: in the grid $\Z^2$ with unit steps to the east and to the north and all weights $1$, take $a_1 = (0, 1)$, $a_2 = (1, 0)$, $b_1 = (1, 2)$, $b_2 = (2, 1)$. The path counts are binomial coefficients, $M = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$, and $\det M = 3$. Of the $4$ pairs of paths $a_1 \to b_1$, $a_2 \to b_2$, exactly one meets (both pass through $(1, 1)$), and no disjoint pair goes $a_1 \to b_2$, $a_2 \to b_1$; so there are $3$ disjoint pairs.

Going deeper

For a student

The lemma is a standard way to turn a determinant into a count, or a count into a determinant. It proves the Jacobi–Trudi formula for Schur functions, where semistandard tableaux become families of disjoint lattice paths. It also counts plane partitions in a box and rhombus tilings of hexagons. It is due to Lindström, and Gessel and Viennot brought it into enumerative combinatorics.