PROFILPELAJAR.COM

数学の線型代数学の分野におけるペロン＝フロベニウスの定理（ペロン＝フロベニウスのていり、英: Perron–Frobenius theorem）とは、オスカー・ペロン（英語版）とゲオルク・フロベニウスによって証明された定理で、成分が正である実正方行列には唯一つの最大実固有値が存在し、それに対応する固有ベクトルの各成分は厳密に正である、という主張が述べられている。また、あるクラスの非負行列に対しても、同様の主張が述べられている。この定理は様々な方面へと応用され、確率論（エルゴード性やマルコフ連鎖）や、力学系の理論（有限タイプのサブシフト（英語版））、数値解析 (特に数値線形代数)^[1]、経済学（置塩の定理、レオンチェフの産業連関表）^[2]、人口学（レスリーの人口年齢分布モデル（英語版））^[3]や、インターネット検索エンジン^[4]からフットボールチーム^[5]のランキングに至るまで、その応用範囲は幅広い。

ペロン＝フロベニウスの定理の内容

全ての成分が正の実数であるような行列をここでは正行列と呼び、それらが非負の実数であるような行列をここでは非負行列と呼ぶ。A をある実正方行列としたとき、その固有値は複素数で、その行列のスペクトルを形成する。行列ベキ A^k の k → ∞ としたときの指数関数的成長率は、絶対値が最大であるような A の固有値によって決定される。ペロン＝フロベニウスの定理は、A を非負の実正方行列としたときのそのような支配的な固有値と、それに対応する固有ベクトルの性質について述べたものである。初期の結果は Oskar Perron (1907) によるもので、正行列を対象としていた。のちに、その結果のある非負行列のクラスへの拡張を、Georg Frobenius (1912) が発見した。既約非負行列に対するペロン＝フロベニウスの定理はAlexandroff-Hopf(1935)とHerstein(1953)によって示された（証明にはブラウワーの不動点定理が使われた）^[1]。

正行列

A = (a_ij) を n × n の正行列とする。すなわち、1 ≤ i, j ≤ n に対して a_ij > 0 が成立しているものとする。このとき、以下の性質が成立する。

ペロン根（Perron root）あるいはペロン＝フロベニウス固有値（Perron-Frobenius eigenvalue）と呼ばれるある正の実数 r が存在する。そのような r は A の固有値であり、他のすべての固有値 λ（複素数の場合もあり得る）の絶対値は、r よりも真に小さい。すなわち、|λ| < r が成立する。したがって、スペクトル半径 ρ(A) は r に等しい。
ペロン＝フロベニウス固有値は単純である。すなわち、r は A の特性多項式の単純根である。その結果、r に対応する固有空間は一次元である（左固有空間、すなわち A^T の固有空間に対しても同様の性質が成り立つ）。
A には、固有値 r に対応する固有ベクトル v = (v₁,…,v_n) が存在して、その成分は全て正にとれる。すなわち、A v = r v かつ全ての 1 ≤ i ≤ n に対して v_i > 0 であるものが存在する（同様に、正の左固有ベクトル w で、w^T A = r w^T および w_i > 0 を満たすものが存在する）。
v の正数倍の他には、正（さらには非負）の固有ベクトルは存在しない（左固有ベクトル w についても同様）。すなわち、他のすべての固有ベクトルは必ず符号が反対の成分あるいは実数でない成分を含む。
$\lim _{k\rightarrow \infty }A^{k}/r^{k}=vw^{T}$ である。ただしここでは、A の左および右の固有ベクトルは w^Tv = 1 が成立するように正規化されているとする。さらに、行列 v w^T は r に対応する固有空間の上への射影である。この射影はペロン射影（Perron projection）と呼ばれる。
コラッツ＝ヴィーランド（Collatz-Wielandt）の公式：全ての非負かつ非ゼロのベクトル x に対して、f(x) を、x_i ≠ 0 であるような全ての i について [Ax]_i / x_i を考えたときの最小値とする。このとき、実数値関数 f の最大値はペロン＝フロベニウス固有値である。
ミニマックスコラッツ＝ヴィーランド（Collatz-Wielandt）の公式も、上と同様の形式を持つものである：全ての（狭義に）正であるベクトル x に対し、g(x) を、すべての i について [Ax]_i / x_i を考えたときの最大値とする。このとき、g は実数値関数でその最小値はペロン＝フロベニウス固有値である。
ペロン＝フロベニウス固有値は、次の不等式を満たす：

