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

数学の線型代数学の分野におけるペロン＝フロベニウスの定理（ペロン＝フロベニウスのていり、英: 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_{1}},\dots ,e_{i_{k}}\}$ （ $0<k<n$ ）によって張られる部分空間が、A の作用によってそれ自身の中に写されないことを意味する。
定義 2: A は置換行列 P によって上三角ブロック行列に相似変換されることはない。すなわち、任意の置換行列 P に対して以下が成り立つ。; $PAP^{-1}\neq {\begin{pmatrix}E&F\\0&G\end{pmatrix}}.$; ここで E と G は次数が 1 以上の正方行列である。

A が非負行列である場合には、以下の条件も既約性と同値である。

定義 3: 任意の添字のペア $(i,j)$ に対し、 $(A^{m})_{ij}>0$ となるようなある自然数 m が存在する。
定義 4: 行列 A に対応する有向グラフ G_A（ $A_{ij}>0$ のとき頂点 i から j へ辺を張るグラフ）が強連結である。

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

A を非負行列とする。添字 i を固定したとき、 $(A^{m})_{ii}>0$ が成立するような全ての自然数 m の最大公約数を、その添字の周期（period of index）と呼ぶ。A が既約であるとき、全ての添字の周期は一致し、これを A の周期と定義する。既約行列 A の周期は、有向グラフ G_A に含まれるすべての閉路の長さの最大公約数に等しい^[9]。

周期は、非原始性の指数（index of imprimitivity）や周期性の位数（order of cyclicity）とも呼ばれる。周期が 1 である既約行列は、非振動的（aperiodic）あるいは非周期的と呼ばれる。

非負行列 A は、ある自然数 m に対して $A^{m}$ のすべての成分が正となるとき、原始的（primitive）であるという。行列が原始的であるための必要十分条件は、既約かつ周期が 1 であることである。

すべての成分が正の正方行列は原始的であり、原始的な行列は常に既約である。正行列に対するペロン＝フロベニウスの定理の諸性質は、原始的な行列に対してもそのまま適用できる。一方で、周期 $h>1$ を持つ非負既約行列の場合、スペクトル半径に等しい絶対値を持つ固有値が $h$ 個存在する。このため、非負既約行列への拡張にあたっては、絶対値最大の固有値の個数に関する記述を修正する必要がある。この結果は、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]。

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