グラフと行列式：行列木定理・Pfaffian と Kasteleyn・Cauchy–Borchardt・Ihara–Bass・Kac–Ward、マトロイドと Nim

0. この記事の要点

点と線でできた図（グラフ）の上で「何通りあるか」を数えようとすると、場合の数は点の数とともに爆発的に増え、一つずつ数え上げるのは現実的ではありません。ところが、たとえば「輪を作らずにすべての点を線でつなぐ選び方（全域木）」の数は、図から作った表（行列）の行列式という一つの数を計算するだけで求まります。この記事は、なぜそのような近道が成り立つのかを、符号がうまく打ち消し合う仕組みとして見ていきます。読み終えると、全域木の数え上げ、ドミノ敷き詰めの数え上げ、2 次元の Ising 模型の分配関数が、どれも行列式（またはその平方根）で書ける理由が分かります。

• グラフの Laplacian $L=D-A$ は、向き付き接続行列 $B$ を使って $L=BWB^{\mathsf T}$ と分解できます。Cauchy–Binet の公式を当てると、$L$ から 1 行 1 列を除いた小行列式が全域木の重み和になります（行列木定理）。$K_n$ に当てれば Cayley の公式 $n^{n-2}$ が一行で出ます。
• 交代行列の行列式は完全平方で、$\det A=\operatorname{Pf}(A)^2$ です。証明は、置換を「二つの完全マッチングの重ね合わせ」と見る組合せ論的な対応です。
• 平面グラフには、各有界面の時計回りの辺が奇数本になる向き（Kasteleyn 向き）が存在し、その符号付き隣接行列の Pfaffian の絶対値が完全マッチング（すべての頂点を重なりなく 2 個ずつ組にする辺の選び方。マッチングの特別な場合）の個数に等しくなります。鍵は Euler の公式による偶奇の勘定です。
• $\det[1/(x_i+y_j)]$ は差積の比で閉じた形に書け（Cauchy の行列式）、その成分を 2 乗した行列の行列式は「行列式 × パーマネント（行列式の符号をすべて $+$ にした和）」になります（Borchardt の恒等式）。後者は、極の位数と次数を比べる議論で示します。
• 非後退な閉歩道（直前に通った辺をすぐ引き返さずに一周して戻る歩道）を数える Ihara ゼータ関数は、$2m$ 次の非後退行列 $B$ の行列式の逆数で、さらに $n$ 次の行列式 $\det(I-uA+u^2(D-I))$ に縮約できます（Ihara–Bass 公式）。証明は Sylvester の行列式恒等式一つです。
• 平面グラフの Ising 模型の分配関数（偶部分グラフの母関数）の 2 乗は、非後退行列に「曲がる角の半分」の位相を付けた行列 $T$ の $\det(I-T)$ に等しくなります（Kac–Ward 公式）。$I-T$ を交代行列に直して Pfaffian を閉路で展開し、閉路の符号を Whitney の回転数補題（回転数の偶奇 = 自己交差数の偶奇 + 1）で頂点での交差に移し、各頂点で「弦の交差の符号和は 1」という局所相殺を使って完全に証明します。
• 補遺（§8・§9）として、グラフの森を独立集合とするマトロイドで貪欲法（Kruskal のアルゴリズム）が最小全域木を与えることを証明し、有向非巡回グラフ上の 2 人ゲームについて、Nim の必勝法（Bouton の定理）を Sprague–Grundy の定理（ゲームの和の Grundy 値はニム和）から導きます。

この記事で使う事前知識

• 行列式: 正方行列に決まる 1 つの数で、列が一次従属なら $0$ になるもの。→ 行列式
• 余因子展開: 行列式を 1 つの行で展開して、1 つ小さい行列の行列式の和に直す方法。→ 余因子展開
• Cauchy–Binet の公式: 長方形の行列の積の行列式を、小行列式の積の和に展開する公式。→ コーシー・ビネの公式
• Sylvester の行列式恒等式: $\det(I+XY)=\det(I+YX)$。大きな行列式を小さな行列式に取り替えるのに使います。→ シルヴェスターの行列式恒等式
• Cayley の公式: 頂点 $n$ 個のラベル付きの木は $n^{n-2}$ 個。→ Cayley の公式

1. 動機

グラフの上で何かを数える問題の多くは、一見すると行列式と無関係です。全域木の数、ドミノ敷き詰めの数、閉路の数え上げ、Ising 模型の分配関数。どれも、場合の数が頂点数について指数的に増える和です。ところが行列式は多項式時間（Gauss の消去法なら $O(n^3)$）で計算できます。指数的な和が行列式で書けるというのは、その和の背後に「符号の相殺」という強い構造が隠れていることを意味します。

この章の定理はどれも、この相殺の仕組みを明示するものです。行列木定理では、全域木でない辺集合に対応する小行列式が「閉路があるので列が一次従属」という理由で消えます。Pfaffian では、奇数長の巡回をもつ置換が向きを反転する対合で打ち消し合います。Kasteleyn の定理では、平面性が符号をそろえます。Ihara–Bass と Kac–Ward では、後戻りする歩道が行列の構造の中で自動的に除かれます。

統計力学の格子模型（2 次元 Ising 模型、ダイマー模型）が厳密に解けるのは、分配関数がこのような行列式・Pfaffian で書けるからです。この章は、それらの厳密解と、行列式による評価を使う議論の前提を用意します。

2. 準備：グラフと接続行列

定義 2.1（グラフ・全域木・閉路）↗

グラフ $G=(V,E)$ は有限集合 $V$（頂点）と、各辺 $e\in E$ に二つの相異なる端点を対応させるデータからなる。同じ 2 頂点を結ぶ辺が複数あってもよい（多重辺）が、自己ループは考えない。$|V|=n$、$|E|=m$ と書く。辺の列 $e_1,\dots,e_k$ と頂点の列 $v_0,v_1,\dots,v_k=v_0$ で、$e_j$ が $v_{j-1}$ と $v_j$ を結び、$v_0,\dots,v_{k-1}$ が相異なり、辺も相異なるものを閉路という（多重辺 2 本は長さ 2 の閉路をなす）。閉路を含まない辺集合を森、連結な森を木という。辺集合 $S\subseteq E$ が全頂点を連結する木をなすとき、$S$ を全域木という。

補題 2.2（森の辺の数と葉）✓

1. 頂点数 $n$ の森で連結成分が $c$ 個なら、辺の数は $n-c$ である。とくに、$n$ 頂点上の $n-1$ 本の辺からなる集合は、閉路を含まなければ全域木である。
2. 2 頂点以上の木には、次数 $1$ の頂点（葉）が少なくとも二つある。

証明（補題 2.2）

2 から示します。木の中の最長の道 $v_0v_1\cdots v_k$（$k\ge1$）を取ります。$v_0$ に $v_1$ 以外の辺 $v_0w$ があれば、$w$ が道の上にあると閉路ができ、道の外にあると道が延びるので、どちらも矛盾です。よって $v_0$ は葉で、$v_k$ も同様です。

1: 頂点数についての帰納法です。辺がなければ $c=n$ で正しい。辺があれば、辺をもつ成分（木）から 2 によって葉 $v$ を一つ取り、$v$ とその辺を除きます。頂点が 1、辺が 1 減り、成分の数は変わらないので、帰納法の仮定から辺の数は $(n-1)-c+1=n-c$ です。後半は、閉路を含まない $n-1$ 本の辺の集合は森で、$n-1=n-c$ から $c=1$、すなわち連結だからです。

∎

定義 2.3（重み付き Laplacian と向き付き接続行列）↗

各辺 $e$ に重み $w_e$（複素数、または不定元）を与え、$W=\operatorname{diag}(w_e)_{e\in E}$ とする。重み付き Laplacian $L$ は $n$ 次正方行列で

$$L_{uu}=\sum_{e\ni u}w_e,\qquad L_{uv}=-\sum_{e:\,u\text{–}v}w_e\quad(u\neq v)$$

と定める（和は $u$ に接続する辺、および $u,v$ を結ぶ辺にわたる）。$w_e\equiv1$ なら $L=D-A$（$D$ は次数の対角行列、$A$ は隣接行列）。各辺に向き $t(e)\to h(e)$ を勝手に一つ選び、$n\times m$ 行列 $B$ を

$$B_{v,e}=\begin{cases}1&v=t(e)\\-1&v=h(e)\\0&\text{それ以外}\end{cases}$$

で定め、向き付き接続行列という。

補題 2.4（Laplacian の分解）✓

$L=BWB^{\mathsf T}$ である。とくに $L$ は向きの選び方によらない。

証明（補題 2.4）

$(BWB^{\mathsf T})_{uv}=\sum_ew_eB_{u,e}B_{v,e}$ です。$u=v$ のとき、$B_{u,e}^2$ は $e$ が $u$ に接続するとき $1$、そうでなければ $0$ なので $\sum_{e\ni u}w_e$ です。$u\neq v$ のとき $B_{u,e}B_{v,e}\neq0$ となるのは $e$ が $u,v$ を結ぶときだけで、そのとき一方が $1$、他方が $-1$ なので積は $-1$ です。向きを反転すると列 $B_{\cdot,e}$ が $-1$ 倍になりますが、$B_{u,e}B_{v,e}$ は変わりません。

∎

3. 行列木定理

頂点 $r$ を一つ固定し、$B$ から第 $r$ 行を除いた $(n-1)\times m$ 行列を $B_r$、$L$ から第 $r$ 行と第 $r$ 列を除いた $(n-1)$ 次正方行列を $L^{(r)}$ と書きます。補題 2.4 の両辺から第 $r$ 行・第 $r$ 列を除くと $L^{(r)}=B_rWB_r^{\mathsf T}$ です。$n-1$ 本の辺からなる集合 $S$ について、$B_r$ から列 $S$ を選んだ正方行列を $B_r[S]$ と書きます。

補題 3.1（接続行列の小行列式）✓

$|S|=n-1$ のとき、$S$ が全域木なら $\det B_r[S]=\pm1$、そうでなければ $\det B_r[S]=0$ である。

証明（補題 3.1）

全域木でない場合。 補題 2.2 の 1 により $S$ は閉路 $v_0e_1v_1\cdots e_kv_0$ を含みます。$e_j$ の向きが $v_{j-1}\to v_j$ なら $\varepsilon_j=1$、逆なら $\varepsilon_j=-1$ とおくと、$\varepsilon_jB_{\cdot,e_j}=\boldsymbol{1}_{v_{j-1}}-\boldsymbol{1}_{v_j}$（$\boldsymbol 1_v$ は第 $v$ 成分だけが $1$ の縦ベクトル）なので、

$$\sum_{j=1}^k\varepsilon_jB_{\cdot,e_j}=\sum_{j=1}^k(\boldsymbol 1_{v_{j-1}}-\boldsymbol 1_{v_j})=\boldsymbol 0$$

と和が望遠鏡式に消えます。第 $r$ 行を除いても関係は保たれるので、$B_r[S]$ の列は一次従属で、行列式は $0$ です（補題 7.2［行列式とその性質］）。

全域木の場合。 $n$ についての帰納法です。$n=2$ なら $B_r[S]$ は $1\times1$ 行列 $(\pm1)$ です。$n\ge3$ とします。補題 2.2 の 2 により木 $S$ には葉が二つ以上あるので、$r$ と異なる葉 $v$ が取れます。$v$ に接続する $S$ の辺は一つ $e$ だけなので、$B_r[S]$ の第 $v$ 行は第 $e$ 列に $\pm1$ があるだけで他は $0$ です。第 $v$ 行について余因子展開すると（定理 5.2［行列式とその性質］）、$\det B_r[S]=\pm\det M$ で、$M$ は第 $v$ 行と第 $e$ 列を除いた行列です。$M$ は、木 $S\setminus\{e\}$（頂点集合 $V\setminus\{v\}$ 上の全域木）の向き付き接続行列から第 $r$ 行を除いたものそのものなので、帰納法の仮定から $\det M=\pm1$ です。

∎

定理 3.2（行列木定理（Kirchhoff））✓

$G$ を $n\ge2$ 頂点のグラフ、$w_e$ を辺の重みとする。任意の頂点 $r$ について

$$\det L^{(r)}=\sum_{T:\ \text{全域木}}\ \prod_{e\in T}w_e$$

が成り立つ。とくに $w_e\equiv1$ なら、$L=D-A$ のどの対角余因子も全域木の個数 $\tau(G)$ に等しい。

証明（定理 3.2）

$L^{(r)}=(B_rW)\,B_r^{\mathsf T}$ に Cauchy–Binet の公式（定理 5.2［行列の固有値評価と不等式］）を当てます。$m\lt n-1$ なら $\det L^{(r)}=0$ で、辺が $n-1$ 本未満なので全域木もなく、両辺は $0$ です。$m\ge n-1$ なら

$$\det L^{(r)}=\sum_{|S|=n-1}\det\bigl((B_rW)[S]\bigr)\det\bigl(B_r^{\mathsf T}[S]\bigr)=\sum_{|S|=n-1}\Bigl(\prod_{e\in S}w_e\Bigr)\bigl(\det B_r[S]\bigr)^2 .$$

ここで $(B_rW)[S]=B_r[S]\operatorname{diag}(w_e)_{e\in S}$ と、転置で行列式が変わらないことを使いました。補題 3.1 により $(\det B_r[S])^2$ は $S$ が全域木なら $1$、そうでなければ $0$ です。

∎

この定理の要点は、符号の消える仕組みが「閉路 ⇒ 列の一次従属」という線形代数の事実で与えられていることです。木の数え上げという組合せ論の問題が、$O(n^3)$ で計算できる行列式に化けます。

例 3.3（完全グラフと Cayley の公式）

$K_n$ では $L=nI_n-J_n$（$J_n$ は全成分 $1$ の行列）なので、$L^{(r)}=nI_{n-1}-\boldsymbol 1\boldsymbol 1^{\mathsf T}$（$\boldsymbol 1\in\mathbb{R}^{n-1}$ は全成分 $1$）。Sylvester の行列式恒等式（系 4.5［行列の固有値評価と不等式］）で $X=-\boldsymbol 1/n$、$Y=\boldsymbol 1^{\mathsf T}$ とすると

$$\det L^{(r)}=n^{n-1}\det\Bigl(I_{n-1}-\tfrac1n\boldsymbol 1\boldsymbol 1^{\mathsf T}\Bigr)=n^{n-1}\Bigl(1-\frac{n-1}{n}\Bigr)=n^{n-2}.$$

定理 3.2 により、頂点 $[n]$ 上の木は $n^{n-2}$ 個です。これは前々章で母関数と Lagrange 反転を使って示した Cayley の公式（定理 5.4［数え上げと母関数］）の別証明になっています。

