ケーリー・ハミルトンの定理の組合せ論的証明

１，概要

正方行列 $A$ の固有多項式 $p_A(\lambda)\triangleq\det(A-I\lambda)$ について， $p_A(A)=O$ が成り立つ．
これをCayley–Hamiltonの定理という．

Cayley–Hamiltonの定理は線形代数のクラスの後半で習うのが普通であるが，実は線形代数の知識を用いずに証明できる．
具体的には，置換を用いた行列式の定義と行列の $n$ 乗の定義から，組合せ論的考察により証明できる．

本記事で紹介する証明は，組合せ論的な視点から線形代数を再構成したBrualdi [1]の本からとったものである．

以下第2節ではまず準備として行列式や固有多項式を，組合せ論的オブジェクトの母関数として解釈する．
次に第3節で，行列の $n$ 乗とグラフ上の歩道の対応を復習する．
最後に第4節で，上の二つを組み合わせてCayley–Hamiltonの定理を証明する．

２，行列式のHarary-Coater流の定義

以下で述べるように，行列式はグラフのサイクルの母関数として解釈できる．
この考え方はBrualdi [1]の第4章に詳しく，行列式のHarary-Coater流の定義と呼ばれる．

グラフ理論の用語の定義

有向グラフ $G=(V,E)$ の部分グラフとは，節点集合 $V'\subseteq V$ と枝集合 $E'\subseteq E$ をもつ有向グラフ $(V',E')$ である．
部分グラフの節点集合がもとのグラフの節点集合に等しいとき，つまり $V'=V$ のとき，グラフ $(V,E')$ を全域部分グラフという．
以下では $\mathbb{K}$ はある体を表す。
有向グラフ $G=(V,E)$ の枝重みとは，関数 $w\colon E\to\mathbb{K}$ である．有向グラフと枝重みの組 $(G,w)$ のことを，重み付き有向グラフという．
重み付き有向グラフ $(G,w)$ の重み $w(G)$ を，グラフの枝重みの積 $w(G)\triangleq\prod_{e\in E}w(e)$ と定める．

有向グラフが2-正則であるとは，全ての節点の入次数と出次数が1であることである．
（これは一般的な言葉遣いとは違うかもしれない．）
2-正則であるような全域部分グラフのことを2-正則全域部分グラフという．
下図のように，2-正則全域部分グラフは有向グラフの全ての節点を，いくつかの交わりを持たないサイクルによって覆う方法であると思うこともできる．

$n$ 次正方行列 $A=(a_{i,j})$ に対応する有向グラフ $G(A)$ とは，
節点集合 $V\triangleq\{1,2,\ldots,n\}$ と，枝集合 $E\triangleq \{(i,j)\mid a_{i,j}\neq 0,\ i,j\in\{1,\ldots,n\}\}$ をもつ有向グラフ $G\triangleq (V,E)$ である．
有向グラフ $G(A)$ の枝重み $w\colon E\to\mathbb{K}$ を，枝 $(i,j)\in E$ に対して $w( (i,j) )\triangleq a_{i.j}$ と定める．

$n$ 次正方行列 $A$ に対し，有向グラフ $G(A)$ の2-正則全域部分グラフの集合を $\mathcal{L}(A)$ とかく．
グラフ $\gamma\in\mathcal{L}(A)$ に含まれるサイクルの数（連結成分の数と言い換えてもよい）を $c(\gamma)$ とかく．
下図はその例．

図中で枝重みを青色で書いている．

行列式のサイクル母関数としての表示

これらの用語を用いると，行列式は次のよう書ける．

定理1 (サイクルを用いた行列式の表示)
$n$ 次正方行列 $A$ の行列式 $\det A$ は，以下の和に等しい．
$\displaystyle\det A\triangleq\sum_{\gamma\in\mathcal{L}(A)}(-1)^{n-c(\gamma)}w(\gamma)$ .

証明の概略
行列式を置換を用いて定義し，置換のサイクル分解を考える．
（証明終わり）

これについては，例を見るとより納得できるだろう．
上の図で登場した行列

の行列式は
$\det A=a_{{1,1}}a_{{2,2}}a_{{3,3}}a_{{4,4}}-a_{{1,3}}a_{{2,1}}a_{{3,4}}a_{{4,2}}-a_{{1,2}}a_{{2,1}}a_{{3,3}}a_{{4, 4}}$
である．
これは以下の図に示すとおり， $\mathcal{L}(A)$ の各要素 $\gamma$ について，その重み $(-1)^{n-c(\gamma)}w(\gamma)$ を足し合わせたものにひとしい．

固有多項式と，2-正則部分グラフ

$n$ 次正方行列 $A$ に対し，有向グラフ $G(A)$ の (全域でなくてもよい)2-正則部分グラフの集合を $\mathcal{C}(A)$ とかく．
有向グラフ $G(A)$ の節点のうち，部分グラフ $\gamma\in\mathcal{C}(A)$ に含まれていないものの数を， ${\rm ip}(\gamma)$ とかく (isolated points，孤立点の意)．

すると以下が成り立つ．

定理2 (サイクルを用いた固有多項式の表示)
$n$ 次正方行列 $A$ に対し
$\displaystyle\det (A-\lambda I)=\sum_{\gamma\in\mathcal{C}(A)}(-1)^{n-c(\gamma)}w(\gamma)\lambda^{{\rm ip}(\gamma)}$
が成り立つ．

証明の概略
まず定理1を用いて行列式 $\det(A-\lambda I)$ を2-正則全域部分グラフの母関数として書く．
グラフ $\gamma\in\mathcal{L}(A-\lambda I)$ に自己ループがあるとき，その自己ループしている枝の重みは $a_{i,i}-\lambda$ であり，それを枝重み $a_{i,i}$ の自己ループとして残すか，重み $\lambda$ の孤立点として扱うかを選ぶことができる．
（証明終わり）

