格子の道と行列式について

まず定義より、次の式が成り立つ。
\begin{eqnarray} \det{M}&=&\sum_{\sigma\in \mathfrak{S}_{n}}sign\left(\sigma\right)\left(\sum_{P_{1}:A_{1}\rightarrow B_{\sigma\left(1\right)}}w\left(P_{1}\right)\right)\left(\sum_{P_2:A_{2}\rightarrow B_{\sigma\left(2\right)}}w\left(P_{2}\right)\right)\cdots\left(\sum_{P_{n}:A_{n}\rightarrow B_{\sigma\left(n\right)}}w\left(P_{n}\right)\right)\\ &=& \sum_{\mathcal{P}\in\left(\mathcal{A}から\mathcal{B}への道の系\right)}sign\left(\sigma\right)\sum_{P_{1}:A_{1}\rightarrow B_{\sigma\left(1\right)}}\sum_{P_{2}:A_{2}\rightarrow B_{\sigma\left(2\right))}}\cdots \sum_{P_{n}:A_{n}\rightarrow B_{\sigma\left(n\right)}}w\left(P_{1}\right)w\left(P_{2}\right)\cdots w\left(P_{n}\right)\\ &=& \sum_{\mathcal{P}\in\left(\mathcal{A}から\mathcal{B}への道の系\right)}sign\left(\mathcal{P}\right)w\left(\mathcal{P}\right) \end{eqnarray}
示すべきことは以下の事である。それは$\mathcal{A}$から$\mathcal{B}$への道の系のうち頂点分離でない道の系を$\mathcal{N}$とすると、次の事が成り立つことである。\begin{equation} \sum_{\mathcal{P}\in\mathcal{N}}sign\left(\mathcal{P}\right)w\left(\mathcal{P}\right)=0 \end{equation}
実際、$\mathcal{P}\in \mathcal{N}$を道$P_{i}:A_{i}\rightarrow B_{\sigma\left(i\right)}$を持つものとする。すると道$\mathcal{N}$の定義より、少なくとも一つ道$P_{j}$が存在して共通の頂点を持つ。
その共通の頂点で$A_{i}$から出発して一番最初に$P_{i}$と$P_{j}$の最初に共有する頂点を$X$とする。
次に、$\pi$を$\pi\mathcal{P}=\left(P_{1}^{'},P_{2}^{'},...,P_{i}^{'},...,P_{j}^{'},...,P_{n}^{'}\right)$の様に定める。ただし、$P_{i}^{'}\quad\left(i=1,2,...,n\right)$は次の様な道をなす。
\begin{eqnarray} \left\{ \begin{array}{l} \cdot k\neq i,jに対してはP_{k}^{'}=P_{k} \\ \cdot P_{i}^{'}は頂点A_{i}から頂点Xまでの経路はP_{i}、頂点Xから頂点B_{\sigma\left(j\right)}への経路はP_{j}に沿う様にとる。\\ \cdot P_{j}^{'}は頂点A_{j}から頂点Xまでの経路はP_{j}、頂点Xから頂点B_{\sigma\left(i\right)}への経路はP_{i}に沿う様にとる。 \end{array} \right. \end{eqnarray}
すると、以下の事が分かる。
まず、$\pi\left(\pi\mathcal{P}\right)=\mathcal{P}$。これは明らか。また、$\pi\mathcal{P}$と$\mathcal{P}$は同じ辺を使用しているので$w\left(\pi\mathcal{P}\right)=w\left(\mathcal{P}\right)$となる。
また、新しい置換$\sigma^{'}$は置換$\sigma$に$\left(i,j\right)$をかけたものなので、$sign\left(\pi\mathcal{P}\right)=-sign\left(\mathcal{P}\right)$となる。ゆえに、補題は示された。

グラフ$G=\left(V,E\right)$を$\mathcal{A}=\{A_{1},A_{2},...,A_{r}\},\mathcal{B}=\{B_{1},B_{2},...,B_{s}\},\mathcal{C}=\{C_{1},C_{2},...,C_{r}\}$とし、
$E=\mathcal{A}\cap\mathcal{B}\cap\mathcal{C}$とする。また、$\mathcal{A}$と$mathcal{B}$の部分を見ると２部グラフ、また$\mathcal{B}$と$mathcal{C}$の部分を見たときも同様に２部グラフになる様に辺の集合$V$を構成する。
また、各辺の重みは$w\left(A_{i}\rightarrow B_{j}\right)=p_{ij},w\left(B_{j}\rightarrow C_{k}\right)=q_{jk}$となる様にとると、$\mathcal{A}$から$\mathcal{C}$への道の$\left(i,k\right)$行列$M$の成分$m_{ik}$はグラフの構成の仕方から$m_{ik}=\sum_{j=1}^{s}p_{ij}q_{jk}$。
また、繋いだグラフにおける$\mathcal{A}$から$\mathcal{C}$への頂点分離の道の系はそれぞれ$\mathcal{A}$から$\mathcal{B}$への頂点分離の道の系と$\mathcal{B}$から$\mathcal{C}$への頂点分離の道の系の対なので、下記の式が導かれるので証明が完了する。
\begin{eqnarray} \det{M}&=&\det{PQ}\\ &=&\sum_{\mathcal{Z}}sign\left(\sigma\tau\right)p_{i\sigma\left(j\right)}q_{\sigma\left(j\right)k}\\ &=&\sum_{\mathcal{Z}}sign\left(\sigma\right)p_{i\sigma\left(j\right)}sign\left(\tau\right)q_{\sigma\left(j\right)k}\\ &=&\sum_{\mathcal{Z}}\det{P}\det{Q} \end{eqnarray}

ビネ-コーシの公式