例 3.4（閉路グラフ）

$n$ 頂点の閉路 $C_n$（$n\ge3$）の全域木は、辺を一つ除いた $n$ 通りです。行列木定理で確かめると、$L^{(r)}$ は対角成分 $2$、隣接する非対角成分 $-1$ の $(n-1)$ 次三重対角行列です。$k$ 次のこの形の行列式を $d_k$ とすると、最後の行で展開して $d_k=2d_{k-1}-d_{k-2}$、$d_1=2$、$d_2=3$ なので $d_k=k+1$、よって $\det L^{(r)}=n$ です。

系 3.5（固有値による表示）✓

$w_e\equiv1$ とし、$L$ の固有値を $0=\lambda_1,\lambda_2,\dots,\lambda_n$（重複込み）とすると、$\tau(G)=\dfrac1n\lambda_2\lambda_3\cdots\lambda_n$ である。

証明（系 3.5）

$L\boldsymbol 1=\boldsymbol 0$ なので $0$ は固有値です。$p(\lambda)=\det(\lambda I-L)=\lambda\prod_{i\ge2}(\lambda-\lambda_i)$ の $\lambda$ の係数は $\prod_{i\ge2}(-\lambda_i)$ です。一方 $p'(0)$ を行列式の多重線形性で計算します。$\lambda$ は第 $r$ 行には $(r,r)$ 成分にしか現れないので、積の微分法則から $p'(\lambda)=\sum_r\det(\text{第 }r\text{ 行を }\boldsymbol 1_r^{\mathsf T}\text{ に置き換えた }\lambda I-L)$ で、これを第 $r$ 行で展開すると $p'(\lambda)=\sum_r\det\bigl((\lambda I-L)^{(r)}\bigr)$ です。$\lambda=0$ とおくと 定理 3.2 により $p'(0)=\sum_r(-1)^{n-1}\det L^{(r)}=(-1)^{n-1}n\,\tau(G)$。比べて $n\tau(G)=\lambda_2\cdots\lambda_n$ です。

∎

4. Pfaffian と Kasteleyn の定理

4.1. Pfaffian

$N=2n$ 次の交代行列 $A$（$A^{\mathsf T}=-A$）を考えます。$[N]$ の完全マッチングとは、$[N]$ を 2 元集合 $n$ 個に分割したものです。完全マッチング $M=\{\{i_1,j_1\},\dots,\{i_n,j_n\}\}$ を並べた語 $w=(i_1,j_1,i_2,j_2,\dots,i_n,j_n)$ に対し、$k\mapsto w_k$ を $[N]$ の置換と見たときの符号を $\operatorname{sgn}(w)$ と書き、

$$t_A(w)=\operatorname{sgn}(w)\prod_{k=1}^na_{w_{2k-1}w_{2k}}$$

とおきます。

補題 4.1（項は並べ方によらない）✓

$t_A(w)$ は、マッチング $M$ の対の並べる順序にも、各対の中の 2 元の順序にもよらない。これを $t_A(M)$ と書く。

証明（補題 4.1）

ある対の中の 2 元を入れ替えると、$\operatorname{sgn}(w)$ は互換一つ分 $-1$ 倍になり、$a_{ji}=-a_{ij}$ により積も $-1$ 倍になるので、$t_A(w)$ は不変です。隣り合う二つの対を入れ替えると、語の位置の置換は互換二つの積なので符号は不変で、積も不変です。対の並べ替えはすべて隣接する対の入れ替えの合成なので、主張が従います。

∎

定義 4.2（Pfaffian）↗

$2n$ 次の交代行列 $A$ の Pfaffian を

$$\operatorname{Pf}(A)=\sum_{M}t_A(M)$$

と定める。和は $[2n]$ の完全マッチング全体（$(2n-1)!!$ 個）にわたる。奇数次の交代行列では $\operatorname{Pf}(A)=0$ とする。

たとえば $\operatorname{Pf}\begin{pmatrix}0&a\\-a&0\end{pmatrix}=a$、4 次では $\operatorname{Pf}(A)=a_{12}a_{34}-a_{13}a_{24}+a_{14}a_{23}$ です（語 $1324$ の符号は $-1$、語 $1423$ の符号は $+1$）。

定理 4.3（Pfaffian の 2 乗は行列式）✓

交代行列 $A$ について $\det A=\operatorname{Pf}(A)^2$ である。

次の証明の方針は、行列式の各項（置換）を、二つの完全マッチングの組に作り替えることです。たとえば $4$ 個の元の置換 $\sigma:1\to2\to3\to4\to1$ は、辺 $\{1,2\},\{3,4\}$ からなるマッチング $M_1$ と、辺 $\{2,3\},\{4,1\}$ からなるマッチング $M_2$ を重ねると、$1,2,3,4$ を順にたどる一つの偶数長の閉路として復元できます。逆に、二つのマッチングを重ねると必ず偶数長の閉路の集まりになり、置換が決まります。この対応で、行列式が Pfaffian の 2 乗に見えてきます。

証明（定理 4.3）

$\det A=\sum_{\sigma}\operatorname{sgn}(\sigma)\prod_ia_{i\sigma(i)}$ の項を、$\sigma$ の巡回分解で分類します（定義 3.1［行列式とその性質］）。

奇数長の巡回をもつ置換は相殺する。 不動点 $\sigma(i)=i$ があれば $a_{ii}=0$ で項は $0$ です。不動点のない $\sigma$ が奇数長の巡回をもつとき、奇数長の巡回に属する元のうち最小のものを含む巡回（長さ $\ge3$）を逆向きにした置換を $\sigma'$ とします。$\sigma'\neq\sigma$ で、巡回の型が同じなので $\operatorname{sgn}\sigma'=\operatorname{sgn}\sigma$、逆にした巡回上の積は $a_{ji}=-a_{ij}$ を奇数回使うので $-1$ 倍です。$\sigma\mapsto\sigma'$ は対合なので（最小元の属する巡回は変わらない）、これらの項は対ごとに消えます。$N$ が奇数ならすべての置換が奇数長の巡回をもつので $\det A=0=\operatorname{Pf}(A)^2$ です。

偶数長の巡回だけの置換と、マッチングの対の全単射。 $\sigma$ の巡回をそれぞれ最小元 $c_1$ から $(c_1,c_2,\dots,c_{2k})$（$\sigma(c_j)=c_{j+1}$、添字は $2k$ を法として）と書き、すべての巡回について連結した語を $w_1$、各巡回を一つずらした $(c_2,c_3,\dots,c_{2k},c_1)$ を連結した語を $w_2$ とします。$w_1$ の隣り合う対から作るマッチングを $M_1=\{\{c_1,c_2\},\{c_3,c_4\},\dots\}$、$w_2$ からのものを $M_2=\{\{c_2,c_3\},\dots,\{c_{2k},c_1\}\}$ とします。逆に、マッチングの対 $(M_1,M_2)$ が与えられると、$M_1\cup M_2$（共通の対は 2 重辺とする）は各頂点の次数が $2$ なので、$M_1$ と $M_2$ の辺が交互に現れる偶数長の巡回に分かれます。各巡回で最小元から $M_1$ の辺、$M_2$ の辺、…の順にたどって $\sigma$ を定めると、上の構成の逆写像になります。

符号の一致。 $w_2=w_1\circ\rho$ で、$\rho$ は語の位置を巡回ごとのブロックの中で一つずらす置換です。長さ $2k$ のブロックのずらしは長さ $2k$ の巡回置換で符号 $-1$ なので、$\operatorname{sgn}\rho=(-1)^{(\text{巡回の数})}=\operatorname{sgn}\sigma$ です（$\sigma$ もすべて偶数長の巡回の積）。したがって

$$t_A(M_1)t_A(M_2)=\operatorname{sgn}(w_1)\operatorname{sgn}(w_2)\prod_{\text{巡回}}\prod_ja_{c_jc_{j+1}}=\operatorname{sgn}(\sigma)\prod_ia_{i\sigma(i)} .$$

長さ 2 の巡回 $(c_1,c_2)$ では $M_1,M_2$ が同じ対を含み、左辺の寄与は $a_{c_1c_2}^2$、右辺は $(-1)a_{c_1c_2}a_{c_2c_1}=a_{c_1c_2}^2$ で確かに一致しています。以上より

$$\det A=\sum_{(M_1,M_2)}t_A(M_1)t_A(M_2)=\operatorname{Pf}(A)^2 .$$∎

証明の中で示した等式 $t_A(M_1)t_A(M_2)=\operatorname{sgn}(\sigma)\prod_ia_{i\sigma(i)}$ は、次の Kasteleyn の定理でもう一度使います。

4.2. Kasteleyn の定理

グラフ $G$ の完全マッチングとは、辺の集合で、各頂点がちょうど一つの辺の端点になるものです。正方格子の部分グラフの完全マッチングは、ドミノ（$1\times2$ の長方形）による敷き詰めと一対一に対応します。

$G$ を単純グラフ（多重辺なし）とし、各辺に向きを与えたとき、符号付き隣接行列 $K$ を、辺 $u\to v$ があれば $K_{uv}=1$、$K_{vu}=-1$、辺がなければ $0$ と定めます。$K$ は交代行列で、定義 4.2 の和で $t_K(M)\neq0$ となるのは $M$ が $G$ の完全マッチングのときだけ、そのとき $t_K(M)=\pm1$ です。したがって

$$\operatorname{Pf}(K)=\sum_{M:\ G\text{ の完全マッチング}}t_K(M),\qquad t_K(M)\in\{\pm1\}$$

で、すべての $t_K(M)$ の符号がそろえば $|\operatorname{Pf}K|$ が完全マッチングの個数になります。平面グラフでは、そのような向きが存在します。

定義 4.4（Kasteleyn 向き）↗

$G$ を連結な単純グラフとし、平面に辺が交差しないように描いたもの（平面グラフ）で、各有界面の境界が単純閉路であるとする。各辺に向きを与えたとき、有界面 $F$ の境界の辺のうち、$F$ を右手に見て一周する向き（時計回り）と一致する辺の数を $\operatorname{cw}(F)$ とする。すべての有界面で $\operatorname{cw}(F)$ が奇数であるとき、この向きを Kasteleyn 向きという。単純閉路 $C$ についても同様に $\operatorname{cw}(C)$ を定める。

次の補題では、平面に描いた閉路の「内側」にある面や頂点の数を数えます。直感的には、閉路は平面を内側と外側に分け、内側の辺や面は外へ出られない、という事実を使います。以下の (i)〜(iii) はその厳密な形です。

平面グラフについては、Jordan の曲線定理（単純閉曲線は平面を内部と外部に分け、曲線はどちらの境界でもある。証明は 定理 4.2［Jordan の曲線定理と Jordan–Brouwer の分離定理］）と、そこから従う平面グラフの面についての次の基本事実を、証明なしに使います。(i) 閉路 $C$ の内部にある面はすべて $G$ の有界面で、$C$ の内部の辺は両側にそれぞれ内部の面をもち、$C$ の辺は内側にちょうど一つ面をもつ。(ii) 橋（除くと非連結になる辺）は両側が同じ面であり、両側が異なる面である辺を除いても連結性は保たれる。(iii) 有界面をもつ連結平面グラフには、片側が外面、反対側が有界面であるような辺がある（有界面の 1 点から無限遠へ半直線を引き、最後に有界面から外面へ抜ける箇所の辺を取ればよい）。Euler の公式 $V-E+F=2$ は 命題 3.1［四色定理］ で証明されています。

補題 4.5（閉路の時計回りの辺の偶奇）✓

Kasteleyn 向きの下で、任意の単純閉路 $C$ について

$$\operatorname{cw}(C)\equiv1+(C\text{ の内部にある頂点の数})\pmod 2 .$$

証明（補題 4.5）

$C$ の長さを $\ell$、内部の頂点の数を $v$、内部の辺（$C$ 上にない、内部にある辺）の数を $e$、内部の面を $F_1,\dots,F_f$ とします。

辺の勘定。 内部の辺は両側の面のうちちょうど一方に対して時計回りです（一方の面を右手に見る向きは、他方の面を左手に見る向きだから）。$C$ の辺は内側の面に対して時計回りであることと、$C$ に対して時計回りであることが同値です。よって $\sum_i\operatorname{cw}(F_i)=e+\operatorname{cw}(C)$ です。Kasteleyn 向きなので左辺は $f$ 個の奇数の和で、$\sum_i\operatorname{cw}(F_i)\equiv f$ です。

Euler の公式。 $C$ とその内部の頂点・辺からなる部分グラフ $H$ は連結です（内部の頂点から $G$ の道をたどると、$C$ を横切れないので $C$ 上の頂点に着く）。$H$ の面は $F_1,\dots,F_f$ と外側の一つなので、Euler の公式から $(\ell+v)-(\ell+e)+(f+1)=2$、すなわち $f=e-v+1$ です。

合わせると $\operatorname{cw}(C)\equiv f-e=1-v\equiv1+v\pmod2$ です。

∎

定理 4.6（Kasteleyn の定理）✓

定義 4.4 の仮定をみたす平面グラフ $G$ は Kasteleyn 向きをもつ。Kasteleyn 向きの符号付き隣接行列を $K$ とすると、$G$ の完全マッチングの個数は $|\operatorname{Pf}(K)|=\sqrt{\det K}$ に等しい。

証明（定理 4.6）

符号がそろうこと。 $M_1,M_2$ を完全マッチングとし、定理 4.3 の証明の対応で置換 $\sigma$ を作ると $t_K(M_1)t_K(M_2)=\operatorname{sgn}(\sigma)\prod_iK_{i\sigma(i)}=\prod_{\text{巡回}}\bigl(-\prod_jK_{c_jc_{j+1}}\bigr)$ です。長さ 2 の巡回の因子は $-K_{c_1c_2}K_{c_2c_1}=K_{c_1c_2}^2=1$ です。長さ $2k\ge4$ の巡回は $G$ の単純閉路 $C$ で、$\prod_jK_{c_jc_{j+1}}=(-1)^{(\text{たどる向きと逆向きの辺の数})}$ です。$C$ の内部の頂点は $M_1$ によって互いに組になります。実際、内部の頂点の $M_1$ の相手は $C$ 上にはなく（$C$ の頂点は $C$ の辺で組になっている）、辺は $C$ を横切れないので内部にあります。よって内部の頂点は偶数個で、補題 4.5 から $\operatorname{cw}(C)$ は奇数、$C$ の長さが偶数なので反時計回りの辺の数も奇数です。どちら向きにたどっても逆向きの辺は奇数本なので、巡回の因子は $-(-1)=1$ です。以上で $t_K(M_1)t_K(M_2)=1$ がすべての対で成り立ち、$t_K(M)$ はすべて等しい符号をもちます。$\operatorname{Pf}(K)=\pm(\text{完全マッチングの数})$ で、定理 4.3 から $\det K=\operatorname{Pf}(K)^2$ です。

