Lindström-Gessel-Viennot lemma

Let $G$ be an acyclic digraph with weight $w:E(G)\mapsto\mathbb{R}$. A path $P$ has weight $w(P):=\prod_{e\in E(P)}w(e)$. Define $$w(u,v)=\sum_{u,v\text{-path }P}w(P)$$ for $u,v\in V(G)$. Given vertex subsets $X,Y\subseteq V(G)$ with $X=\{x_1,\dots,x_m\}$ and $Y=\{y_1,\dots,y_m\}$, an $X,Y$-path system $\mathcal{P}$ consists of a permutation $\sigma_\mathcal{P}$ of $[m]$ and paths $P_1,P_2,\dots,P_m$ s.t. $P_i$ is an $x_i,y_{\sigma_\mathcal{P}(i)}$-path. It is a disjoint-path system if the paths are pairwise disjoint. Define an $m\times m$ matrix $$N=(n_{i,j})$$ where $n_{i,j}=w(x_i,y_j)$.

Lindström–Gessel–Viennot lemma: $$\det(N)=\sum_{\mathcal{P}=(P_1,\dots,P_m)\in\mathbf{P}}\text{sign}\left(\sigma_{\mathcal{P}}\right)\prod_{i=1}^mw(P_i)$$ where $\mathbf{P}$ is the set of all disjoint $X,Y$-path systems.

=======================================

Proof:

We show that the total contribution from the set $\mathbf{P}'$ of non-disjoint $X,Y$-path systems is zero to $\det(N)$, and the rest is obvious. This is done by giving an involution $f:\mathbf{P}'\to\mathbf{P}'$ s.t. $$\text{sign}\left(\mathcal{P}\right)=-\text{sign}\left(f\left(\mathcal{P}\right)\right)$$ for every $\mathcal{P}\in\mathbf{P}'$. In other words, we pair all non-disjoint $X,Y$-path systems so that every pair have opposite signs.

Given a non-disjoint $X,Y$-path systems $\mathcal{P}$, let $(i,j)\in[m]^2$ be the lexicographic smallest pair s.t. $P_i,P_j\in\mathcal{P}$ intersect, and let $u\in V(P_i)\cap V(P_j)$ be the first vertex on both paths. Obtain $P'_i$ and $P'_j$ by swapping the subpaths of $P_i$ and $P_j$ after $u$, and obtain $\mathcal{P'}=f\left(\mathcal{P}\right)$ by keeping all other paths unchanged. We clearly have $\text{sign}\left(\mathcal{P}\right)=-\text{sign}\left(f\left(\mathcal{P}\right)\right)$.