行列式がパフィアンの二乗に等しいことのグラフを用いた証明
はじめに
$2n$次の交代行列$A=(a_{ij})$に対して, $A$のパフィアン(Pfaffian)$\mathrm{Pf}(A)$とは以下で定義される値のことを指す:
$$\mathrm{Pf}(A)=\displaystyle\sum_\sigma{\mathop{\mathrm{sgn}}\nolimits}(\sigma)\prod_{i=1}^n a_{\sigma(2i-1)\sigma(2i)}$$
ここで$\sigma$は$1, 2, \cdots ,2n$の置換であって
$$\sigma(2i-1)<\sigma(2i)\quad (i=1, 2, \cdots ,n)$$
$$\sigma(1)<\sigma(3)<\cdots <\sigma(2n-1)$$
を満たすもの全体を動く.
$A$が$2\times 2$行列のとき$\mathrm{Pf}(A)=a_{12}$
$A$が$4\times 4$行列のとき$\mathrm{Pf}(A)=a_{12}a_{34}-a_{13}a_{24}+a_{14}a_{23}$
このとき以下の関係式が成立することが知られている.
$\det (A)=\big(\mathrm{Pf}(A)\big)^2$
以下この等式が成立することの証明をする.
証明
左辺について
まず左辺の$\det(A)$の意味付けをする. 各$\sigma\in S_{2n}$について, $1, 2, \cdots ,2n$を頂点とし$i \rightarrow \sigma(i)$の向きに有向辺を張った有向グラフを考える. なお, 以下グラフを考えるときはすべて$1, 2, \cdots ,2n$を頂点とするものを考える. 辺$i \rightarrow j$の重みを$a_{ij}$とし, 有向グラフ$G$の重み$w(G)$を$G$のすべての有向辺の重みの積として定義する. すると,
$$\det(A)= \sum_{\sigma\in S_{2n}}\mathrm{sgn}(\sigma) \prod_{i=1}^{2n}a_{i\sigma(i)} $$
は各$\sigma$に対応する有向グラフ$G$の重み$w(G)$と $\mathrm{sgn}(\sigma)$との積を$\sigma\in S_{2n}$すべてにわたって足し合わせたものと捉えられる. ここで各頂点についてその点から出る辺とその点に入る辺の本数はどちらも一本であるから, これらのグラフはいくつかのサイクルに分解できる. いま$A$は交代行列であり$a_{ij}=-a_{ji}$を満たすから, $G$のあるサイクルを逆向きに変えたグラフ$G'$について$w(G')$と$w(G)$は符号の差異をのぞけば等しい. よって, 有向グラフ$G, G'$が辺の向きを無視して無向グラフとして見たときに一致するとき$w(G)$と$w(G')$は符号の差異をのぞけば等しい.
各頂点の次数が$2$である無向グラフ$g$に対して, $g$の各サイクルに対する向き付けの方法$\sigma$全てにわたる$\mathrm{sgn(\sigma)}w(g_{\sigma})$の総和を$w(g)$で表す(ただし$g_{\sigma}$は$g$に$\sigma$に対応する向きをつけた有向グラフ). このとき
$$\det(A)= \displaystyle\sum_{g} w(g)$$
であることが従う(ただし$g$は各頂点の次数が$2$である無向グラフ全体を動く).
$g$が長さ奇数のサイクルを含むとき, $w(g)=0$
$g$が長さ$1$のサイクル(つまりループ)を含む場合は明らか($\because A$は交代行列より$a_{ii}=0$).
$g$が長さ$L$($L$は$3$以上の奇数)のサイクル$s$を含むとする. $g$に対する向き付け$\sigma$を一つとる. $s$のみ逆向きにし, 他のサイクルは$\sigma$と同じ向きにする向き付け方を$\sigma'$とする. このとき, $L$本の辺を逆向きにしたことから$w(g_{\sigma'})=(-1)^Lw(g_{\sigma})=-w(g_{\sigma})$. また, 一般に$\mathrm{sgn}(\tau)=\mathrm{sgn}(\tau^{-1})$が成り立つことを利用すれば, $\mathrm{sgn}(\sigma)=\mathrm{sgn}(\sigma')$が得られる(置換の逆元をとる操作が, 対応する有向グラフの辺をすべて逆向きに変える操作に相当することに注意する). 以上より$\mathrm{sgn}(\sigma')w(g_{\sigma'})=-\mathrm{sgn}(\sigma)w(g_\sigma)$であり, $w(g)=0$が導かれる.
補題$2$より, $g$として任意のサイクルの長さが偶数であるようなものだけを考えればよい. そのような$g$を一つとって固定する. 補題$2$の証明を応用すれば, $g$に対する任意の向き付け$\sigma$について$w(g_\sigma)$の符号が一致し, 故に$\mathrm{sgn}(\sigma)w(g_\sigma)$の符号が一致することが従う. また$g$の長さ$4$以上の各サイクルに対して向き付け方はそれぞれ$2$通りあるので, $g$の長さ$4$以上のサイクルの個数を$N$とおけば$w(g)=2^N\mathrm{sgn}(\sigma)w(g_\sigma)$. ただし$\sigma$は$g$に対する適当な向き付け方.
以下$\mathrm{sgn}(\sigma)$を計算するためにいくつかの補題を用意する.
巡回置換$\sigma=(i_1 ~i_2 ~\cdots ~i_m)$について, $\mathrm{sgn}(\sigma)=(-1)^{m-1}$
$\sigma=(i_1~i_m)(i_1~i_{m-1})\cdots(i_1~i_2)$より従う.
$\sigma \in S_n$が$q$個の巡回置換の積で書けるとき, $\mathrm{sgn}(\sigma)=(-1)^{n-q}$
各巡回置換の長さを$m_1, m_2, \cdots, m_q$とおく. 補題$3$より,
$$ \mathrm{sgn}(\sigma)=(-1)^{m_1-1}(-1)^{m_2-1}\cdots(-1)^{m_q-1}=(-1)^{n-q}.$$
補題$4$より, $g$のサイクルの個数を$q$とすれば
$$w(g)=2^N\mathrm{sgn}(\sigma)w(g_\sigma)=(-1)^{2n-q}2^Nw(g_\sigma)=(-1)^q2^Nw(g_\sigma).$$
右辺について
次に右辺の$\big(\mathrm{Pf}(A)\big)^2$の意味付けをする. 各$\sigma\in S_{2n}$について, $\sigma(2i-1) \rightarrow \sigma(2i)$の向きに有向辺を張った有向グラフを考える. その他の記号や重みについては上と同様とする. すると,
$$\mathrm{Pf}(A)=\displaystyle\sum_\sigma{\mathop{\mathrm{sgn}}\nolimits}(\sigma)\prod_{i=1}^n a_{\sigma(2i-1)\sigma(2i)} $$
は各$\sigma$に対応する有向グラフ$G$の重み$w(G)$と $\mathrm{sgn}(\sigma)$との積を$\sigma\in S_{2n}$すべてにわたって足し合わせたものと捉えられる. ここで, ある$k$について$\sigma'$を
$$ \sigma'(n)=
\begin{eqnarray}
\left\{
\begin{array}{l}
\sigma(n+1)\quad(n=2k-1) \\
\sigma(n-1)\quad(n=2k) \\
\sigma(n)\quad\quad~~~(otherwise)
\end{array}
\right.
\end{eqnarray}$$
で定めると,
$
\begin{align}
{\mathop{\mathrm{sgn}}\nolimits}(\sigma')\prod_{i=1}^n a_{\sigma'(2i-1)\sigma'(2i)}
&=-{\mathop{\mathrm{sgn}}\nolimits}(\sigma')\prod_{i=1}^n a_{\sigma(2i-1)\sigma(2i)} \\
&={\mathop{\mathrm{sgn}}\nolimits}(\sigma)\prod_{i=1}^n a_{\sigma(2i-1)\sigma(2i)}
\end{align}
$
であるから, 各辺の向きを逆にしてもグラフの重みは保たれる. また, 辺の向きを無視して無向グラフとして見たときにこのグラフは完全マッチングとなる. $\mathrm{Pf}(A)$の定義にある$\sigma$の条件より, 完全マッチングと条件を満たす$\sigma$が一対一に対応することがわかる. そして完全マッチングを二つ重ね合わせてできる無向グラフは, 各頂点の次数が$2$であり, かつ長さが奇数のサイクルを含まない.
ここで, 各頂点の次数が$2$で任意のサイクルの長さが偶数である無向グラフ$g$とその適当な向き付け$\sigma$に対して, $g$が二つの完全マッチング$(m_1, m_2)$の合併として得られるようなすべての$(m_1, m_2)$の組にわたる$\mathrm{sgn}(\sigma_1)\mathrm{sgn}(\sigma_2)w(g_\sigma)$の総和を$w'(g)$で表す. ただし$\sigma_1$は$m_1$に$\sigma$の向き付けをして得られる有向グラフに対応する置換であり, $\sigma_2$についても同様.
このとき,
$$\big(\mathrm{Pf}(A)\big)^2=\displaystyle\sum_{\sigma_1, \sigma_2}{\mathop{\mathrm{sgn}}\nolimits}(\sigma_1)\mathrm{sgn}(\sigma_2)\prod_{i=1}^n a_{\sigma_1(2i-1)\sigma_1(2i)}\prod_{i=1}^n a_{\sigma_2(2i-1)\sigma_2(2i)} $$
は$\displaystyle\sum_{g} w'(g)$に等しいことが従う(ただし$g$は各頂点の次数が$2$で任意のサイクルの長さが偶数である無向グラフ全体を動く). 以下このような$g$を一つとって固定する.
$g$のサイクルの個数を$q$としたとき
$$ \mathrm{sgn}(\sigma_1)\mathrm{sgn}(\sigma_2)=(-1)^q$$
$g_\sigma$の巡回置換$(i_1 ~i_2 ~\cdots ~i_{2m})$をとる. このサイクル内で, $\sigma_1$が$i_{2k-1} \rightarrow i_{2k}$に, $\sigma_2$が$i_{2k} \rightarrow i_{2k+1}$に対応しているとしてよい(添え字は適宜循環させて考える). $\sigma_2$に巡回置換$(i_{2m-1} ~i_{2m-3} ~\cdots ~i_{3} ~i_1)$を乗じると, 変換後の対応は$i_{2k} \rightarrow i_{2k-1}$になる. ここですべての辺の向きを逆転させる操作を行うことで, このサイクル内で$\sigma_2$を$\sigma_1$に変えることができる. 最初の変換により, 補題$3$から$\mathrm{sgn}(\sigma_2)$の値は$(-1)^{m-1}$倍され, 次の操作によりさらに$(-1)^m$倍される. つまり全体で$(-1)$倍される. すべてのサイクルでこの操作を行うことを考えると, $ \mathrm{sgn}(\sigma_1)=(-1)^q\mathrm{sgn}(\sigma_2)$が得られる. この式の両辺に$\mathrm{sgn}(\sigma_2)$を乗じれば求める結果が得られる.
$g$が二つの完全マッチング$(m_1, m_2)$の合併として得られるような$(m_1, m_2)$の組を数え上げる. $g$の長さ$4$以上の各サイクルに対して完全マッチングの組はそれぞれ$2$通りあるので, $g$の長さ$4$以上のサイクルの個数を$N$とおけば補題$5$とあわせて$w'(g)=(-1)^q2^Nw(g_\sigma)$.
以上より$w(g)=w'(g)$が条件を満たすすべての$g$について成立するので, $g$を動かしたときの総和を取れば$\det (A)=\big(\mathrm{Pf}(A)\big)^2$が従う.
おわりに
以前この等式を示した際に, 愚直に係数比較をして示す方針をとったら思いの外興味深い方法で示すことができて驚いたので記事にしてみた.
この記事を高評価した人
この記事に送られたバッジ
投稿者