存在。 有界面の数 $f$ についての帰納法です。$f=0$ なら、Euler の公式で $n-m+1=2$、すなわち $m=n-1$ で、$G$ は木です（連結で 補題 2.2 の 1 から閉路はない）。条件は空なので任意の向きでよい。$f\ge1$ なら、基本事実 (iii) により、片側が外面、反対側が有界面 $F$ である辺 $e$ があります。(ii) により $G-e$ は連結で、その有界面は $F$ 以外の $G$ の有界面と同じ境界をもちます。帰納法の仮定で $G-e$ に Kasteleyn 向きを与え、最後に $e$ の向きを、$F$ の時計回りの辺の数が奇数になるように選べばよい。

∎

2×3 の格子の Kasteleyn 向き。左の面は時計回りの辺が 3 本、右の面は 1 本で、どちらも奇数

例 4.7（正方形：向きの条件が必要な理由）

頂点 $1,2,3,4$ を正方形の左下・右下・右上・左上に置いた 4 頂点の閉路を考えます。完全マッチングは $\{12,34\}$ と $\{14,23\}$ の 2 個です。4 次の Pfaffian は $K_{12}K_{34}-K_{13}K_{24}+K_{14}K_{23}$ で、$K_{13}=K_{24}=0$ なので $K_{12}K_{34}+K_{14}K_{23}$ です。向きを $1\to2$、$2\to3$、$3\to4$、$1\to4$ とすると、時計回り（$1\to4\to3\to2\to1$）と一致するのは $1\to4$ だけで $\operatorname{cw}=1$、$\operatorname{Pf}=1\cdot1+1\cdot1=2$ です。一方、$4\to1$ に変えて全部を反時計回りにすると $\operatorname{cw}=0$ で、$\operatorname{Pf}=1-1=0$ となり、マッチングの数を数えません。

5. Cauchy の行列式と Borchardt の恒等式

定理 5.1（Cauchy の行列式）✓

$x_1,\dots,x_n,y_1,\dots,y_n$ を、すべての $i,j$ で $x_i+y_j\neq0$ となる複素数とする。このとき

$$\det\Bigl[\frac1{x_i+y_j}\Bigr]_{i,j=1}^n=\frac{\prod_{i\lt j}(x_j-x_i)(y_j-y_i)}{\prod_{i,j}(x_i+y_j)} .$$

証明（定理 5.1）

左辺を $C_n(x;y)$ とし、$n$ についての帰納法で示します。$n=1$ は明らかです。$i\lt n$ の各行から第 $n$ 行を引くと

$$\frac1{x_i+y_j}-\frac1{x_n+y_j}=\frac{x_n-x_i}{(x_i+y_j)(x_n+y_j)}$$

です。第 $i$ 行（$i\lt n$）から $x_n-x_i$ を、第 $j$ 列から $1/(x_n+y_j)$ をくくり出すと、第 $i$ 行（$i\lt n$）は $1/(x_i+y_j)$、第 $n$ 行はすべて $1$ の行列が残ります。次に $j\lt n$ の各列から第 $n$ 列を引くと、第 $n$ 行は $(0,\dots,0,1)$ になり、$i\lt n$ の成分は

$$\frac1{x_i+y_j}-\frac1{x_i+y_n}=\frac{y_n-y_j}{(x_i+y_j)(x_i+y_n)}$$

です。第 $j$ 列（$j\lt n$）から $y_n-y_j$ を、第 $i$ 行（$i\lt n$）から $1/(x_i+y_n)$ をくくり出し、第 $n$ 行で展開すると（定理 5.2［行列式とその性質］、行の基本変形で行列式は変わらない：命題 4.3［行列式とその性質］）

$$C_n=\frac{\prod_{i\lt n}(x_n-x_i)\prod_{j\lt n}(y_n-y_j)}{\prod_{j\le n}(x_n+y_j)\prod_{i\lt n}(x_i+y_n)}\,C_{n-1}(x_1,\dots,x_{n-1};y_1,\dots,y_{n-1}).$$

分母は $i=n$ または $j=n$ である対 $(i,j)$ 全体にわたる積です。帰納法の仮定を代入すれば主張です。

∎

例 5.2（Hilbert 行列）

$x=(1,2)$、$y=(0,1)$ とすると $[1/(x_i+y_j)]=\begin{pmatrix}1&1/2\\1/2&1/3\end{pmatrix}$（2 次の Hilbert 行列）で、直接計算すると行列式は $\frac13-\frac14=\frac1{12}$ です。公式では分子 $(2-1)(1-0)=1$、分母 $1\cdot2\cdot2\cdot3=12$ で一致します。Hilbert 行列の行列式が急速に $0$ に近づく（数値的に悪条件である）ことは、分母の積の増え方から読み取れます。

成分を 2 乗した行列について、パーマネント $\operatorname{per}[a_{ij}]=\sum_\sigma\prod_ia_{i\sigma(i)}$（符号を付けない行列式）を使った恒等式が成り立ちます。

定理 5.3（Borchardt の恒等式）✓

定理 5.1 と同じ仮定の下で、$a_{ij}=1/(x_i+y_j)$ とおくと

$$\det\bigl[a_{ij}^2\bigr]=\det\bigl[a_{ij}\bigr]\cdot\operatorname{per}\bigl[a_{ij}\bigr].$$

$n=2$ では $a_{11}^2a_{22}^2-a_{12}^2a_{21}^2=(a_{11}a_{22}-a_{12}a_{21})(a_{11}a_{22}+a_{12}a_{21})$ で、平方の差の因数分解にすぎません。一般の $n$ では、任意の行列について成り立つわけではありません（下の証明は Cauchy 行列の極の構造を本質的に使います）。

次の証明の方針は、$CP-D$ に分母 $\Pi^2$ を掛けた多項式 $G$ を考え、「次数がそれより大きい多項式で割り切れる」ことを示して $G=0$ を結論することです。割り切れることを示す鍵が、$x_1=-y_j$ での極の位数の比較です。

証明（定理 5.3）

$x,y$ を不定元とみなし、$\Pi=\prod_{i,j}(x_i+y_j)$ とおきます。$D=\det[a_{ij}^2]$、$C=\det[a_{ij}]$、$P=\operatorname{per}[a_{ij}]$、$F=CP-D$ として、多項式

$$G=F\cdot\Pi^2=(C\Pi)(P\Pi)-D\Pi^2$$

が $0$ であることを $n$ についての帰納法で示します。$n=1$ では $F=0$ です。

次数。 定理 5.1 から $C\Pi=\prod_{i\lt j}(x_j-x_i)(y_j-y_i)$ は次数 $n(n-1)$ の多項式です。$P\Pi$ は、各 $\sigma$ について $\sigma$ に現れない $n^2-n$ 個の因子 $x_i+y_j$ の積を足したもので、次数 $n^2-n$ の多項式です。$D\Pi^2$ も同様に次数 $2n^2-2n$ の多項式です。よって $G$ は次数 $2n^2-2n$ 以下の多項式です。

交代性。 $x_1$ と $x_2$ を入れ替えると、$C$ と $D$ は行の入れ替えで符号を変え、$P$ と $\Pi$ は不変です。よって $G$ も符号を変え、$x_1=x_2$ で $0$ になるので $x_1-x_2$ で割り切れます。同様に、すべての $x_i-x_j$、$y_i-y_j$（$i\lt j$）で割り切れます。

極は 1 位。 $x_1$ 以外の変数に、すべて相異なり $x_i+y_j\neq0$ となる複素数を代入し、$x_1$ の 1 変数有理関数として $x_1=-y_j$ の近くを見ます。第 1 行で展開すると $D=\sum_k(-1)^{1+k}a_{1k}^2D_{1k}$、$C=\sum_k(-1)^{1+k}a_{1k}C_{1k}$、$P=\sum_ka_{1k}P_{1k}$ で、小行列式・小パーマネント $D_{1k},C_{1k},P_{1k}$ は $x_1$ を含みません。$a_{1j}=1/(x_1+y_j)$ の 2 次の極の係数は、$D$ では $(-1)^{1+j}D_{1j}$、$CP$ では $(-1)^{1+j}C_{1j}P_{1j}$ です（$k\neq j$ の項は $x_1=-y_j$ で正則）。$D_{1j},C_{1j},P_{1j}$ は変数 $x_2,\dots,x_n$ と $y$ から $y_j$ を除いたものについての $n-1$ 次の同じ形の量なので、帰納法の仮定から $C_{1j}P_{1j}=D_{1j}$ で、$F$ の $x_1=-y_j$ での極は高々 1 位です。$\Pi^2$ は $(x_1+y_j)^2$ をちょうど 1 回含むので、$G$ は $x_1=-y_j$ で $0$ になります。代入した値は任意（有限個の条件を除く）なので、多項式 $G$ は超平面 $x_1+y_j=0$ 上で恒等的に $0$、すなわち $x_1+y_j$ で割り切れます。$G$ の交代性から $x_1$ を任意の $x_i$ に置き換えても同じで、$G$ はすべての $x_i+y_j$ で割り切れます。

結論。 $x_i-x_j$、$y_i-y_j$、$x_i+y_j$ は互いに定数倍でない 1 次式（既約多項式）なので、多項式環の素因数分解の一意性により、その積（次数 $n(n-1)+n^2=2n^2-n$）が $G$ を割り切ります。$G$ の次数は $2n^2-2n\lt 2n^2-n$ なので $G=0$ です。

∎

6. Ihara ゼータ関数と Ihara–Bass 公式

定義 2.1 のグラフ $G$ の各辺に両方の向きを与えた有向辺の集合を $\vec E$（$|\vec E|=2m$）とし、有向辺 $e$ の始点・終点を $t(e)$、$h(e)$、逆向きを $\bar e$ と書きます。

定義 6.1（非後退行列と Ihara ゼータ関数）↗

$2m$ 次の行列 $\mathcal B$ を、$h(e)=t(f)$ かつ $f\neq\bar e$ のとき $\mathcal B_{ef}=1$、それ以外は $0$ と定める（非後退行列、Hashimoto 行列）。有向辺の列 $(e_1,\dots,e_k)$ で、添字を $k$ を法として $h(e_j)=t(e_{j+1})$ かつ $e_{j+1}\neq\bar e_j$ をみたすものを、長さ $k$ の非後退閉歩道（基点付き）といい、その個数を $N_k$ とする。Ihara ゼータ関数を形式的冪級数

$$Z_G(u)=\exp\Bigl(\sum_{k\ge1}\frac{N_k}{k}u^k\Bigr)$$

で定める。

条件 $e_1\neq\bar e_k$ も課しているので、「行って戻るひげ」をもつ閉歩道は数えません。行列の積の定義から $(\mathcal B^k)_{ee}$ は $e_1=e$ である長さ $k$ の非後退閉歩道の数なので、$N_k=\operatorname{tr}\mathcal B^k$ です。

命題 6.2（Ihara ゼータ関数は行列式の逆数）✓

形式的冪級数として $Z_G(u)=\dfrac1{\det(I-u\mathcal B)}$。さらに、非後退閉歩道の巡回的なずらしによる同値類で、ある短い閉歩道の繰り返しでないもの（素な類）の全体を $\mathcal P$、類 $p$ の長さを $\ell(p)$ とすると

$$Z_G(u)=\prod_{p\in\mathcal P}\bigl(1-u^{\ell(p)}\bigr)^{-1}.$$

証明（命題 6.2）

行列式。 Jordan 標準形（定理 6.2［対角化とジョルダン標準形］）で $\mathcal B$ を上三角化すると、対角成分は固有値 $\lambda_1,\dots,\lambda_{2m}$ で、$\mathcal B^k$ の対角成分は $\lambda_i^k$、$I-u\mathcal B$ の対角成分は $1-u\lambda_i$ です。よって $\operatorname{tr}\mathcal B^k=\sum_i\lambda_i^k$、$\det(I-u\mathcal B)=\prod_i(1-u\lambda_i)$ で、

$$-\log\det(I-u\mathcal B)=\sum_i\sum_{k\ge1}\frac{\lambda_i^ku^k}{k}=\sum_{k\ge1}\frac{\operatorname{tr}\mathcal B^k}{k}u^k=\sum_k\frac{N_k}ku^k$$

が形式的冪級数として（$|u|$ が小さければ収束する級数としても）成り立ちます。

Euler 積。 長さ $k$ の基点付き非後退閉歩道 $c=(e_1,\dots,e_k)$ について、$c$ を $s$ だけずらしても $c$ に戻る $s\in\mathbb{Z}/k$ の全体は部分群なので、ある $d\mid k$ で生成されます。$c$ は最初の $d$ 個の有向辺からなる閉歩道 $q$ の $k/d$ 回の繰り返しです（$q$ が閉じて非後退であることは、$e_{d+1}=e_1$ と $c$ の条件から従う）。$q$ はそれ自身より短い周期をもたないので素で、$c$ のずらしは相異なる $d$ 個です。よって、長さ $d$ の素な類の数を $\pi_d$ とすると $N_k=\sum_{d\mid k}d\,\pi_d$ で、

$$\log\prod_{p}(1-u^{\ell(p)})^{-1}=\sum_d\pi_d\sum_{r\ge1}\frac{u^{dr}}{r}=\sum_k\frac{u^k}{k}\sum_{d\mid k}d\,\pi_d=\sum_k\frac{N_k}ku^k .$$∎

$2m$ 次の行列式が、実は頂点数 $n$ 次の行列式に縮約できるというのが次の定理です。

定理 6.3（Ihara–Bass の公式）✓

$G$ の隣接行列を $A$（$A_{uv}$ は $u,v$ を結ぶ辺の数）、次数の対角行列を $D$ とすると、

$$\det(I-u\mathcal B)=(1-u^2)^{m-n}\det\bigl(I-uA+u^2(D-I)\bigr).$$

次の証明の方針は、$2m$ 次の行列を、$n\times2m$ と $2m\times n$ の長方形の行列の積の形に書き直し、Sylvester の行列式恒等式で $n$ 次の行列式に取り替えることです。以下に並ぶ等式 $ST^{\mathsf T}=A$ などは、行列の積の成分を定義どおりに書き下せば確かめられます。たとえば $(ST^{\mathsf T})_{uv}=\sum_e[t(e)=u][h(e)=v]$ は、$u$ から $v$ へ向かう有向辺の数、つまり $A_{uv}$ です。

証明（定理 6.3）

$n\times2m$ 行列 $S,T$ を $S_{v,e}=[t(e)=v]$、$T_{v,e}=[h(e)=v]$ で、$2m$ 次の行列 $J$ を $J_{ef}=[f=\bar e]$ で定めます（$[\cdot]$ は条件が成り立てば $1$、そうでなければ $0$）。定義から直ちに

