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

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

定理 5.18.1

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

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

$f$ を行ベクトル $(τ (D, 1), τ (D, 2), \dots, τ (D, n))$ とする。このとき $f L = 0$ が成り立つ。

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

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

補題 5.18.2

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

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

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

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

第 $r$ 行の第 $s$ 要素を $1$ とする。
第 $r$ 行の第 $t$ 要素を $- 1$ とする。
それ以外の第 $r$ 行の要素は $0$ とする。

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

C_{\sim r, \sim k} = B_{\sim r, \sim k} (\forall k \in {1, 2, \dots, n}) (7)

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

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

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

det C = k = 1 \sum n (- 1)^{r + k} C_{r, k} det (C_{\sim r, \sim k}) = (- 1)^{r + s} 1 det (C_{\sim r, \sim s}) + (- 1)^{r + t} (- 1) det (C_{\sim r, \sim t})

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

0 = (- 1)^{r + s} 1 det (C_{\sim r, \sim s}) + (- 1)^{r + t} (- 1) det (C_{\sim r, \sim t}) = (- 1)^{r + s} det = B_{\sim r, \sim s} (式 (7) より) (C_{\sim r, \sim s}) - (- 1)^{r + t} det = B_{\sim r, \sim t} (式 (7) より) (C_{\sim r, \sim t}) = (- 1)^{r + s} det (B_{\sim r, \sim s}) - (- 1)^{r + t} det (B_{\sim r, \sim t})

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

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

定理 5.18.3

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

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

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

定理 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 (L_{\sim r, \sim r}) = = (- 1)^{r + s} (- 1)^{s - r} det (L_{\sim r, \sim s}) = (- 1)^{r + s} det (L_{\sim r, \sim s})

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

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

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

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

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

τ (D, r) = (# r を終根とする D の全域有向木) (∵ τ (D, r) の定義) = (- 1)^{r + s} det (L_{\sim r, \sim s}) (8)

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

r = 1 \sum n = (- 1)^{r + s} d e t (L_{\sim r, \sim s}) (式 (8) より) τ (D, r) L_{r, s} = r = 1 \sum n (- 1)^{r + s} det (L_{\sim r, \sim s}) L_{r, s} = r = 1 \sum n (- 1)^{r + s} L_{r, s} det (L_{\sim r, \sim s}) = det L (第 s 列に沿った L のラプラス展開より) = 0

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

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

例えば $n = 4$ , $B = a a^{'} a^{''} a^{'''} b b^{'} b^{''} b^{'''} c c^{'} c^{''} c^{'''} d d^{'} d^{''} d^{'''}$ , $s = 1$ , $t = 3$ , $r = 2$ なら

$C = a 1 a^{''} a^{'''} b 0 b^{''} b^{'''} c - 1 c^{''} c^{'''} d 0 d^{''} d^{'''}$

となる。 ↩︎
$C$ の $r$ 行 $k$ 列成分を $C_{r, k}$ と表記している。 ↩︎
証明: よく知られているように、行列の任意の列を他の列に加えても行列式は変化しない。よって $C$ の行列式は $C$ の第 $1$ 列を除いた各列を第 $1$ 列に足しても変化しない。 $C$ の各列の和が零ベクトルなので、この操作で得られる行列は第 $1$ 列が零ベクトルであり、その行列式は $0$ と分かる。この操作は行列式を変化させないので、 $C$ の行列式も $0$ である。以上で $det C = 0$ は証明された。 ↩︎
$L$ の $r$ 行 $s$ 列成分を $L_{r, s}$ と表記している。 ↩︎
私は Spring 2018 Math 4707 midterm #3 への解答で、この証明の詳細な説明を試みた ── この PDF の Theorem 0.7 の証明がそうである。私の説明が分かりやすいかどうかの判断は読者に任せる。 ↩︎