\min _{i}\sum _{j}a_{ij}\leq r\leq \max _{i}\sum _{j}a_{ij}.

これらの主張はメイヤー（Meyer）による次の参考文献に見られる：^[6] chapter 8 claims 8.2.11-15 page 667 and exercises 8.2.5,7,9 pages 668-669.

この定理の多くの応用において、右および左固有ベクトル v および w は、それぞれ成分の和を 1 に正規化して、（右および左の）確率固有ベクトル（stochastic eigenvector）と呼ばれる。

非負行列

ペロン＝フロベニウスの定理は各成分が非負であるような非負行列に対して拡張できる。正行列と非負行列の二つの場合の共通点と相違点をまとめる上で、次の点に注意されたい：全ての非負行列は、正行列の極限として得ることが出来る。したがって、非負の成分の固有ベクトルの存在が分かる。それに対応する固有値は、明らかに、全ての他の固有値の絶対値よりも大きいか等しい^[7]^[8]。しかしながら、簡単な例

{\begin{pmatrix}0&1\\1&0\end{pmatrix}},{\begin{pmatrix}0&1\\0&0\end{pmatrix}}

により、非負行列に対しては固有値の絶対値の最大が等しい複数の固有値（上の例の最初の行列に対しては、1 と -1）が存在し得ることが分かる。さらに、絶対値最大の固有値が特性多項式の単純根ではない場合もあり得る。例えば上の例の二番目の行列に対しては、固有値0に対応する唯一の固有ベクトル (1,0) は狭義正では無い（最大固有値0は二重であって単純ではない）。したがって、正行列に対する定理の性質は、非負行列に対してはほとんど成立しないように思えるが、フロベニウスはその解決策となる概念を発見したのである。

非負行列の理論においてカギとなる概念として、既約行列（irreducible matrix）と呼ばれる、ある特別な非負行列の類が存在する。それにより、自明では無い一般化が可能になる。すなわち、絶対値が最大である固有値が複数存在する場合にも、最大固有値の構造を理解することができるのである：それらは、h をある整数（行列の周期）とし、r を正の実固有値とし、k = 0, 1, ..., h − 1 とすれば、r e^{$2\pi ki/h$} という式で表せる。そうして r に対応する固有ベクトルは、狭義正の成分を持つ（これは一般的な非負行列において、成分が非負であるだけという場合と対照的である）。またそのような固有値は全て、特性多項式の単純根である。その他の性質については、以下で述べる。

行列の分類

正方行列 A （必ずしも正あるいは実でなくてもよい）が既約（irreducible）であるとは、以下の（互いに同値な）定義で述べられている性質が成立することを言う。

定義 1：A は非自明な不変座標部分空間を持たない。ここで、非自明な座標部分空間とは、任意の基底ベクトルの真部分集合によって張られる線型部分空間を意味する。より明確に言うと、基底ベクトル e_i₁, ..., e_{i_k}, n > k > 0 によって張られる任意の線型部分空間に対し、作用 A を施した像は同じ部分空間には含まれない、ということを意味する。

定義 2：A は置換行列 P によって上三角ブロック行列に相似変換されることはない：

PAP^{-1}\neq {\begin{pmatrix}E&F\\0&G\end{pmatrix}}.

ここで E と G は非自明な（すなわち、行列次数がゼロではない）正方行列である。