$$\mathcal B=T^{\mathsf T}S-J,\qquad ST^{\mathsf T}=A,\qquad TT^{\mathsf T}=D,\qquad SJ=T,\qquad J^2=I$$

です（たとえば $(T^{\mathsf T}S)_{ef}=[h(e)=t(f)]$ で、$f=\bar e$ の分を $J$ で引く。$(SJ)_{v,e}=[t(\bar e)=v]=[h(e)=v]$）。$u^2\neq1$ とします。$I+uJ$ は互いに素な $m$ 個の 2 次ブロック $\begin{pmatrix}1&u\\u&1\end{pmatrix}$ からなるので $\det(I+uJ)=(1-u^2)^m$、逆行列は $(I+uJ)^{-1}=(I-uJ)/(1-u^2)$ です。

$$I-u\mathcal B=(I+uJ)-uT^{\mathsf T}S=(I+uJ)\bigl(I-u(I+uJ)^{-1}T^{\mathsf T}S\bigr)$$

に Sylvester の行列式恒等式（系 4.5［行列の固有値評価と不等式］）を当てると

$$\det(I-u\mathcal B)=(1-u^2)^m\det\bigl(I_n-uS(I+uJ)^{-1}T^{\mathsf T}\bigr).$$

ここで $S(I-uJ)T^{\mathsf T}=ST^{\mathsf T}-uTT^{\mathsf T}=A-uD$ なので

$$\det(I-u\mathcal B)=(1-u^2)^m\det\Bigl(I-\frac{u(A-uD)}{1-u^2}\Bigr)=(1-u^2)^{m-n}\det\bigl((1-u^2)I-uA+u^2D\bigr)$$

です。両辺は $u$ の多項式（$m\lt n$ でも、左辺が多項式なので右辺も多項式）で、$u^2\neq1$ で一致するので恒等的に一致します。

∎

例 6.4（閉路グラフ）

$C_n$ では $m=n$、$D=2I$ で、$A$ の固有値は $2\cos(2\pi k/n)$（$k=0,\dots,n-1$）です（固有ベクトル $(\omega^{kv})_v$、$\omega=e^{2\pi i/n}$）。$1-2u\cos\theta+u^2=(1-ue^{i\theta})(1-ue^{-i\theta})$ と $\prod_k(1-u\omega^k)=1-u^n$ から、

$$\det(I-u\mathcal B)=\prod_{k}\bigl(1-u\omega^k\bigr)\bigl(1-u\omega^{-k}\bigr)=(1-u^n)^2 .$$

直接見ても、閉路上の非後退閉歩道は一方向に回り続けるしかなく、素な類は二つ（右回りと左回り）で、どちらも長さ $n$ です。

$(q+1)$ 正則グラフでは $\det(I-uA+qu^2I)=\prod_\lambda(1-\lambda u+qu^2)$ で、$Z_G$ の極は $A$ の固有値で決まります。自明でない固有値がすべて $|\lambda|\le2\sqrt q$ をみたすグラフ（Ramanujan グラフ）は、$Z_G$ の極が（自明なものを除き）円 $|u|=1/\sqrt q$ 上にあるという「グラフの Riemann 予想」をみたします。

7. Kac–Ward 公式

7.1. Ising 模型と偶部分グラフ

$G$ を単純グラフ、$J_e\ge0$ を結合定数とし、Ising 模型の分配関数 $\mathcal Z=\sum_{\sigma\in\{\pm1\}^V}\exp\bigl(\sum_{e=\{a,b\}}J_e\sigma_a\sigma_b\bigr)$ を考えます（逆温度は $J_e$ に含めます）。辺集合 $F\subseteq E$ で、各頂点に接続する $F$ の辺の数が偶数であるものを偶部分グラフといい、

$$\mathcal E(G;x)=\sum_{F:\ \text{偶部分グラフ}}\ \prod_{e\in F}x_e$$

とおきます（$F=\varnothing$ も含む）。

命題 7.1（高温展開）✓

$x_e=\tanh J_e$ とおくと $\mathcal Z=2^{n}\prod_{e}\cosh J_e\cdot\mathcal E(G;x)$ である。

証明（命題 7.1）

$\sigma_a\sigma_b\in\{\pm1\}$ なので $e^{J\sigma_a\sigma_b}=\cosh J+\sigma_a\sigma_b\sinh J=\cosh J\,(1+x\sigma_a\sigma_b)$ です。積を展開すると

$$\mathcal Z=\prod_e\cosh J_e\sum_{F\subseteq E}\Bigl(\prod_{e\in F}x_e\Bigr)\sum_\sigma\prod_{v}\sigma_v^{\deg_F(v)} .$$

$\sum_{\sigma_v=\pm1}\sigma_v^k$ は $k$ が偶数なら $2$、奇数なら $0$ なので、$\sigma$ の和は $F$ が偶部分グラフなら $2^n$、そうでなければ $0$ です。

∎

7.2. Kac–Ward 行列

$G$ を、辺を線分として交差なく平面に描いた単純グラフとします。有向辺 $e,f$ で $h(e)=t(f)$、$f\neq\bar e$ のとき、$e$ の向きから $f$ の向きへの回転角を $\angle(e,f)\in(-\pi,\pi)$ とします（$f\neq\bar e$ なので $\pm\pi$ にはならない）。

定義 7.2（Kac–Ward 行列）↗

$2m$ 次の行列 $T$ を

$$T_{ef}=\begin{cases}x_e\,e^{i\angle(e,f)/2}&h(e)=t(f),\ f\neq\bar e\\0&\text{それ以外}\end{cases}$$

で定める。$x_e\equiv u$ として位相を落とせば $T=u\mathcal B$ であり、$T$ は非後退行列に「曲がった角の半分」の位相を付けたものである。

定理 7.3（Kac–Ward 公式）✓

平面に線分で描いた単純グラフ $G$ と辺の重み $x_e$ について

$$\det(I-T)=\mathcal E(G;x)^2 .$$

証明（定理 7.3）

7.3 節と 7.4 節で示す補題を組み立てます（どの補題もこの定理を使わずに証明されます）。まず、すべての辺で $x_e\neq0$ とします。

1. 補題 7.13 により、交代行列 $K$ があって $\det(I-T)=P^2$、$P=\operatorname{Pf}(K)\prod_g x_g\bar u_{g^+}$ です。
2. 補題 7.14 により、$x$ によらない符号 $\epsilon\in\{\pm1\}$ があって

$$P=\epsilon\sum_{F}x^F\sum_{\pi}\prod_{j}\bigl(-e^{i\operatorname{rot}(\gamma_j)/2}\bigr)$$

です。$F$ は偶部分グラフ、$\pi=(\pi_v)_v$ は各頂点でのつなぎ方、$\gamma_j$ は $(F,\pi)$ が定める閉路です。 3. 補題 7.16 により、積 $\prod_j(-e^{i\operatorname{rot}(\gamma_j)/2})$ は $(-1)^{\sum_v\operatorname{cr}_v(\pi_v)}$ に等しくなります。ここが Whitney の回転数補題（定理 7.11）と平面性を使う箇所です。 4. $\pi$ は各頂点のつなぎ方 $\pi_v$ を独立に選んだものなので、内側の和は頂点ごとの和の積

$$\sum_\pi(-1)^{\sum_v\operatorname{cr}_v(\pi_v)}=\prod_v\sum_{\pi_v}(-1)^{\operatorname{cr}_v(\pi_v)}$$

に分かれ、補題 7.15 から各因子は $1$ です（$F$ の辺が $v$ に接続しなければ $\pi_v$ は空のつなぎ方一つで、因子は $1$）。

以上より $P=\epsilon\sum_Fx^F=\epsilon\,\mathcal E(G;x)$、したがって $\det(I-T)=\mathcal E(G;x)^2$ です。最後に、両辺は $x=(x_e)$ の多項式で、すべての $x_e$ が $0$ でない点で一致します。差の多項式 $D(x)$ を一つの変数 $x_{e_1}$ の多項式と見ると、他の変数を $0$ でない値に固定するごとに無限個の根をもつので係数がすべて $0$ になり、これを変数ごとに繰り返すと $D=0$ です。よって等式はすべての $x$ で成り立ちます。

∎

この定理と 命題 7.1 を合わせると、平面グラフ上の Ising 模型の分配関数は $2m$ 次の行列式の平方根で書けます。正方格子に周期境界条件を課して Fourier 変換で $T$ をブロック対角化すれば、Onsager の自由エネルギーの公式が出ます。

この節の残りでは、行列式を閉歩道の族に展開して、位相 $e^{i\angle/2}$ が符号を担う仕組みを見ます。証明に使う補題は 7.3 節（Whitney の回転数補題）と 7.4 節（Pfaffian の展開と局所相殺）で示します。

補題 7.4（閉歩道族への展開）✓

有向辺の非後退な巡回列 $\gamma=(e_1,\dots,e_k)$（$h(e_j)=t(e_{j+1})$、$e_{j+1}\neq\bar e_j$、添字は $k$ を法とし、$e_j$ は相異なる）に、重み $w(\gamma)=\prod_jx_{e_j}\cdot e^{i\operatorname{rot}(\gamma)/2}$、$\operatorname{rot}(\gamma)=\sum_j\angle(e_j,e_{j+1})$ を与える。このとき $\operatorname{rot}(\gamma)\in2\pi\mathbb{Z}$ で、

$$\det(I-T)=\sum_{\Gamma}\prod_{\gamma\in\Gamma}\bigl(-w(\gamma)\bigr)$$

が成り立つ。和は、どの有向辺も高々一度しか使わない巡回列の（順序なし）族 $\Gamma$ 全体にわたる（$\Gamma=\varnothing$ は $1$ を与える）。

証明（補題 7.4）

各列の多重線形性から $\det(I-T)=\sum_{S\subseteq\vec E}(-1)^{|S|}\det T[S]$ です（$T[S]$ は行・列を $S$ に制限した小行列）。$\det T[S]=\sum_\sigma\operatorname{sgn}(\sigma)\prod_{e\in S}T_{e\sigma(e)}$ の各項は、$S$ の置換 $\sigma$ の巡回がすべて非後退な巡回列であるときだけ $0$ でなく、そのとき巡回の積は $w(\gamma)$ です。$(-1)^{|S|}\operatorname{sgn}(\sigma)=\prod_{\text{巡回}}(-1)^{\text{長さ}}(-1)^{\text{長さ}-1}=(-1)^{(\text{巡回の数})}$ なので主張の形になります。$\operatorname{rot}(\gamma)$ は、向き $e_1$ から出発して各頂点で曲がった角の和で、一周すると向きが $e_1$ に戻るので $2\pi$ の整数倍です。

∎

したがって $e^{i\operatorname{rot}(\gamma)/2}=(-1)^{\operatorname{rot}(\gamma)/2\pi}$ は実数 $\pm1$ で、$\det(I-T)$ は実数です。

命題 7.5（単純な閉路は正の寄与）✓

$\gamma$ が $G$ の単純閉路を一方向に一周する巡回列なら $-w(\gamma)=+\prod_{e\in\gamma}x_e$ である。

証明（命題 7.5）

単純閉路の頂点を順に結んだ閉折れ線（定義 7.8）を考えると、$p_j$ での外角は $\angle(e_j,e_{j+1})\in(-\pi,\pi)$ で、回転数は $\operatorname{rot}(\gamma)$ です。単純閉路は各頂点を一度しか通らず、平面グラフの辺どうしは端点以外で交わらないので、この閉折れ線は自己交差をもたず一般の位置にあります（$\operatorname{cr}=0$）。定理 7.11 から $\operatorname{rot}(\gamma)/2\pi$ は奇数で、$e^{i\operatorname{rot}(\gamma)/2}=-1$、したがって $-w(\gamma)=\prod x_e$ です。（Hopf の回転数定理によれば実際には $\operatorname{rot}=\pm2\pi$ ですが、ここでは偶奇だけで足ります。）

∎

例 7.6（多角形での検算）

$G$ が $n$ 角形（閉路グラフ）なら、偶部分グラフは $\varnothing$ と全体だけで $\mathcal E=1+x_1\cdots x_n$ です。一方、非後退な巡回列は右回り・左回りの一周 $\gamma_+,\gamma_-$ の二つだけで、両者は有向辺を共有しないので、補題 7.4 の族は $\varnothing,\{\gamma_+\},\{\gamma_-\},\{\gamma_+,\gamma_-\}$ です。命題 7.5 から

$$\det(I-T)=1+2x_1\cdots x_n+(x_1\cdots x_n)^2=\mathcal E^2 .$$

位相 $e^{i\angle/2}$ を付けないと（$T=x\mathcal B$）、例 6.4 のように $(1-x^n)^2$ となり、符号が合いません。半角の位相は、単純な閉路の寄与を $-1$ 倍して正にするための装置です。

注意 7.7

一般のグラフでは、補題 7.4 の族 $\Gamma$ の閉歩道は頂点を共有し、一つの辺を両向きに 1 回ずつ使うこともあり、向き付きの閉歩道の和のまま $\mathcal E^2$ と比べると、向きの選び方についての大域的な勘定が残ります。そこで以下の証明では、$I-T$ を対角行列で挟んで交代行列 $K$ に直し、$\det(I-T)$ を $\operatorname{Pf}(K)$ の 2 乗として扱います。Pfaffian の項は向きのない「つなぎ方」で書けるので、残る仕事は二つに分かれます。(a) 閉路の符号 $-e^{i\operatorname{rot}/2}$ を、閉路を頂点の近くで少しずらして描いたときの交差の偶奇に移すこと（Whitney の回転数補題。ここで平面性を使う）。(b) 各頂点で、交差の偶奇を符号にしたつなぎ方の和が $1$ になること（局所相殺）。別の証明として、Lis（2016）の短い証明と、Kasteleyn の定理に帰着させる Cimasoni（2010）の証明があります（参考文献）。

7.3. Whitney の回転数補題

閉曲線の接線が一周する間に何回転するかを数えるのが回転数です。折れ線では、各角で曲がる角度（外角）の和として定めます。

定義 7.8（閉折れ線の回転数と交差数）↗

平面（$\mathbb{C}$ と同一視する）の点の列 $p_0,p_1,\dots,p_{N-1}$（添字は $N$ を法とする）で、各 $j$ について $p_{j+1}\neq p_j$ であり、$p_{j+1}-p_j$ が $p_j-p_{j-1}$ の負の実数倍でないものを閉折れ線という。$v_j=(p_{j+1}-p_j)/|p_{j+1}-p_j|$ とし、$p_j$ での外角 $\tau_j\in(-\pi,\pi)$ を $e^{i\tau_j}=v_j/v_{j-1}$ で、回転数を $\operatorname{rot}=\sum_j\tau_j$ で定める。$\prod_je^{i\tau_j}=1$ なので $\operatorname{rot}\in2\pi\mathbb{Z}$ である。

