5.18. ラプラシアンの左零空間について

目次

有向グラフのラプラシアンに関する結果をもう一つ紹介する。この結果を使うと、読者も抱いたはずの自然な疑問に答えられる。有向グラフ \(D\) のラプラシアン \(L\) は \(e= \left(1,1,\ldots,1\right)^{T} \) に対して常に \(Le=0\) を満たすと以前に示した。よって、このベクトル \(e\) は \(L\) の右零空間 (右核) に属する。容易に分かるように、もし \(D\) が終根を持つ (そして票数 \(0\) の体を考えている) なら、\(e\) は \(L\) の右零空間を張る ── つまり、\(e\) の定数倍でないベクトルは \(L\) の右零空間に属さない (実は、この逆も成り立つ)。\(L\) の左零空間についてはどうだろうか？ \(fL=0\) を満たす \(0\) でないベクトル \(f\) は存在するだろうか？ この質問の答えは「存在する」である:

定理 5.18.1

[ラプラシアンに対する調和ベクトル定理 (harmonic vector theorem for Laplacians)] \(D=\left( V,A,\psi\right) \) を多重有向グラフとする。ある \(n \in \mathbb{N}\) で \(V=\left\{ 1,2,\ldots,n\right\} \) だと仮定する。

任意の \(r \in V\) に対して、\(r\) を終根とする \(D\) の全域有向木の個数を \(\tau\left( D,r\right) \) と表す。

\(f\) を行ベクトル \(\left( \tau\left( D,1\right) ,\ \tau\left( D,2\right) ,\ \ldots,\ \tau\left( D,n\right) \right) \) とする。このとき \(fL=0\) が成り立つ。

定理 5.18.1 (正確には、次節で見る重み付きバージョン) は Markov 連鎖の定常状態を陽に計算するために利用される (参考: [KrGrWi10])。[Sahi14, § 1] では経済学の用語を使った同様の解釈 (物々交換経済における通貨の発生) が説明されている。

これから定理 5.18.1 を二つの補題を通して証明する。一つ目の補題は線形代数に関する一般的な結果である:

補題 5.18.2

任意の可換環 \(\mathbb{K}\) 上の \(n \times n\) 行列を \(B\) とする。 [例えば \(\mathbb{R}\) は \(\mathbb{K}\) になれる。そのとき \(B\) は実数行列となる。] \(B\) の列を全て足すと零ベクトルになると仮定する。このとき、任意の \(r,s,t\in\left\{ 1,2,\ldots,n\right\} \) に対して次の等式が成り立つ:

\[ \det\left( B_{\sim r,\sim t}\right) =\left( -1\right) ^{s-t}\det\left( B_{\sim r,\sim s}\right) \]

[証明] この補題には様々な証明が知られている。おそらく最もエレガントな証明を次に示す:

\(s = t\) なら補題は明らかなので、一般性を失うことなく \(s \neq t\) と仮定する。行列 \(B\) の第 \(r\) 行を次のように変更した行列を考える:

こうして得られる \(n\times n\) 行列を \(C\) とする1。第 \(r\) 行を除けば \(C\) と \(B\) は一致するから、次の等式が成り立つ:

\[ C_{\sim r,\sim k}=B_{\sim r,\sim k} \quad (\forall k \in\left\{ 1,2,\ldots,n\right\}) \qquad (7) \]

また、\(C\) の第 \(r\) 行の非零要素は \(C_{r,s}=1\) と \(C_{r,t}=-1\) だけ2なので、\(C\) の第 \(r\) 行の和は \(0\) である。

補題の仮定より行列 \(B\) の列を全て足すと零ベクトルとなる。言い換えれば、\(B\) の任意の行は和が \(0\) である。よって行列 \(C\) も同じ性質を持つ。 [\(C\) と \(B\) は第 \(r\) 行を除けば等しく、\(C\) の第 \(r\) 行の和が \(0\) であることは前段落で示した。] つまり、\(C\) の列を全て足すと零ベクトルになる。これが \(\det C=0\) を意味することは容易に分かる3。