A が非負行列である場合には、次の異なる定義が存在する：

定義 3：添字 i と j の全てのペアに対し、(A^m)_ij が 0 とならないようなある自然数 m が存在する。

定義 4：行列 A に関連する有向グラフ G_A を考える。そのグラフは A のサイズ n と等しい数の頂点を持ち、A_ij > 0 である場合に頂点 i から頂点 j への辺が存在するものとする。このとき、行列 A が既約であるための必要十分条件は、その対応するグラフ G_A が強連結であることである。

既約でない行列は、可約（reducible）と呼ばれる。

A を非負行列とする。添字 i を固定したとき、その添字の周期（period of index）を、(A^m)_ii > 0 が成立するような全ての自然数 m の最大公約数として定義する。A が既約であるとき、全ての添字の周期は等しく、それは A の周期と呼ばれる。実際、A が既約であるとき、その周期は、グラフ G_A に含まれる全ての有向閉路の長さの最大公約数として定義される（Kitchens^[9] の 16 ページを参照）。

その周期はまた、非原始性の添字（index of imprimitivity）、または周期性の位数（order of cyclicity）などと呼ばれる。

周期が 1 であるとき、行列 A は非振動的（aperiodic）と呼ばれる。

行列 A は、非負かつ m 次のべきが正となるようなある自然数 m が存在するとき、原始的（primitive）であると呼ばれる。行列が原始的であることと、非負既約かつ非振動的であること、は同値であることは証明されている。

正の正方行列は原始的であり、原始的な行列は既約である。正行列に対するペロン＝フロベニウスの定理の全ての内容は、原始的な行列に対してもやはり真である。しかし、一般的な非負既約行列 A については、（その周期が1でなければ）A のスペクトル半径に等しい絶対値を持つ固有値が複数個存在する場合がある。したがって正行列に対する定理は非負既約行列に対しては、絶対値が最大である固有値の数は行列の周期に等しい、と修正する必用がある。非負既約行列に対するこの結果は、1912年、フロベニウスによって初めて与えられた。