閉折れ線を、線分 $[p_j,p_{j+1}]$ を区間 $[j/N,(j+1)/N]$ で一定の速さでたどる周期 $1$ の連続写像 $\gamma:\mathbb{R}\to\mathbb{C}$ と同一視する。$0\le s\lt t\lt1$ かつ $\gamma(s)=\gamma(t)$ となる組 $(s,t)$ を交差といい、交差が有限個で、どの交差でも $\gamma(s)$ が二つの線分の内点であり、それら二つの線分が平行でないとき、$\gamma$ は一般の位置にあるという。交差の個数を $\operatorname{cr}(\gamma)$ と書く。二つの閉折れ線 $\gamma_1,\gamma_2$ についても、$s,t\in[0,1)$、$\gamma_1(s)=\gamma_2(t)$ となる組を交差と呼び、同じ条件で互いに一般の位置にあるといい、その個数を $\operatorname{cr}(\gamma_1,\gamma_2)$ と書く。

角度の変化を足し合わせるために、偏角を連続に追う道具を用意します。連続写像 $c:[a,b]\to S^1=\{z\in\mathbb{C}:|z|=1\}$ には、連続関数 $\vartheta:[a,b]\to\mathbb{R}$ で $c=e^{i\vartheta}$ となるもの（偏角の連続な選び方）があり、$2\pi$ の整数倍の定数を除いて一意です。これは被覆写像 $t\mapsto e^{2\pi it}$（例 3.3［基本群と被覆空間］）に対する道の持ち上げの存在と一意性（定理 3.6［基本群と被覆空間］）そのものです。$\vartheta(b)-\vartheta(a)$ を $c$ に沿った偏角の変化量と呼びます。道をつなげば変化量は足し算になり、逆にたどれば符号が変わり、閉じた道（$c(a)=c(b)$）の変化量は $2\pi$ の整数倍です。また、$c$ が $S^1$ の 1 点 $-e^{i\psi_0}$ を値にとらなければ、$S^1\setminus\{-e^{i\psi_0}\}$ から $(\psi_0-\pi,\psi_0+\pi)$ への連続な偏角 $\arg_{\psi_0}$ があるので、$\vartheta=\arg_{\psi_0}\circ c$ と取れ、変化量は $\arg_{\psi_0}c(b)-\arg_{\psi_0}c(a)$ です。以下これを (F) と呼びます。たとえば、互いに逆向きでない（$b\neq-a$）単位ベクトル $a,b$ について、$c(\lambda)$ が $(1-\lambda)a+\lambda b$ の向き（$\lambda\in[0,1]$）なら、$c$ は $a,b$ の挟む角の二等分方向の反対を値にとらないので、変化量は $a$ から $b$ への回転角 $\in(-\pi,\pi)$ です。

補題 7.9（穴のある領域の境界に沿った偏角）✓

$Q$ を平面の凸多角形、$R_1,\dots,R_r$ を $Q$ の内部にある互いに交わらない閉正方形（辺は座標軸に平行）とし、$R=Q\setminus\bigcup_k\operatorname{int}R_k$ とする。連続写像 $\phi:R\to S^1$ について、$\partial Q$ を反時計回りに一周する道に沿った $\phi$ の偏角の変化量は、各 $\partial R_k$ を反時計回りに一周する道に沿った変化量の和に等しい。

証明（補題 7.9）

$R$ はコンパクトなので $\phi$ は一様連続で、$\delta>0$ を、$|p-q|\lt\delta$ なら $|\phi(p)-\phi(q)|\lt1$ となるように取れます。各 $R_k$ の辺を延長した直線と、間隔 $\delta/2$ の縦横の直線で $Q$ を切ると、$Q$ は有限個の凸多角形（格子の長方形と $Q$ の共通部分）に分かれ、各 $R_k$ はそのいくつかの和になります。$R$ に含まれる小片 $\Delta$ の直径は $\delta$ 未満なので、$\Delta$ の 1 点 $q$ を取ると $\phi(\Delta)$ は $-\phi(q)$ を含みません（$|\phi(p)-\phi(q)|\lt1\lt2$）。(F) により $\Delta$ 全体で連続な偏角 $\arg_{\psi_0}\circ\phi$ が取れるので、$\partial\Delta$ を一周する変化量は $0$ です。

この $0$ を $R$ に含まれるすべての小片について足します。隣り合う二つの小片が共有する線分は、両方の反時計回りの境界で逆向きにたどられるので打ち消します。残るのは、$\partial Q$ 上の線分（$Q$ の反時計回りの向き）と、$\partial R_k$ 上の線分（$R$ を左に見る向き、すなわち $R_k$ の時計回り）です。よって $(\partial Q\text{ に沿った変化量})-\sum_k(\partial R_k\text{ に沿った変化量})=0$ です。

∎

補題 7.10（線形写像の像の偏角）✓

$L$ を $\mathbb{R}^2$ の可逆な線形写像、$R$ を原点を中心とする閉正方形とする。$\partial R$ を反時計回りに一周する道に沿った $L(p)/|L(p)|$ の偏角の変化量は、$\det L\gt0$ なら $2\pi$、$\det L\lt0$ なら $-2\pi$ である。

証明（補題 7.10）

原点からの半直線は $\partial R$ とちょうど 1 点で交わるので、$\partial R$ は $r(\psi)\boldsymbol{v}(\psi)$（$\boldsymbol{v}(\psi)=(\cos\psi,\sin\psi)$、$r\gt0$ 連続、$\psi\in[0,2\pi]$）とたどれ、$L(r\boldsymbol{v})/|L(r\boldsymbol{v})|=L\boldsymbol{v}/|L\boldsymbol{v}|$ です。$w(\psi)=L\boldsymbol{v}(\psi)$ の偏角の連続な選び方 $\vartheta$ は、局所的には滑らかな偏角の枝との合成なので微分でき、