例として，以下の行列 $A$ を考える．

行列 $A$ の固有多項式は
$\det(A-\lambda I)=\lambda^2-\lambda(a_{1,1}+a_{2,2})+a_{1,1}a_{2,2}-a_{1,2}a_{2,1}$
である．
一方，グラフ $G(A)$ の2-正則部分グラフの重み和は下図の通り．

３，行列の $n$ 乗と，グラフ上の歩道の対応

グラフの隣接行列を $n$ 乗した行列の第 $(i,j)$ 成分は，グラフの節点 $i$ から節点 $j$ への長さ $n$ の歩道の母関数である．
これはグラフ理論やマルコフ連鎖の理論でよく使う事実であるから，知っている人も多いと思う．
本節ではこの事実を復習する．

枝重み付き有向グラフ $(V,E)$ の節点 $s$ から節点 $t$ への歩道とは，節点の列
$(s=v_0,v_1,v_2,\ldots,v_{n-1},v_n=t), \quad v_i\in V$
であって，隣り合う節点 $v_i$ ,から $v_{i+1}$ への枝がある，つまり
$(v_i,v_{i+1})\in E,\quad i\in\{0,1,\ldots, n-1\}$
なるものである．
歩道 $\mu=(v_0,v_1,\ldots,v_n)$ の重み $w(\mu)$ を，枝重みの積により
$w(\mu)\triangleq\prod_{i=0}^{n-1}w( (v_i,v_{i+1}) )$
と定める．
歩道 $\mu$ の長さ $|\mu|$ を，列 $\mu$ の要素数 $-1$ と定める．
節点 $s$ から節点 $t$ への歩道の集合を $s\rightsquigarrow t$ とかく．
すると以下が成り立つ．

定理3 (行列の $n$ 乗とグラフの歩道の関係)
$n$ 次正方行列 $A$ に対し $A^k$ の第 $(i,j),\ i,j\in\{1,\ldots,n\}$ 成分 $[A^k]_{i,j}$ は
$\displaystyle[A^k]_{i,j}=\sum_{\substack{\mu\colon i\rightsquigarrow j\\|\mu|=k}}w(\mu)$
と表せる．但し和は節点 $i$ から節点 $j$ への長さ $k$ の全ての歩道にわたってとる．

４，Cayley–Hamiltonの定理の組合せ論的証明

Cayley–Hamiltonの定理
$n$ 次正方行列 $A$ に対し $p_A(\lambda)\triangleq\det(A-\lambda I)$ と定めると，
$p_A(A)=O$ が成り立つ．

証明
まず定理2から，
$\displaystyle p_A(\lambda)=\sum_{\gamma\in\mathcal{C}(A)}(-1)^{n-c(\gamma)}w(\gamma)\lambda^{{\rm ip}(\gamma)}$
である．
次に $p_A(\lambda)$ に行列 $A$ を代入すると，
$\displaystyle p_A(A)=\sum_{\gamma\in\mathcal{C}(A)}(-1)^{n-c(\gamma)}w(\gamma)A^{{\rm ip}(\gamma)}$
となる．
定理3から，行列 $p_A(A)$ の第 $(i,j),\ i,j\in\{1,\ldots,n\}$ 成分 $[p_A(A)]_{i,j}$ は
$\displaystyle[p_A(A)]_{i,j}=\sum_{\gamma\in\mathcal{C}(A)}\sum_{\substack{\mu\colon i\rightsquigarrow j\\|\mu|={\rm ip}(\gamma)}}(-1)^{n-c(\gamma)}w(\gamma)w(\mu)$
である．

以下，やることは，対合を作って $[p_A(A)]_{i,j}=0$ を示すことである．

行列 $A$ と $1\leq i,j\leq n$ に対して，ケーリーハミルトン配置の集合 $\mathcal{K}(A;i,j)$ を以下のように定義する．
$\mathcal{K}(A;i,j)\triangleq \{(\gamma,\mu)\mid \gamma\in\mathcal{C}(A),\ \mu\colon i\rightsquigarrow j,\ |\mu|={\rm ip}(\gamma)\}$ .

以下はケーリーハミルトン配置の例である．

言葉でいうと，ケーリーハミルトン配置とは，グラフ $G(A)$ 上のいくつかのサイクル（上図赤色）と，節点 $i$ から $j$ への歩道（上図青色）の重ね合わせであって，歩道の長さがサイクルに含まれない $G(A)$ の節点の数（上図の例では４個）に等しいものである．

これを用いると，今考えている和はケーリーハミルトン配置にわたる和として
(★)　 $\displaystyle [p_A(A)]_{i,j}=\sum_{(\gamma,\mu)\in \mathcal{K}(A;i,j)}(-1)^{n-c(\gamma)}w(\gamma)w(\mu)$
とかける．

式（★）が0であることを示すには以下のような対合 $\psi$ を構成すればよい．

$\psi\colon \mathcal{K}(A;i,j)\ni (\gamma,\mu)\mapsto (\gamma',\mu')\ni\mathcal{K}(A;i,j)$
であって，
$w(\gamma')w(\mu')=w(\gamma)w(\mu),$
$c(\gamma')=c(\gamma)\pm 1$
を満たすもの．

以下，そのような対合を構成する．
任意のケーリーハミルトン配置 $(\gamma,\mu)$ について，
歩道 $\mu$ を $\mu=(v_0,v_1,\ldots,v_\ell)$ とすると，以下の1, 2のどちらかが成り立つような最小の添字 $k$ が存在する．