一方、第 \(r\) 行に関するラプラス展開 (余因子展開) からは次の等式が分かる:

\[ \begin{aligned} \det C & =\sum_{k=1}^{n}\left( -1\right) ^{r+k}C_{r,k}\det\left( C_{\sim r,\sim k}\right) \\ & =\left( -1\right) ^{r+s}1\det\left( C_{\sim r,\sim s}\right) +\left( -1\right) ^{r+t}\left( -1\right) \det\left( C_{\sim r,\sim t}\right) \end{aligned} \]

[\(C\) の第 \(r\) 行の非零要素は \(C_{r,s}=1\) と \(C_{r,t}=-1\) だけであるため。] この等式を \(\det C=0\) と比較すると次を得る:

\[ \begin{aligned} 0 & =\left( -1\right) ^{r+s}1\det\left( C_{\sim r,\sim s}\right) +\left( -1\right) ^{r+t}\left( -1\right) \det\left( C_{\sim r,\sim t}\right) \\ & =\left( -1\right) ^{r+s}\det\underbrace{\left( C_{\sim r,\sim s}\right) }_{\substack{=B_{\sim r,\sim s}\\\text{(式 (7) より)}}}-\left( -1\right) ^{r+t}\det\underbrace{\left( C_{\sim r,\sim t}\right) }_{\substack{=B_{\sim r,\sim t}\\\text{(式 (7) より)}}}\\ & =\left( -1\right) ^{r+s}\det\left( B_{\sim r,\sim s}\right) -\left( -1\right) ^{r+t}\det\left( B_{\sim r,\sim t}\right) \end{aligned} \]

つまり \(\left( -1\right) ^{r+t}\det\left( B_{\sim r,\sim t}\right) =\left( -1\right) ^{r+s}\det\left( B_{\sim r,\sim s}\right) \) が成り立つ。両辺を \(\left( -1\right) ^{r+t}\) で割れば \(\det\left( B_{\sim r,\sim t}\right) =\left( -1\right) ^{s-t}\det\left( B_{\sim r,\sim s}\right) \) を得る。以上で補題 5.18.2 は証明された。□

二つ目の補題は行列木定理 (定理 5.14.7) の一般化である:

定理 5.18.3

[行列木定理の非対角バージョン] \(D=\left( V,A,\psi\right) \) を多重有向グラフとする。ある \(n \in \mathbb{N}\) で \(V=\left\{ 1,2,\ldots,n\right\} \) だと仮定する。

\(L\) を \(D\) のラプラシアン、\(r\), \(s\) を \(D\) の頂点とする。このとき次の等式が成り立つ:

\[ \left(\text{\# } r \text{ を終根とする } D \text{ の全域有向木} \right) =\left( -1\right) ^{r+s}\det\left( L_{\sim r,\sim s}\right) \]

定理 5.14.7 は 定理 5.18.3 で \(s=r\) とした特殊ケースである。幸い、この一般的な命題は補題 5.18.2 を使えば特殊ケースから簡単に示せる。

[補題 5.18.3 の証明] ラプラシアン \(L\) の列の和が零ベクトルであることは以前に (命題 5.14.6 の証明で) 見た。よって補題 5.18.2 を \(B=L\), \(t=r\) として適用すれば次の等式を得る:

\[ \det\left( L_{\sim r,\sim r}\right) =\underbrace{\left( -1\right) ^{s-r}}_{=\left( -1\right) ^{r+s}}\det\left( L_{\sim r,\sim s}\right) =\left(-1\right) ^{r+s}\det\left( L_{\sim r,\sim s}\right) \]

よって行列木定理 (定理 5.14.7) から次の等式を得る:

\[ \begin{aligned} \left(\text{\# } r \text{ を終根とする } D \text{ の全域有向木} \right) & =\det\left( L_{\sim r,\sim r}\right) \\ & =\left( -1\right) ^{r+s}\det\left( L_{\sim r,\sim s}\right) \end{aligned} \]

以上で定理 5.18.3 は証明された。□

これで定理 5.18.1 を証明する準備が整った:

[定理 5.18.1 の証明] 定理 5.18.3より、任意の \(r,s\in\left\{ 1,2,\ldots ,n\right\} \) に対して次の等式が成り立つ:

\[ \begin{aligned} \tau\left( D,r\right) & =\left(\text{\# } r \text{ を終根とする } D \text{ の全域有向木}\right) \\ & \qquad \qquad \left(\because\ \tau\left( D,r\right) \text{ の定義} \right)\\ & =\left( -1\right) ^{r+s}\det\left( L_{\sim r,\sim s}\right) \qquad (8) \end{aligned} \]

一方、定理の設定より \(f=\left( \tau\left( D,1\right) ,\tau\left( D,2\right) ,\ldots,\tau\left( D,n\right) \right) \) だから、任意の \(s\in\left\{ 1,2,\ldots,n\right\} \) に対して列ベクトル \(fL\) の第 \(s\) 要素は次のように変形できる4:

\[ \begin{aligned} & \sum_{r=1}^{n}\underbrace{\tau\left( D,r\right) }_{\substack{=\left( -1\right) ^{r+s}\det\left( L_{\sim r,\sim s}\right) \\\text{(} \text{式 } (8) \text{ より)}}}L_{r,s}\\ & \quad =\sum_{r=1}^{n}\left( -1\right) ^{r+s}\det\left( L_{\sim r,\sim s}\right) L_{r,s}\\ & \quad =\sum_{r=1}^{n}\left( -1\right) ^{r+s}L_{r,s}\det\left( L_{\sim r,\sim s}\right) =\det L\\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( \text{第 } s \text{ 列に沿った } L \text{ のラプラス展開より} \right) \\ & \quad =0 \end{aligned} \]

[最後の変形では命題 5.14.6 を使った。] つまり \(fL\) の全ての要素は \(0\) に等しい。言い換えれば \(fL=0\) である。以上で定理 5.18.1 は証明された。□

定理 5.18.1 には別証明も知られている。例えば、[Sahi14, Theorem 1] では組合せ論的な証明の概略が示されている5 (正確には、弧の向きを反転させて行列を転置したバージョンの定理 5.18.1 が [Sahi14, Theorem 1] である)。

  1. 例えば \(n=4\), \(\ B=\left(\begin{array}{cccc}a & b & c & d\\ a^{\prime} & b^{\prime} & c^{\prime} & d^{\prime}\\ a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime} & d^{\prime\prime}\\ a^{\prime\prime\prime} & b^{\prime\prime\prime} & c^{\prime\prime\prime} & d^{\prime\prime\prime} \end{array} \right)\), \(\ s=1\), \(\ t=3\), \(\ r=2\) なら

    \[ C=\left( \begin{array}{cccc}a & b & c & d\\ 1 & 0 & -1 & 0\\ a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime} & d^{\prime\prime}\\ a^{\prime\prime\prime} & b^{\prime\prime\prime} & c^{\prime\prime\prime} & d^{\prime\prime\prime} \end{array}\right) \]

    となる。 ↩︎

  2. \(C\) の \(r\) 行 \(k\) 列成分を \(C_{r,k}\) と表記している。 ↩︎

  3. 証明: よく知られているように、行列の任意の列を他の列に加えても行列式は変化しない。よって \(C\) の行列式は \(C\) の第 \(1\) 列を除いた各列を第 \(1\) 列に足しても変化しない。\(C\) の各列の和が零ベクトルなので、この操作で得られる行列は第 \(1\) 列が零ベクトルであり、その行列式は \(0\) と分かる。この操作は行列式を変化させないので、\(C\) の行列式も \(0\) である。以上で \(\det C = 0\) は証明された。 ↩︎

  4. \(L\) の \(r\) 行 \(s\) 列成分を \(L_{r,s}\) と表記している。 ↩︎

  5. 私は Spring 2018 Math 4707 midterm #3 への解答で、この証明の詳細な説明を試みた ── この PDF の Theorem 0.7 の証明がそうである。私の説明が分かりやすいかどうかの判断は読者に任せる。 ↩︎

広告
このページの文章はテキストゆれないくんを使って校正されました。