$$\vartheta'=\frac{w_1w_2'-w_2w_1'}{|w|^2}=\frac{\det(w,w')}{|w|^2}=\frac{\det L\cdot\det(\boldsymbol{v},\boldsymbol{v}')}{|w|^2}=\frac{\det L}{|w|^2}$$

です（$w'=L\boldsymbol{v}'$、$\det(\boldsymbol{v},\boldsymbol{v}')=1$）。よって $\vartheta$ は $\det L$ の符号の向きに狭義単調です。$w(\psi+\pi)=-w(\psi)$ なので $\vartheta(\psi+\pi)-\vartheta(\psi)$ は $\pi$ の奇数倍です。その絶対値が $3\pi$ 以上なら、中間値の定理により $\psi\lt\psi'\lt\psi+\pi$ で $\vartheta(\psi')=\vartheta(\psi)\pm\pi$ となる $\psi'$ があり、$L\boldsymbol{v}(\psi')$ は $L\boldsymbol{v}(\psi)$ の負の実数倍、$L$ の可逆性から $\boldsymbol{v}(\psi')$ は $\boldsymbol{v}(\psi)$ の負の実数倍となって $\psi'\equiv\psi+\pi$ に矛盾します。よって半周ごとの変化は $\det L$ の符号をもつ $\pi$ で、一周で $\pm2\pi$ です。

∎

定理 7.11（Whitney の回転数補題（偶奇版））✓

一般の位置にある閉折れ線 $\gamma$ について

$$\frac{\operatorname{rot}(\gamma)}{2\pi}\equiv1+\operatorname{cr}(\gamma)\pmod 2 .$$

とくに $e^{i\operatorname{rot}(\gamma)/2}=-(-1)^{\operatorname{cr}(\gamma)}$ であり、自己交差のない閉折れ線では $e^{i\operatorname{rot}(\gamma)/2}=-1$ である。

Whitney（1937）は符号付きの等式 $\operatorname{rot}/2\pi=\pm1+\sum(\text{交差の符号})$ を示しました。Kac–Ward 公式に必要なのは偶奇だけなので、ここではその形で証明します。考え方は Hopf の「割線の方法」で、曲線上の 2 点を結ぶ向き $\gamma(t)-\gamma(s)$ を $(s,t)$ の 2 変数関数と見ます。

Whitney の補題の証明で使う (s, t) 平面の領域。対角線のすぐ上の辺では割線が接線を近似し、左と上の辺では最下点から見た向き、左上の角の短い辺では最下点の前後の割線を見る。交差の点（黒丸）を小さな正方形でくり抜く

証明（定理 7.11）

基点の選び方。 $\gamma$ の頂点のうち $y$ 座標が最小のもの、その中で $x$ 座標が最小のものを $p$ とし、番号を付け直して $p=p_0=\gamma(0)$ とします。$\gamma$ は線分の和なので $y$ 座標の最小値は頂点で取られ、$y$ 座標が最小の点は $p$ か $p$ より右にあります。一般の位置の仮定から交差は頂点で起きないので、$0\lt t\lt1$ なら $\gamma(t)\neq p$ です。よって $0\lt t\lt1$ のとき $\gamma(t)-p$ は集合 $H=\{y\gt0\}\cup\{y=0,\ x\gt0\}$ に入り、偏角を $[0,\pi)$ の値で連続に選べます。$p$ に入る線分の向きを $v_{-1}$、出る線分の向きを $v_0$ とし、$\alpha=\arg v_0$、$\beta=\arg(-v_{-1})$ とおくと、どちらも $[0,\pi)$ に入り、$v_0\neq-v_{-1}$ から $\alpha\neq\beta$ です。

領域。 $\eta\gt0$ を、どの線分の媒介変数の長さ $1/N$ よりも小さく、どの交差 $(s,t)$ についても $\eta\lt t-s\lt1-\eta$ となるように取ります。$(s,t)$ 平面の凸四角形

$$Q=\{(s,t):\ s\ge0,\ t\le1,\ \eta\le t-s\le1-\eta\}$$

（頂点 $(0,\eta)$、$(1-\eta,1)$、$(\eta,1)$、$(0,1-\eta)$）を取ると、交差はすべて $Q$ の内部にあり、$Q$ の交差以外の点では $\gamma(t)\neq\gamma(s)$ です（$s\lt t$ で、$(s,t)=(0,1)$ は含まれない）。各交差を中心とする小さな閉正方形 $R_k$ を、互いに交わらず $Q$ の内部にあり、その中で $s$ と $t$ がそれぞれ交差の点を含む線分の上に留まるように取ります。$\phi(s,t)=(\gamma(t)-\gamma(s))/|\gamma(t)-\gamma(s)|$ は $R=Q\setminus\bigcup\operatorname{int}R_k$ で連続です。

境界の 4 辺。 $\partial Q$ を反時計回りにたどり、各辺での $\phi$ の偏角の変化量を求めます。

• 下の辺 D（$t=s+\eta$、$s$ が $0$ から $1-\eta$ へ）: $\eta$ が線分の長さより短いので、$[s,s+\eta]$ に入る頂点は高々一つです。頂点を含まないとき割線 $\gamma(s+\eta)-\gamma(s)$ はその線分の向きで一定、頂点 $p_j$ を含むときは入る向き $v_{j-1}$ と出る向き $v_j$ の正係数の和で、$s$ が増えると $v_{j-1}$ の向きから $v_j$ の向きへ動きます。(F) によりこの間の変化量は外角 $\tau_j$ です。$s=0$ と $s=1-\eta$ では割線はそれぞれ $v_0$、$v_{-1}$ の向きで、途中で通る頂点は $p_0$ 以外のすべてなので、変化量は $\sum_{j\ne0}\tau_j=\operatorname{rot}-\tau_0$ です。
• 上の辺（$t=1$、$s$ が $1-\eta$ から $\eta$ へ）: $\phi$ は $p-\gamma(s)$ の向きで、偏角を $[\pi,2\pi)$ に選べます。変化量は $\arg(-v_0)-\arg(v_{-1})=(\alpha+\pi)-(\beta+\pi)=\alpha-\beta$ です。
• 角の辺（$t=s+1-\eta$、$s$ が $\eta$ から $0$ へ）: 周期性から $\gamma(t)=\gamma(s-\eta)$ で、$\gamma(s-\eta)-\gamma(s)$ は $-v_{-1}$ と $-v_0$ の非負係数の和です。$s=\eta$ で $-v_0$ の向き、$s=0$ で $-v_{-1}$ の向きなので、(F) により変化量は $-v_0$ から $-v_{-1}$ への回転角、すなわち $v_0$ から $v_{-1}$ への回転角 $-\tau_0$ です。
• 左の辺（$s=0$、$t$ が $1-\eta$ から $\eta$ へ）: $\phi$ は $\gamma(t)-p$ の向きで、偏角を $[0,\pi)$ に選べます。変化量は $\arg v_0-\arg(-v_{-1})=\alpha-\beta$ です。

合計は $\operatorname{rot}+2(\alpha-\beta-\tau_0)$ です。$e^{i\tau_0}=v_0/v_{-1}=e^{i(\alpha-\beta-\pi)}$ で、$\alpha-\beta\in(-\pi,\pi)$ です。$\alpha\gt\beta$ なら $\alpha-\beta-\pi\in(-\pi,0)$ なので $\tau_0=\alpha-\beta-\pi$、合計は $\operatorname{rot}+2\pi$。$\alpha\lt\beta$ なら $\tau_0=\alpha-\beta+\pi$ で、合計は $\operatorname{rot}-2\pi$ です。

穴の寄与。 交差 $(s_k,t_k)$ で $\gamma(s_k)=\gamma(t_k)=c$ とし、$s$ 側・$t$ 側の線分の向きを $a,b$、たどる速さを $\lambda,\lambda'\gt0$ とすると、$R_k$ の上で

$$\gamma(t)-\gamma(s)=\lambda'(t-t_k)\,b-\lambda(s-s_k)\,a$$

で、これは $(s-s_k,t-t_k)$ の線形写像です。$a,b$ が平行でないので可逆で、補題 7.10 から $\partial R_k$ に沿った変化量は $\pm2\pi$ です。

まとめ。 補題 7.9 により、$\operatorname{rot}\pm2\pi=2\pi\sum_k\epsilon_k$（$\epsilon_k\in\{\pm1\}$）です。両辺を $2\pi$ で割って $2$ を法とすると、$\operatorname{rot}/2\pi\equiv1+\operatorname{cr}(\gamma)$ です。後半は $e^{i\operatorname{rot}/2}=(-1)^{\operatorname{rot}/2\pi}$ から従います。

∎

同じ割線の方法を二つの曲線に使うと、交差が偶数個であることも出ます。

系 7.12（二つの閉折れ線の交差は偶数個）✓

互いに一般の位置にある二つの閉折れ線 $\gamma_1,\gamma_2$ について、$\operatorname{cr}(\gamma_1,\gamma_2)$ は偶数である。

証明（系 7.12）

交差は有限個なので、媒介変数の始点をずらして、交差 $(s,t)$ ではつねに $0\lt s,t\lt1$ となるようにできます。正方形 $Q=[0,1]^2$ の上で $\phi(s,t)=(\gamma_2(t)-\gamma_1(s))/|\gamma_2(t)-\gamma_1(s)|$ を考え、交差の周りを小さな正方形でくり抜きます。周期性から $\phi(s,0)=\phi(s,1)$、$\phi(0,t)=\phi(1,t)$ なので、$\partial Q$ を反時計回りにたどると下の辺と上の辺、右の辺と左の辺の変化量がそれぞれ打ち消し、合計は $0$ です。一方、定理 7.11 の証明と同じく各交差の正方形の寄与は $\pm2\pi$ です（補題 7.10）。補題 7.9 から $0=2\pi\sum_k\epsilon_k$ で、$\pm1$ の和が $0$ になるので項の数 $\operatorname{cr}(\gamma_1,\gamma_2)$ は偶数です。

∎

7.4. Kac–Ward 公式の証明

有向辺 $e$ の向きを表す単位複素数を $u_e$ とします（$e$ の始点から終点へ向かうベクトルを長さ $1$ にしたもの）。$u_{\bar e}=-u_e$ で、7.2 節の角は $e^{i\angle(e,f)}=u_f/u_e$ をみたします。各辺 $g$ について一方の向きの有向辺 $g^+$ を選び、他方を $g^-$ とします。重みは辺ごとに与えられているので $x_{\bar e}=x_e$ で、$\bar u=1/u$ は複素共役です。

次の補題の行列 $K$ は、天下りに見えるかもしれませんが、狙いは一つです。Pfaffian が使えるのは交代行列だけなので、$I-T$ に対角行列と $J$ を掛けて交代行列に直し、その行列式を Pfaffian の 2 乗として扱えるようにします。

補題 7.13（Kac–Ward 行列と交代行列）✓

すべての辺で $x_e\neq0$ とする。$2m$ 次の行列 $K$ を

$$K_{e\bar e}=\frac{u_e}{x_e},\qquad K_{ef}=-u_e\,e^{i\angle(e,\bar f)/2}\quad(h(e)=h(f),\ e\neq f),$$

それ以外の成分は $0$ と定める。$K$ は交代行列であり、

$$\det(I-T)=P^2,\qquad P=\operatorname{Pf}(K)\prod_{g\in E}x_g\,\bar u_{g^+}$$

が成り立つ。

証明（補題 7.13）

$h(e)=h(f)$、$e\neq f$ なら、$\bar f$ は $e$ の終点から出て $\bar f\neq\bar e$ なので、$\angle(e,\bar f)$ は定義されています。

$K$ の構成。 $X=\operatorname{diag}(x_e)$、$U_{ef}=e^{i\angle(e,f)/2}$（$h(e)=t(f)$、$f\neq\bar e$ のとき。それ以外 $0$）とおくと $I-T=X(X^{-1}-U)$ です。$\Lambda=\operatorname{diag}(u_e)$ と 定理 6.3 の証明の $J$（$J_{ef}=[f=\bar e]$）を使って $K=\Lambda X^{-1}(I-T)J$ となることを確かめます。右から $J$ を掛けると列 $f$ が列 $\bar f$ に置き換わるので、$(\Lambda(X^{-1}-U)J)_{ef}=u_e\bigl([\bar f=e]x_e^{-1}-U_{e\bar f}\bigr)$ です。$U_{e\bar f}\neq0$ となるのは $h(e)=t(\bar f)=h(f)$ かつ $\bar f\neq\bar e$、すなわち $h(e)=h(f)$、$e\neq f$ のときで、値は $e^{i\angle(e,\bar f)/2}$ です。これは $K$ の定義と一致します。

交代性。 対角成分は $0$ です（$e=\bar e$ はなく、$h(e)=h(e)$ でも $e\neq e$ は成り立たない）。$K_{\bar ee}=u_{\bar e}/x_{\bar e}=-u_e/x_e=-K_{e\bar e}$ です。$h(e)=h(f)$、$e\neq f$ のとき $\varphi=\angle(e,\bar f)$ とおくと $e^{i\varphi}=u_{\bar f}/u_e=-u_f/u_e$、$e^{i\angle(f,\bar e)}=-u_e/u_f=e^{-i\varphi}$ で、どちらの角も $(-\pi,\pi)$ にあるので $\angle(f,\bar e)=-\varphi$ です。よって

$$K_{fe}=-u_fe^{-i\varphi/2}=-\bigl(-u_ee^{i\varphi}\bigr)e^{-i\varphi/2}=u_ee^{i\varphi/2}=-K_{ef}$$

です。$K_{ef}\neq0$ となる条件は $e,f$ について対称なので、その他の成分はどちらも $0$ です。

行列式。 $\det\Lambda=\prod_g u_{g^+}u_{g^-}=\prod_g(-u_{g^+}^2)$、$\det X=\prod_gx_g^2$、$J$ は $m$ 個の互換の積なので $\det J=(-1)^m$ です。よって

$$\det K=\prod_g\frac{u_{g^+}^2}{x_g^2}\cdot\det(I-T)$$

で、定理 4.3（証明は成分が複素数でもそのまま通る）から $\det(I-T)=\bigl(\operatorname{Pf}(K)\prod_gx_g\bar u_{g^+}\bigr)^2=P^2$ です。

∎

次に $\operatorname{Pf}(K)$ を展開します。偶部分グラフ $F$ と、各頂点 $v$ で $F$ の $v$ に接続する辺（偶数本）を 2 本ずつの組に分ける分け方 $\pi_v$ の組 $\pi=(\pi_v)_v$ を考え、$\pi_v$ を $v$ でのつなぎ方と呼びます。$F$ の辺を、頂点 $v$ に着いたら $\pi_v$ で組になった辺へ進む、という規則でたどると、$F$ は辺を共有しない閉路 $\gamma_1,\dots,\gamma_r$ に分かれます。各 $\gamma_j$ は有向辺の巡回列 $(d_1,\dots,d_k)$ で、$h(d_l)=t(d_{l+1})$ かつ $d_{l+1}\neq\bar d_l$（非後退）をみたします。$\operatorname{rot}(\gamma_j)=\sum_l\angle(d_l,d_{l+1})$ は 補題 7.4 の証明と同じ理由で $2\pi$ の整数倍なので、$e^{i\operatorname{rot}(\gamma_j)/2}=\pm1$ です。逆向きにたどると角はすべて符号を変えるので、この値はたどる向きによりません。

補題 7.14（Pfaffian の閉路展開）✓

すべての辺で $x_e\neq0$ とする。$x$ によらない符号 $\epsilon\in\{\pm1\}$ があって

$$P=\epsilon\sum_{F}x^F\sum_{\pi}\prod_{j=1}^{r}\bigl(-e^{i\operatorname{rot}(\gamma_j)/2}\bigr)$$

が成り立つ。$F$ は偶部分グラフ全体、$\pi$ は $F$ のつなぎ方全体を動き、$x^F=\prod_{g\in F}x_g$、$\gamma_1,\dots,\gamma_r$ は $(F,\pi)$ が定める閉路である（$F=\varnothing$ では積は $1$）。

証明（補題 7.14）

どのマッチングが効くか。 定義 4.2 の和で $t_K(M)\neq0$ となるのは、$M$ のどの対も $\{e,\bar e\}$ の形か、$h(e)=h(f)$ をみたす $\{e,f\}$ の形のときだけです。$\mu_0=\{\{g^+,g^-\}:g\in E\}$ とします。そのような $M$ に対し、二つの向きが $M$ で組になっていない辺の集合を $F$ とします。$g\in F$ の $v$ に入る向きの相手 $f$ は $h(f)=v$ をみたし、$f$ の辺も $F$ に入ります（$f$ は $\bar f$ と組になっていない）。よって $v$ に入る $F$ の有向辺は $M$ によって互いに組になり、$F$ の辺の $v$ でのつなぎ方 $\pi_v$ が定まり、$\deg_F(v)$ は偶数です。逆に $(F,\pi)$ から $M$ が一通りに復元できるので、$t_K(M)\neq0$ となりうる $M$ と $(F,\pi)$ は一対一に対応します。

$\mu_0$ との比較。 定理 4.3 の証明で示した等式（定理 4.6 の証明でも使ったもの）により、$t_K(M)t_K(\mu_0)$ は $M\cup\mu_0$ の巡回 $(c_1,\dots,c_{2k})$ ごとの因子 $-\prod_lK_{c_lc_{l+1}}$ の積です。$g\notin F$ の対 $\{g^+,g^-\}$ は長さ 2 の巡回で、因子は $K_{g^+g^-}^2=u_{g^+}^2/x_g^2$ です。長い巡回は $M$ の対と $\mu_0$ の対を交互にたどるので、適当な番号付けで

$$(d_1,\ \bar d_2,\ d_2,\ \bar d_3,\ \dots,\ d_k,\ \bar d_1)$$

の形をしています。ここで $\{d_l,\bar d_{l+1}\}$ が $M$ の対、$\{\bar d_{l+1},d_{l+1}\}$ が $\mu_0$ の対です。$h(d_l)=h(\bar d_{l+1})=t(d_{l+1})$ なので $(d_1,\dots,d_k)$ は閉じた歩道で、$\bar d_{l+1}\neq d_l$ から非後退であり、$d_l$ の辺から $d_{l+1}$ の辺へは $\pi$ に従って進んでいます。つまりこれは $(F,\pi)$ の閉路の一つで、$F$ の各辺はちょうど一つの巡回にちょうど一回現れます（巡回を逆にたどる番号付けなら、逆向きの閉路になるだけです）。この巡回の因子は

$$K_{d_l\bar d_{l+1}}K_{\bar d_{l+1}d_{l+1}}=\bigl(-u_{d_l}e^{i\angle(d_l,d_{l+1})/2}\bigr)\Bigl(-\frac{u_{d_{l+1}}}{x_{d_{l+1}}}\Bigr)=\frac{u_{d_l}u_{d_{l+1}}}{x_{d_{l+1}}}e^{i\angle(d_l,d_{l+1})/2}$$

の積の $-1$ 倍、すなわち $-e^{i\operatorname{rot}(\gamma)/2}\prod_lu_{d_l}^2/x_{d_l}$ です。$u_{g^-}^2=u_{g^+}^2$ に注意して全部掛けると

$$t_K(M)\,t_K(\mu_0)=\prod_j\bigl(-e^{i\operatorname{rot}(\gamma_j)/2}\bigr)\cdot x^F\cdot\prod_{g\in E}\frac{u_{g^+}^2}{x_g^2}.$$

まとめ。 語 $w_0=(g_1^+,g_1^-,\dots,g_m^+,g_m^-)$ の符号を $\epsilon=\operatorname{sgn}(w_0)$ とすると $t_K(\mu_0)=\epsilon\prod_gu_{g^+}/x_g\neq0$ です。上の等式をこれで割ると $t_K(M)=\epsilon\prod_j(-e^{i\operatorname{rot}(\gamma_j)/2})\,x^F\prod_gu_{g^+}/x_g$ で、$M$ について足して $\prod_gx_g\bar u_{g^+}$ を掛ければ主張を得ます。$\epsilon$ は番号付けだけで決まり、$x$ によりません。

∎

次の補題が局所相殺の中身です。

補題 7.15（弦の交差の符号和は 1）✓

円周上の相異なる $2k$ 個の点を 2 個ずつの組に分ける分け方（完全マッチング）$M$ について、各組を弦で結んだとき、端点が円周上で交互に並ぶ（弦が交わる）組の対の数を $\operatorname{cr}(M)$ とする。このとき

$$\sum_{M}(-1)^{\operatorname{cr}(M)}=1$$

である（$k=0$ では空の分け方一つ）。

証明（補題 7.15）

$k$ についての帰納法です。点に円周の順に $1,\dots,2k$ と番号を付け、点 $1$ の相手を $j$ とします。弦 $\{1,j\}$ と交わるのは、端点の一方だけが $\{2,\dots,j-1\}$ にある弦です。この $j-2$ 個の点のうち、互いに組になっている点は偶数個なので、外と組になっている点の数、すなわち $\{1,j\}$ と交わる弦の数は $j$ と偶奇が等しくなります。$\{1,j\}$ を除いた残りは、残る $2k-2$ 点の分け方 $M'$ で、その中の交差は変わりません。よって

$$\sum_M(-1)^{\operatorname{cr}(M)}=\sum_{j=2}^{2k}(-1)^j\sum_{M'}(-1)^{\operatorname{cr}(M')}=\sum_{j=2}^{2k}(-1)^j=1$$

です（帰納法の仮定で内側の和は $1$、外側は $+1-1+\dots+1$ の $2k-1$ 項）。

∎

最後に、閉路の符号を頂点での交差に移します。各頂点 $v$ で、$v$ に接続する辺を $v$ のまわりの反時計回りの順に円周上の点として並べ、つなぎ方 $\pi_v$ の組を弦で結んだときの交差の数を $\operatorname{cr}_v(\pi_v)$ とします。

補題 7.16（閉路の符号は頂点での交差で決まる）✓

平面に線分で描いた単純グラフ $G$ の偶部分グラフ $F$ とつなぎ方 $\pi$ について、$(F,\pi)$ が定める閉路を $\gamma_1,\dots,\gamma_r$ とすると

$$\prod_{j=1}^r\bigl(-e^{i\operatorname{rot}(\gamma_j)/2}\bigr)=(-1)^{\sum_v\operatorname{cr}_v(\pi_v)} .$$

証明（補題 7.16）

描き方。 $\delta\gt0$ を、相異なる頂点の距離の半分より小さく、どの頂点からそれを端点としない辺への距離よりも小さく取ります。頂点 $v$ と $v$ に接続する辺 $g$ について、$v$ から $g$ に沿った単位ベクトルを $a_{v,g}$、$q_{v,g}=v+\delta a_{v,g}$ とします。単純グラフを線分で描いているので、$v$ に接続する辺の向き $a_{v,g}$ は相異なり、$q_{v,g}$ は $v$ を中心とする半径 $\delta$ の円周上に、辺の反時計回りの順に並びます。閉路 $\gamma=(d_1,\dots,d_k)$ を、各 $l$ について「辺 $d_l$ を両端から $\delta$ ずつ縮めた線分（素線）」と「$v=h(d_l)$ で $q_{v,d_l}$ から $q_{v,d_{l+1}}$ へ引く弦」を交互につないだ閉折れ線として描きます（$q_{v,d}$ の $d$ は有向辺 $d$ の辺を表す）。

回転数は変わらない。 $v=h(d_l)$ で $a=a_{v,d_l}$、$b=a_{v,d_{l+1}}$ とおくと、素線 $d_l$ の向きは $-a$、弦の向きは $b-a$、次の素線の向きは $b$ です。$\psi=\angle(d_l,d_{l+1})$ とすると $e^{i\psi}=b/(-a)$、$\psi\in(-\pi,\pi)$ で、

$$b-a=(-a)\bigl(1+e^{i\psi}\bigr)=(-a)\,e^{i\psi/2}\cdot2\cos(\psi/2),\qquad\cos(\psi/2)\gt0$$

なので、弦は $-a$ と $b$ の二等分方向を向きます。この 2 か所の外角はどちらも $\psi/2$ で、和は $\angle(d_l,d_{l+1})$ です。とくに隣り合う線分が逆向きになることはなく、描いた閉折れ線の回転数は $\operatorname{rot}(\gamma)$ に等しくなります。

交わり方。 平面グラフの相異なる辺は端点でしか交わらず、素線は端点を含まないので、素線どうしは交わりません（$F$ の各辺はちょうど一つの閉路で一回だけ使われる）。$v$ での弦は閉円板 $B(v,\delta)$ に入り、円周に触れるのは両端だけです。$v$ に接続する辺の素線は $v$ から遠ざかる向きに伸びるので、$B(v,\delta)$ とは端点 $q_{v,g}$ でしか触れず、$v$ に接続しない辺の素線は $\delta$ の選び方から $B(v,\delta)$ と交わりません。異なる頂点の円板は交わりません。したがって、つなぎ目以外で起きる交わりは同じ頂点の二本の弦の交わりだけです。二本の弦の 4 つの端点は円周上の相異なる点なので、弦が交わるのは端点が交互に並ぶときに限り、そのとき交点は両方の弦の内点で、二本は平行ではありません。よって描いた閉折れ線たちはそれぞれ一般の位置にあり、互いにも一般の位置にあって、

$$\sum_j\operatorname{cr}(\gamma_j)+\sum_{j\lt l}\operatorname{cr}(\gamma_j,\gamma_l)=\sum_v\operatorname{cr}_v(\pi_v)$$

です。

符号。 定理 7.11 から $-e^{i\operatorname{rot}(\gamma_j)/2}=(-1)^{\operatorname{cr}(\gamma_j)}$、系 7.12 から $\operatorname{cr}(\gamma_j,\gamma_l)$ は偶数です。よって左辺の積は $(-1)^{\sum_j\operatorname{cr}(\gamma_j)}=(-1)^{\sum_v\operatorname{cr}_v(\pi_v)}$ です。

∎

これで 定理 7.3 の証明に必要な補題がそろいました。平面性を使ったのは 補題 7.16 の「交わりは頂点の近くでしか起きない」という一点だけです。平面に描けないグラフ（辺が交差する描き方）では、辺の交差ごとに符号が一つずつずれ、$\det(I-T)$ は $\mathcal E^2$ からずれます。

8. マトロイドと貪欲法

行列木定理は全域木を「数える」定理でした。全域木のうち辺の重みの和が最小のもの（最小全域木）を「求める」問題は、組合せ最適化の最も基本的な問題で、辺を軽い順に取っていくだけの単純な方法（貪欲法）で解けます。なぜそれで最適になるかを説明する構造が、マトロイドです。

定義 8.1（マトロイド）↗

有限集合 $E$ と、$E$ の部分集合の族 $\mathcal{I}$（その元を独立集合という）の組 $(E,\mathcal{I})$ がマトロイドであるとは、次の 3 条件を満たすことをいう。

• (I1) $\varnothing\in\mathcal{I}$。
• (I2)（遺伝性）$J\subseteq I\in\mathcal{I}$ ならば $J\in\mathcal{I}$。
• (I3)（交換公理）$I,J\in\mathcal{I}$ かつ $|I|<|J|$ ならば、$I\cup\{x\}\in\mathcal{I}$ となる $x\in J\setminus I$ が存在する。

$E$ の部分集合 $A$ の極大独立部分集合（$A$ に含まれる独立集合のうち、包含で極大のもの）を、$A=E$ のとき基という。

命題 8.2（極大独立部分集合の大きさは一定）✓

$(E,\mathcal{I})$ をマトロイドとする。$A\subseteq E$ の極大独立部分集合はすべて同じ元の個数をもつ（これを $A$ の階数 $r(A)$ という）。とくに基はすべて同じ大きさ $r(E)$ をもつ。

証明（命題 8.2）

$I,J$ を $A$ の極大独立部分集合とし、$|I|<|J|$ と仮定します。定義 8.1 の (I3) により $I\cup\{x\}\in\mathcal{I}$ となる $x\in J\setminus I\subseteq A$ があり、$I\cup\{x\}\subseteq A$ は $I$ の極大性に反します。対称に $|J|<|I|$ も起きません。

∎

例 8.3（線形マトロイド）

体 $K$ 上のベクトル空間のベクトルの有限族 $(v_e)_{e\in E}$ について、$I\subseteq E$ を「$(v_e)_{e\in I}$ が一次独立」で独立と定めるとマトロイドです。(I1)(I2) は明らかです。(I3)：$|I|<|J|$ とし、すべての $x\in J\setminus I$ について $I\cup\{x\}$ が従属だと仮定します。$I$ が独立なので、このとき $v_x\in\mathrm{span}(v_e:e\in I)$ です。$x\in J\cap I$ でもこれは自明に成り立つので、$J$ のすべてのベクトルが、$|I|$ 次元の空間 $\mathrm{span}(v_e:e\in I)$ に入ります。そこに $|J|>|I|$ 個の一次独立なベクトルが入ることになり、取り替え補題（補題 5.4［ベクトル空間と線形変換］）に反します。この場合の階数は、ベクトルの張る空間の次元です。

命題 8.4（グラフ的マトロイド）✓

$G=(V,E)$ をグラフとし、$\mathcal{I}$ を森（閉路を含まない辺集合）の全体とする。$(E,\mathcal{I})$ はマトロイドである。$G$ が連結なら、その基は全域木にほかならない。

証明（命題 8.4）

(I1)(I2) は明らかです。(I3)：$I,J$ を森とし $|I|<|J|$ とします。グラフ $(V,I)$、$(V,J)$ の連結成分の個数を $c(I)$、$c(J)$ とすると、補題 2.2 の 1 から $|I|=|V|-c(I)$、$|J|=|V|-c(J)$ なので $c(J)<c(I)$ です。$J$ のすべての辺の両端が $I$ の同じ連結成分に入るとすると、$J$ の辺をたどる道は $I$ の 1 つの連結成分の外へ出ないので、$J$ の各連結成分は $I$ の 1 つの連結成分に含まれ、$c(J)\ge c(I)$ となって矛盾です。したがって、両端が $I$ の異なる連結成分にある辺 $e\in J$ があります。$I$ の辺は両端が同じ成分にあるので $e\notin I$ で、異なる成分の 2 頂点を結ぶ辺を足しても閉路はできないので $I\cup\{e\}$ は森です。

連結な $G$ では、基（極大な森）$F$ について、$(V,F)$ が連結でなければ、$G$ の連結性から異なる成分を結ぶ $G$ の辺があり、それを足すと $F$ より大きい森ができて極大性に反します。よって $F$ は連結な森、すなわち全域木で、補題 2.2 の 1 から $|F|=|V|-1$ です。逆に全域木 $T$ は、$|V|-1$ 本の辺をもつ森で、ある基 $F\supseteq T$ に含まれます（有限集合なので極大な独立集合に拡張できる）。命題 8.2 により基の大きさはすべて $|V|-1$ なので $F=T$、すなわち $T$ は基です。

∎

マトロイドの上で、各要素 $e\in E$ に重み $w(e)\in\mathbb{R}$ が与えられているとき、基 $B$ の重み $w(B)=\sum_{e\in B}w(e)$ を最大にする基を求める問題を考えます。次の手続きを貪欲法といいます。$E$ の元を重みの大きい順に $e_1,e_2,\dots,e_m$ と並べます（同じ重みは任意の順で固定する）。$I=\varnothing$ から始め、$i=1,\dots,m$ について、$I\cup\{e_i\}\in\mathcal{I}$ なら $e_i$ を $I$ に加えます。

定理 8.5（貪欲法の最適性）✓

マトロイド $(E,\mathcal{I})$ と重み $w:E\to\mathbb{R}$ に対し、貪欲法の出力 $G$ は基であり、重みが最大の基である。

証明（定理 8.5）

$G$ が基であること：$G$ は独立です。$e\notin G$ なら、$e$ を考えた時点の集合 $I_e\subseteq G$ について $I_e\cup\{e\}\notin\mathcal{I}$ です。もし $G\cup\{e\}\in\mathcal{I}$ なら、(I2) により部分集合 $I_e\cup\{e\}$ も独立になって矛盾するので、$G\cup\{e\}\notin\mathcal{I}$ です。したがって $G$ は極大独立、すなわち基です。

最適性：$G=\{g_1,\dots,g_r\}$ を、並べた順（$e_1,\dots,e_m$ の順）で $g_1,\dots,g_r$ とします。$B=\{b_1,\dots,b_r\}$ を任意の基とし、同じ順序で並べます（命題 8.2 により大きさは $r$）。$w(g_i)\ge w(b_i)$ をすべての $i$ で示せば、$w(G)\ge w(B)$ です。

$w(g_i)<w(b_i)$ となる最小の $i$ があったとします。$I_0=\{g_1,\dots,g_{i-1}\}$（独立、大きさ $i-1$）と $\{b_1,\dots,b_i\}$（独立、大きさ $i$）に (I3) を使うと、$b_j\notin I_0$（$j\le i$）で $I_0\cup\{b_j\}\in\mathcal{I}$ となるものがあります。$w(b_j)\ge w(b_i)>w(g_i)$ ですから、並べた順で $b_j$ は $g_i$ より前にあります。貪欲法が $b_j$ を考えた時点の集合 $I'$ は、$b_j$ より前に採用された元の集まりで、$g_i$ より前なので $I'\subseteq I_0$ です。(I2) から $I'\cup\{b_j\}\subseteq I_0\cup\{b_j\}$ は独立で、貪欲法は $b_j$ を採用します。すると $b_j$ は $g_i$ より前の $G$ の元、すなわち $b_j\in I_0$ ですが、これは $b_j\notin I_0$ に反します。

∎

重みが非負で独立集合全体の最大重みを求めるときも、最大重みの独立集合は基に拡張しても重みが減らないので、同じ結果です。最小の重みの基を求めたいときは、$w$ を $-w$ に替える、すなわち軽い順に並べればよいのです。

系 8.6（Kruskal のアルゴリズム）✓

連結グラフ $G=(V,E)$ と辺の重み $w:E\to\mathbb{R}$ が与えられたとき、辺を軽い順に並べ、閉路ができない限り順に採用していくと、重みの和が最小の全域木が得られる。

証明（系 8.6）

命題 8.4 により $(E,\text{森})$ はマトロイドで、基は全域木です。重み $-w$ に 定理 8.5 を使います。$-w$ の大きい順は $w$ の小さい順で、「$I\cup\{e\}\in\mathcal{I}$」は「閉路ができない」です。出力は $-w$ の和が最大の基、すなわち $w$ の和が最小の全域木です。

∎

例 8.7（4 頂点の最小全域木）

頂点 $a,b,c,d$、辺 $ab=1$、$bc=2$、$ac=3$、$cd=4$、$bd=5$（辺の重み）とします。軽い順に $ab$（採用）、$bc$（採用）、$ac$（$a,b,c$ に閉路ができるので不採用）、$cd$（採用）、$bd$（$b,c,d$ に閉路で不採用）となり、全域木 $\{ab,bc,cd\}$、重み $7$ です。このグラフは $K_4$ から辺 $ad$ を除いたもので、全域木は 8 個です（演習 10.1 と同じ計算）。たとえば $\{ab,ac,cd\}$ は重み $8$、$\{ab,bd,cd\}$ は $10$ で、他の全域木も重みはすべて $7$ 以上です。

逆に、すべての重みで貪欲法が最適になる独立集合の族はマトロイドに限る、という定理もあります（Rado と Edmonds）。貪欲法が通用する場面を過不足なく特徴づけるのがマトロイドの意義です。

9. 組合せゲーム：Nim と Sprague–Grundy の定理

有向グラフの上のゲームを調べます。2 人のプレイヤーが交互に、有向辺に沿って駒を動かし、動かせなくなったほうが負けとします。駒を動かすかわりに石を取るゲームもすべてこの形に書けます。

定義 9.1（公平ゲームと P・N 位置）↗

有限の公平ゲームとは、有限の有向非巡回グラフ $(V,\to)$（頂点を局面、$u\to v$ を $u$ から $v$ への手という）で、手番のプレイヤーは現在の局面 $u$ から手 $u\to v$ を 1 つ選んで局面を $v$ に動かし、手がないときは負けとするものをいう。局面 $u$ から出発する最長の道の長さ（辺の数）を $h(u)$ と書く（非巡回で有限なので有限）。$h$ についての再帰で、局面を次のように P 位置と N 位置に分ける：手がない局面と、すべての手が N 位置に向かう局面は P 位置、ある手が P 位置に向かう局面は N 位置。

命題 9.2（P 位置・N 位置と必勝法）✓

各局面はちょうど一方であり、P 位置では手番のプレイヤーは相手が最善を尽くすと負け、N 位置では手番のプレイヤーに勝つ戦略がある。

証明（命題 9.2）

$h(u)$ についての帰納法です。$h(u)=0$ なら手がなく P 位置で、手番のプレイヤーは負けです。$h(u)>0$ のとき、手 $u\to v$ では $h(v)<h(u)$ なので、$v$ は帰納法の仮定から P か N のいずれか一方に分類され、$u$ の分類は定義で一意に決まります。$u$ が N 位置なら、P 位置 $v$ に動かせば、帰納法の仮定により $v$ では手番の相手が負けです。$u$ が P 位置なら、どの手も N 位置 $v$ に動くので、相手は勝つ戦略をもちます。

∎

定義 9.3（mex と Grundy 値）↗

非負整数の有限集合 $S$ に対し $\mathrm{mex}(S)$ を、$S$ に含まれない最小の非負整数とする。局面 $u$ の Grundy 値を $h(u)$ についての再帰で $g(u)=\mathrm{mex}\{g(v):u\to v\}$ と定める（手がなければ $g(u)=\mathrm{mex}\,\varnothing=0$）。

命題 9.4（Grundy 値 0 は P 位置）✓

局面 $u$ について、$g(u)=0$ であることと $u$ が P 位置であることは同値である。

証明（命題 9.4）

$h(u)$ についての帰納法です。$g(u)=0$ は、$0$ が $\{g(v)\}$ に含まれない、すなわちすべての手の先 $v$ で $g(v)\ne0$ ということで、帰納法の仮定により「すべての手の先が N 位置」です。これは P 位置の定義です（手がない場合も含む）。

∎

二つのゲームを同時に進め、各手番では一方のゲームでだけ手を指す、というゲームの和を考えます。

定義 9.5（ゲームの和・Nim）↗

二つの有限の公平ゲーム $G=(V_G,\to)$、$H=(V_H,\to)$ の和 $G+H$ とは、局面の集合 $V_G\times V_H$、手 $(u,v)\to(u',v)$（$u\to u'$ のとき）と $(u,v)\to(u,v')$（$v\to v'$ のとき）のゲームである（有限非巡回）。石山 $*n$ ($n\ge0$) は局面 $\{0,1,\dots,n\}$、手 $m\to m'$（$m'<m$）のゲームで、$k$ 個の石山 $*n_1+\cdots+*n_k$ を Nim という（各手番に 1 つの山から好きな個数（1 個以上）を取る）。

定理 9.6（Sprague–Grundy の定理（和の Grundy 値））✓

有限の公平ゲーム $G,H$ の和 $G+H$ の局面 $(u,v)$ の Grundy 値は、$g(u,v)=g(u)\oplus g(v)$（ビットごとの排他的論理和、ニム和）である。

証明（定理 9.6）

$h(u)+h(v)$（和の最長の道の長さ）についての帰納法で示します。$a=g(u)$、$b=g(v)$、$c=a\oplus b$ とします。$g(u,v)=\mathrm{mex}$（後続局面の Grundy 値の集合）$=c$ を、次の 2 点で示します。

(i) 後続局面の Grundy 値は $c$ ではない：$(u',v)$（$u\to u'$）の値は帰納法の仮定から $g(u')\oplus b$ で、$g(u')\ne a$（mex の定義）なので $g(u')\oplus b\ne a\oplus b=c$ です。$(u,v')$ も同様です。

(ii) $0\le t<c$ なら、Grundy 値が $t$ の後続局面がある：$d=t\oplus c\ne0$ とし、$d$ の最上位のビットの位置を $p$ とします。$p$ より上のビットでは $t$ と $c$ が一致し、$p$ では異なります。$t<c$ なので $c$ の第 $p$ ビットは $1$（$t$ は $0$）です。$c=a\oplus b$ の第 $p$ ビットが $1$ なので、$a,b$ の一方だけがその第 $p$ ビットを $1$ にもちます。$a$ がそうだとします（$b$ の場合は対称）。$a'=a\oplus d$ は、第 $p$ ビットより上は $a$ と同じで、第 $p$ ビットが $1$ から $0$ になるので $a'<a$ です。$a=\mathrm{mex}\{g(u'):u\to u'\}$ ですから $g(u')=a'$ となる $u'$ があり、$(u',v)$ の Grundy 値は $a'\oplus b=a\oplus b\oplus d=c\oplus d=t$ です。

(i)(ii) から、後続局面の Grundy 値の集合は $\{0,\dots,c-1\}$ を含み、$c$ を含まないので、mex は $c$ です。

∎

系 9.7（Nim の必勝法（Bouton の定理））✓

Nim の局面 $(n_1,\dots,n_k)$ は、ニム和 $n_1\oplus\cdots\oplus n_k$ が $0$ であるときに限り P 位置である。ニム和 $s\ne0$ のとき、$n_i\oplus s<n_i$ となる山 $i$ が存在し、$n_i$ を $n_i\oplus s$ に減らす手は P 位置に向かう。

証明（系 9.7）

$*n$ の Grundy 値は、後続が $0,1,\dots,n-1$ で、それらの Grundy 値が帰納的に同じ数なので、$\mathrm{mex}\{0,\dots,n-1\}=n$ です。定理 9.6 を繰り返し使うと、$k$ 山の Nim の Grundy 値は $n_1\oplus\cdots\oplus n_k$ で、命題 9.4 から前半が従います。$s\ne0$ とし、$s$ の最上位ビットの位置を $p$ とします。ニム和の第 $p$ ビットは $1$ なので、第 $p$ ビットが $1$ の山 $n_i$ がある。$n_i\oplus s$ は第 $p$ ビットより上は $n_i$ と同じで第 $p$ ビットが $0$ なので $n_i\oplus s<n_i$ で、その山を $n_i\oplus s$ に減らすと全体のニム和は $s\oplus s=0$ になり、P 位置です。

∎

例 9.8（山が 3, 4, 5 の Nim）

$3\oplus4\oplus5=011_2\oplus100_2\oplus101_2=010_2=2\ne0$ なので、手番のプレイヤーが勝ちます。$s=2$ で、$3\oplus2=1<3$ なので山 $3$ を $1$ に減らすと $(1,4,5)$、$1\oplus4\oplus5=0$ で P 位置です。

例 9.9（石取りゲーム（1 回に 1〜3 個））

$1$ つの山から 1 回に $1,2,3$ 個を取れるゲームの局面 $n$（残りの石の数）の Grundy 値は $g(n)=n\bmod4$ です。$n\le3$ では後続が $0,\dots,n-1$ なので mex は $n$ です。$n\ge4$ では後続 $n-1,n-2,n-3$ の Grundy 値は（帰納法の仮定で）$n\bmod4$ 以外の 3 つの剰余すべてで、mex は $n\bmod4$ です。したがって P 位置は $n\equiv0\pmod 4$ で、1 つの山では相手に残す数を 4 の倍数にすれば勝てます。2 つの山では 定理 9.6 により $(n_1\bmod4)\oplus(n_2\bmod4)=0$、すなわち $n_1\equiv n_2\pmod 4$ のときに限り P 位置です。

10. 演習

演習 10.1易

$K_4$ から辺を 1 本除いたグラフの全域木の個数を、行列木定理で求めよ。

解答

頂点 $1,2,3,4$ とし、辺 $34$ を除きます。次数は $3,3,2,2$ で

$$L=\begin{pmatrix}3&-1&-1&-1\\-1&3&-1&-1\\-1&-1&2&0\\-1&-1&0&2\end{pmatrix},\qquad \det L^{(1)}=\det\begin{pmatrix}3&-1&-1\\-1&2&0\\-1&0&2\end{pmatrix}=3\cdot4-(-1)(-2)+(-1)\cdot2=8 .$$

検算として、$K_4$ の全域木 $16$ 個（Cayley）のうち、各木は 3 本の辺をもち、対称性から各辺は $16\cdot3/6=8$ 個の木に含まれるので、辺 $34$ を含まない木は $16-8=8$ 個です。

演習 10.2標準

図の $2\times3$ 格子の向き（横の辺は右向き、縦の辺は $1\to4$、$5\to2$、$3\to6$）について、完全マッチング 3 個それぞれの $t_K(M)$ を計算し、$\operatorname{Pf}(K)=3$ を確かめよ。

解答

$K_{12}=K_{23}=K_{45}=K_{56}=K_{14}=K_{36}=1$、$K_{25}=-1$ です。

• $M=\{14,25,36\}$：語 $142536$ の転倒は $(4,2),(4,3),(5,3)$ の 3 個で符号 $-1$、積 $K_{14}K_{25}K_{36}=-1$、よって $t_K=+1$。
• $M=\{12,45,36\}$：語 $124536$ の転倒は $(4,3),(5,3)$ で符号 $+1$、積 $1$、$t_K=+1$。
• $M=\{14,23,56\}$：語 $142356$ の転倒は $(4,2),(4,3)$ で符号 $+1$、積 $1$、$t_K=+1$。

符号がそろい、$\operatorname{Pf}(K)=3$ です。中央の縦の辺を上向き（$K_{25}=1$）にすると左の面の時計回りの辺が 2 本になり、第 1 項が $-1$ に変わって $\operatorname{Pf}=1$ となります。

演習 10.3標準

定理 5.1 を使って $\det\bigl[1/(i+j)\bigr]_{i,j=1}^3$ を求めよ。

解答

$x=y=(1,2,3)$ とします。分子は $\prod_{i\lt j}(j-i)^2=(1\cdot2\cdot1)^2=4$、分母は $\prod_{i,j}(i+j)=(2\cdot3\cdot4)(3\cdot4\cdot5)(4\cdot5\cdot6)=24\cdot60\cdot120=172800$ なので、行列式は $4/172800=1/43200$ です。

演習 10.4難

$K_4$ について Ihara–Bass の公式で $\det(I-u\mathcal B)$ を因数分解し、$N_1=N_2=0$、$N_3=24$ を確かめよ。$N_3$ を直接数えた値とも比べよ。

解答

$n=4$、$m=6$、$D=3I$ で、$A=J-I$ の固有値は $3$（1 重）と $-1$（3 重）です。定理 6.3 から

$$\det(I-u\mathcal B)=(1-u^2)^2(1-3u+2u^2)(1+u+2u^2)^3=(1-u^2)^2(1-u)(1-2u)(1-\alpha u)^3(1-\beta u)^3,$$

ここで $\alpha+\beta=-1$、$\alpha\beta=2$ です。命題 6.2 から $\sum_kN_ku^k/k=-\log\det(I-u\mathcal B)$ です。$-\log(1-cu)=\sum_kc^ku^k/k$ は $N_k$ に $c^k$ を加え、$-2\log(1-u^2)=\sum_r2u^{2r}/r=\sum_r4u^{2r}/(2r)$ は偶数の $k$ の $N_k$ に $4$ を加えるので

$$N_k=1+2^k+3(\alpha^k+\beta^k)+4\,[k\text{ は偶数}] .$$

$\alpha^2+\beta^2=(\alpha+\beta)^2-2\alpha\beta=-3$、$\alpha^3+\beta^3=(\alpha+\beta)^3-3\alpha\beta(\alpha+\beta)=5$ から

$$N_1=1+2-3=0,\qquad N_2=1+4-9+4=0,\qquad N_3=1+8+15=24 .$$

直接数えると、長さ 3 の非後退閉歩道は三角形を一周するものだけで、$K_4$ の三角形 4 個それぞれに基点 3 通り・向き 2 通りがあるので $4\cdot3\cdot2=24$ で一致します。長さ 1 の閉歩道にはループが、長さ 2 の非後退閉歩道には同じ 2 頂点を結ぶ別の辺が必要なので、$N_1=N_2=0$ も直接確かめられます。

演習 10.5標準

$E=\{1,2,3\}$、$\mathcal{I}=\{\varnothing,\{1\},\{2\},\{3\},\{2,3\}\}$ はマトロイドでないことを示し、重み $w(1)=3$、$w(2)=w(3)=2$ で貪欲法が最大重みの独立集合を与えないことを確かめよ。

解答

$I=\{1\}$、$J=\{2,3\}$ は $|I|<|J|$ ですが、$I\cup\{2\}=\{1,2\}$ も $I\cup\{3\}=\{1,3\}$ も $\mathcal{I}$ に属さないので (I3) が成り立ちません。貪欲法は重み順に $1$（採用）、次に $2$ を足そうとして $\{1,2\}\notin\mathcal{I}$、$3$ も同様に不採用で、$G=\{1\}$、重み $3$ です。一方 $\{2,3\}\in\mathcal{I}$ の重みは $4$ で、貪欲法は最適ではありません。定理 8.5 の証明の (I3) の使用箇所（$I_0\cup\{b_j\}$ を作る箇所）が、まさにここで壊れます。

演習 10.6易

山が $7,9,12$ の Nim で、手番のプレイヤーの必勝手を 1 つ求めよ。

解答

$7\oplus9=0111_2\oplus1001_2=1110_2=14$、$14\oplus12=1110_2\oplus1100_2=0010_2=2\ne0$ なので N 位置です。$s=2$ について、$7\oplus2=5<7$ なので山 $7$ を $5$ 個に減らす（2 個取る）と、$5\oplus9\oplus12=0101_2\oplus1001_2\oplus1100_2=0$ で P 位置です（系 9.7）。山 $9$ と $12$ は $9\oplus2=11>9$、$12\oplus2=14>12$ で減らす手になりません。

演習 10.7標準

1 つの山から 1 回に $1$ 個または $2$ 個を取れるゲームの局面 $n$ の Grundy 値を求め、山が $(5,7)$ の 2 山のときにどちらが勝つかを決めよ。

解答

$g(0)=0$、$g(1)=\mathrm{mex}\{g(0)\}=1$、$g(2)=\mathrm{mex}\{g(1),g(0)\}=2$、$g(3)=\mathrm{mex}\{g(2),g(1)\}=0$、$g(4)=\mathrm{mex}\{g(3),g(2)\}=\mathrm{mex}\{0,2\}=1$、以下周期 $3$ で $g(n)=n\bmod3$ です（$n\ge3$ で後続の値は $n\bmod 3$ 以外の 2 つの剰余で、mex は $n\bmod3$）。$(5,7)$ では $g=(5\bmod3)\oplus(7\bmod3)=2\oplus1=3\ne0$ なので、定理 9.6 と 命題 9.4 により N 位置で、手番のプレイヤー（先手）が勝ちます。たとえば山 $5$ から 1 個取って $(4,7)$、$g=1\oplus1=0$ にします。

参考文献

• R. P. Stanley, Algebraic Combinatorics: Walks, Trees, Tableaux, and More, Springer, 2013 — 第 9 章（行列木定理）。
• J. G. Oxley, Matroid Theory, 2nd edition, Oxford University Press, 2011 — 第 1 章（マトロイドの定義）。
• E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, 2nd edition, A K Peters, 2001 — Nim と Sprague–Grundy の理論。
• C. L. Bouton, “Nim, a game with a complete mathematical theory”, Annals of Mathematics 3 (1901–02), 35–39.
• P. W. Kasteleyn, “The statistics of dimers on a lattice I. The number of dimer arrangements on a quadratic lattice”, Physica 27 (1961), 1209–1225.
• A. Terras, Zeta Functions of Graphs: A Stroll through the Garden, Cambridge University Press, 2011 — Ihara ゼータ関数と Ihara–Bass の公式。
• M. Kac, J. C. Ward, “A combinatorial solution of the two-dimensional Ising model”, Physical Review 88 (1952), 1332–1337.
• H. Whitney, “On regular closed curves in the plane”, Compositio Mathematica 4 (1937), 276–284 — 回転数と交差の関係。
• M. Lis, “A short proof of the Kac–Ward formula”, Annales de l’Institut Henri Poincaré D 3 (2016).
• D. Cimasoni, “A generalized Kac–Ward formula”, Journal of Statistical Mechanics (2010).