既約行列に対するペロン＝フロベニウスの定理(のまとめ）

いま　A を、非負かつ既約な n × n 行列とし、その周期は h で、スペクトル半径は ρ(A) = r でそれぞれ表されるものとする。このとき、次の主張が成立する。

行列 A のスペクトル半径である正の実数 r は、A の固有値（ペロン＝フロベニウス固有値と呼ばれる）である。
このペロン＝フロベニウス固有値 r は単純（重複が無い）である。よって r に対応する右および左の各固有空間は、一次元である。
A は、固有値 r に対応する左固有ベクトル v を持ち、その成分はすべて正の実数にとれる。
同様に、A は固有値 r に対応する右固有ベクトル w を持ち、その成分はすべて正の実数にとれる。
すべての成分が正の実数である固有ベクトルは、（定数倍を乗じる違いを無視すれば）固有値 r に対応する上述のものだけである。
行列 A は、絶対値が r と等しい複素固有値をちょうど h 個（h は行列の周期）持つ。それらはそれぞれ、特性多項式の単純根であり、r に 1のh乗根を乗じたものとして与えられる。
ω = $2\pi$ /h とする。このとき行列 A は行列 $e^{i\omega }$ A と相似で、したがって A のスペクトル（固有値の分布）は $e^{i\omega }$ の乗算に対して不変である（その乗算は、偏角 ω による複素平面上の回転に対応する）。
h > 1 のときは、次を満たす置換行列 P が存在する：

PAP^{-1}={\begin{pmatrix}0&A_{1}&0&0&\ldots &0\\0&0&A_{2}&0&\ldots &0\\\vdots &\vdots &\vdots &\vdots &&\vdots \\0&0&0&0&\ldots &A_{h-1}\\A_{h}&0&0&0&\ldots &0\end{pmatrix}}.

ここで主対角線上のブロック行列は、すべてゼロの正方行列である。

9. コラッツ＝ヴィーランド（Collatz-Wielandt）の公式：全ての非負かつ非ゼロなベクトル x に対し、x_i ≠ 0 である全ての i について、 [Ax]_i / x_i の最小値を、f(x) とする。このとき、実数値関数 f の最大値はペロン＝フロベニウス固有値 r に等しい。

10. ペロン＝フロベニウス固有値 r は、次の不等式を満たす：

\min _{i}\sum _{j}a_{ij}\leq r\leq \max _{i}\sum _{j}a_{ij}.

さらなる性質

A を既約な非負行列とする。このとき、以下が成立する：

(I+A)ⁿ⁻¹ は正行列である（Meyer ^[6] claim 8.3.5 p. 672を参照）。
ヴィーランドの定理：行列 B の各要素をその絶対値で置き換えた行列を　|B| と表すときに、|B|<A ならば、ρ(B)≤ρ(A) である。等号が成立する（すなわち、μ=ρ(A)e^iφ が B の固有値である）なら、ある対角ユニタリ行列 D に対して B = e^iφ D AD⁻¹ が成立する（すなわち、D の対角成分は e^iΘ_l に等しく、非対角成分はゼロである）^[10]。
行列のベキ A^q が既約であるなら、それは完全既約である。すなわち、ある置換行列 P が存在し、次が成立する：

$PAP^{-1}={\begin{pmatrix}A_{1}&0&0&\dots &0\\0&A_{2}&0&\dots &0\\\vdots &\vdots &\vdots &&\vdots \\0&0&0&\dots &A_{d}\\\end{pmatrix}}$ ここで A_i は同じ最大固有値を持つ既約行列である。これらの行列の数 d は、q と h の最大公約数である。ただし h は行列 A の周期である^[11]。

c(x)=xⁿ+c_k_₁ x^n-k^₁ +c_k_₂ x^n-k^₂ + ... + c_{k_s} x^n-k_s が、非ゼロの係数のみを挙げた A の特性多項式であるなら、A の周期は k₁, k₂, ... , k_s の最大公約数に等しい^[12]。
チェザロ平均： $\lim _{k\rightarrow \infty }{\frac {1}{k}}\sum _{i=0,...,k}A^{i}/r^{i}=(vw^{t})$ が成立する。ただし、A の左右の固有ベクトルは w^tv = 1 が成立するように正規化されている。さらに、行列 v w^t は r に対応するスペクトル射影、すなわち、ペロン射影である^[13]。
r をペロン＝フロベニウス固有値とすると、(r-A) の随伴行列は正である^[14]。
A の対角成分の少なくとも一つが非ゼロであるなら、A は原始的である^[15]。

また、次も成立する。

0 ≤ A < B なら、r_A ≤ r_B であり、さらにもし A が既約であるなら、厳密な不等号が成立する。すなわち、r_A < r_B となる。

行列の原始性の定義の一つによれば、原始的な行列 A は非負であり、A^m が正となるようなある m が存在する。A のサイズに依存してこの m がどれほど大きい値となるのか、疑問に思うこともあるかも知れない。次の主張は、その疑問に対する解答となっている：

A を、サイズが n であるような非負の原始的行列とする。このとき、A^n²-2n+2 は正である。さらに、n > 1 であるなら、以下で与えられるような行列 M が存在する。全ての k < n²-2n+2 に対して M^k は正でなく（しかしもちろん、非負である）、特に (M^n²-2n+1)₁₁=0 である：

M={\begin{pmatrix}0&1&0&0&...&0\\0&0&1&0&...&0\\0&0&0&1&...&0\\\vdots &\vdots &\vdots &\vdots &&\vdots \\0&0&0&0&...&1\\1&1&0&0&...&0\\\end{pmatrix}}

^[16]

応用

非負行列を主題とした著書は数多く存在し、それらにおいてペロン＝フロベニウスの理論は常に中心的な題材となっている。以下に述べる例は、その理論の広大な応用範囲の中から、部分的にピックアップしてきたものに過ぎない。

非負行列

ペロン＝フロベニウスの定理は、一般的な非負行列に対して直接適用することは出来ない。しかし、任意の可約行列 A は、次のような上三角ブロック行列の形式で記述されうる（この形式は可約行列の標準形として知られる）^[17]

PAP⁻¹ =

\left({\begin{smallmatrix}B_{1}&*&*&\cdots &*\\0&B_{2}&*&\cdots &*\\\vdots &\vdots &\vdots &&\vdots \\0&0&0&\cdots &*\\0&0&0&\cdots &B_{h}\end{smallmatrix}}\right)

ここで P は置換行列であり、各 B_i は既約かゼロのいずれかであるような正方行列である。もし A が非負であるなら、各 B_i もすべて非負であり、A のスペクトルはそれらのスペクトルの合併で与えられる。したがって、A のスペクトルに関する性質の多くは、既約な B_i に対してペロン＝フロベニウスの定理を適用することにより、得ることが出来る。

例えば、上の行列のペロン根は ρ(B_i) の最大値で与えられる。固有ベクトルの成分は依然として非負であるが、それらのどれかは正でない場合が起こり得る。

確率行列

行（あるいは、列）確率行列とは、各行（あるいは、列）の成分が非負の実数で、その行（あるいは、列）毎の和が 1 となるようなもののことを言う。このような行列は必ずしも既約ではないため、ペロン＝フロベニウスの定理を直接的に適用することは出来ない。

A を行確率行列とすると、各成分が 1 であるような列ベクトルは、その行列の固有値 1 に対応する固有ベクトルであることが分かる。ここで固有値 1 は、上述の議論により ρ(A) である。しかし、それは単位円上の唯一つの固有値では無いこともあり、対応する固有空間が多次元となることもあり得る。A が既約な行確率行列であるなら、ペロン射影も同様に行確率的で、そのすべての行は等しい。

代数的グラフ理論

ペロン＝フロベニウスの定理は、特に代数的グラフ理論においてよく用いられる。ある非負の n-正方行列の基礎グラフ（underlying graph）とは、1, ..., n で番号付けられた頂点と、頂点iから頂点jに向かう辺を A_ij ≠ 0 の場合に限り持つグラフのことを言う。そのような行列の基礎グラフが強連結であるなら、その行列は既約であり、したがってペロン＝フロベニウスの定理を適用することが出来る。特に、強連結グラフの隣接行列は、既約である^[18]^[19]。

有限マルコフ連鎖

ペロン＝フロベニウスの定理は、有限マルコフ連鎖の理論においても自然に利用されている（その理論においては、連鎖の遷移行列に関して形成される定常分布への、既約な有限マルコフ連鎖の収束についての行列理論的な同値性が見られる。例えば、有限タイプのサブシフト（英語版）を参照されたい）。

コンパクト作用素

→詳細は「クレイン・ルトマンの定理」を参照

より一般的に、有限次元の行列と類似性が多く見られるような、非負コンパクト作用素へと定理を拡張することが出来る。それらの作用素は、物理学において、転送作用素やルエール＝ペロン＝フロベニウス作用素（ダヴィッド・ルエールの名にちなむ）の名前で知られ、広く研究されている。そのような場合、上述の意味で代表となる固有値は力学系の熱力学的平衡に対応し、それ以外の固有値は平衡状態に無い系の崩壊モードに対応する。したがってこの理論は、点集合位相の観点から考察すると可逆的で、決定論的な力学過程であるように思われるかも知れないが、時間の矢を発見するための一つのすじ道を提供するものであった^[20]。

注釈

^ ^a ^b 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。
^ Meyer 2000, p. 8.3.6 p. 681
^ Meyer 2000, p. 8.3.7 p. 683
^ Langville & Meyer 2006, p. 15.2 p. 167
^ Keener 1993, p. p. 80
^ ^a ^b Meyer 2000, p. chapter 8 page 665
^ Meyer 2000, p. chapter 8.3 page 670
^ Gantmacher 2000, p. chapter XIII.3 theorem 3 page 66
^ Kitchens, Bruce (1998), Symbolic dynamics: one-sided, two-sided and countable state markov shifts., Springer
^ Meyer 2000, p. claim 8.3.11 p. 675
^ Gantmacher 2000, p. section XIII.5 theorem 9
^ Meyer 2000, p. page 679
^ Meyer 2000, p. example 8.3.2 p. 677
^ Gantmacher 2000, p. section XIII.2.2 page 62
^ Meyer 2000, p. example 8.3.3 p. 678
^ Meyer 2000, p. chapter 8 example 8.3.4 page 679 and exercise 8.3.9 p. 685
^ Varga 2002, p. 2.43 (page 51)
^ Brualdi, Richard A.; Ryser, Herbert John (1992). Combinatorial Matrix Theory. Cambridge: Cambridge UP. ISBN 0-521-32265-0
^ Brualdi, Richard A.; Cvetkovic, Dragos (2009). A Combinatorial Approach to Matrix Theory and Its Applications. Boca Raton, FL: CRC Press. ISBN 978-1-4200-8223-4
^ Mackey, Michael C. (1992). Time's Arrow: The origins of thermodynamic behaviour. New York: Springer-Verlag. ISBN 0-387-97702-3

参考文献

原著論文

Perron, Oskar (1907), “Zur Theorie der Matrices”, Mathematische Annalen 64 (2): 248–263, doi:10.1007/BF01449896

Frobenius, Georg (1912), “Ueber Matrizen aus nicht negativen Elementen”, Sitzungsber. Königl. Preuss. Akad. Wiss.: 456–477

Frobenius, Georg (1908), “Über Matrizen aus positiven Elementen, 1”, Sitzungsber. Königl. Preuss. Akad. Wiss.: 471–476

Frobenius, Georg (1909), “Über Matrizen aus positiven Elementen, 2”, Sitzungsber. Königl. Preuss. Akad. Wiss.: 514–518

Gantmacher, Felix (2000) [1959], The Theory of Matrices, Volume 2, AMS Chelsea Publishing, ISBN 0-8218-2664-6 (1959 edition had different title: "Applications of the theory of matrices". Also the numeration of chapters is different in the two editions.)

Collatz, Lothar (1942), “Einschließungssatz für die charakteristischen Zahlen von Matrize”, Mathematische Zeitschrift 48 (1): 221–226, doi:10.1007/BF01180013

Wielandt, Helmut (1950), “Unzerlegbare, nicht negative Matrizen”, Mathematische Zeitschrift 52 (1): 642–648, doi:10.1007/BF02230720

図書

Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. ISBN 0-89871-321-8.
Chris Godsil and Gordon Royle, Algebraic Graph Theory, Springer, 2001.
A. Graham, Nonnegative Matrices and Applicable Topics in Linear Algebra, John Wiley&Sons, New York, 1987.
R. A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, 1990
S. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability London: Springer-Verlag, 1993. ISBN 0-387-19832-6 (2nd edition, Cambridge University Press, 2009)
Henryk Minc, Nonnegative matrices, John Wiley&Sons, New York, 1988, ISBN 0-471-83966-3
Seneta, E. Non-negative matrices and Markov chains. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Originally published by Allen & Unwin Ltd., London, 1973) ISBN 978-0-387-29765-1
Suprunenko, D.A. (2001), “Perron-Frobenius theorem”, in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 (The claim that A_j has order n/h at the end of the statement of the theorem is incorrect.)
Richard S. Varga, Matrix Iterative Analysis, 2nd ed., Springer-Verlag, 2002