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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

ペロン=フロベニウスの定理の内容[編集]

全ての成分が実数であるような行列をここでは正行列と呼び、それらが非負の実数であるような行列をここでは非負行列と呼ぶ。A をある実正方行列としたとき、その固有値複素数で、その行列のスペクトルを形成する。行列ベキ Akk → ∞ としたときの指数関数的成長率英語版は、絶対値が最大であるような A の固有値によって決定される。ペロン=フロベニウスの定理は、A を非負の実正方行列としたときのそのような支配的な固有値と、それに対応する固有ベクトルの性質について述べたものである。初期の結果は Oskar Perron (1907) によるもので、正行列を対象としていた。のちに、その結果のある非負行列のクラスへの拡張を、Georg Frobenius (1912) が発見した。

正行列[編集]

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

  1. ペロン根(Perron root)あるいはペロン=フロベニウス固有値(Perron-Frobenius eigenvalue)と呼ばれるある正の実数 r が存在する。そのような rA の固有値であり、他のすべての固有値 λ複素数であることもあり得る)の絶対値は、r よりも厳密に小さい。すなわち、|λ| < r が成立する。したがって、スペクトル半径 ρ(A) は r に等しい。
  2. ペロン=フロベニウス固有値は単純固有値である。すなわち、rA特性多項式の単純根である。その結果、r に対応する固有空間は一次元となる(左固有空間、すなわち AT の固有空間に対しても同様の性質が成り立つ)。
  3. A には、固有値 r に対応する固有ベクトル v = (v1,…,vn) で、その成分が全て正であるようなものが存在する。すなわち、A v = r v かつ全ての 1 ≤ in に対して vi > 0 が成立する(同様に、正の左固有ベクトル w で、wT A = r wT および wi > 0 を満たすようなものも存在する)。
  4. v の正数倍を除いて、他に正(さらには非負)の固有ベクトルは存在しない(左固有ベクトル w についても同様)。すなわち、他の全ての固有ベクトルは少なくとも一つの負の成分あるいは実数でない成分を含む。
  5.  \lim_{k \rightarrow \infty} A^k/r^k = v w^T である。ただし、A の左および右の固有ベクトルは wTv = 1 が成立するように正規化されている。さらに、行列 v wTr に対応する固有空間の上への射影である。この射影はペロン射影(Perron projection)と呼ばれる。
  6. コラッツ=ヴィーヘルトの公式:全ての非負かつ非ゼロのベクトル x に対し、f(x) を、xi ≠ 0 であるような全ての i について [Ax]i / xi を考えたときの最小値とする。このとき、f はその最大値がペロン=フロベニウス固有値であるような実数値関数である。
  7. ミニマックスコラッツ=ヴィーヘルトの公式も、上と同様の形式を持つものである:全ての厳密に正であるベクトル x に対し、g(x) を、すべての i について [Ax]i / xi を考えたときの最大値とする。このとき、g はその最小値がペロン=フロベニウス固有値であるような実数値関数である。
  8. ペロン=フロベニウス固有値は、次の不等式を満たす:
\min_i \sum_{j} a_{ij} \le r \le \max_i \sum_{j} a_{ij}.

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

右および左固有ベクトル v および w は、通常それらの成分の和が 1 となるように正規化される。そのような場合、それらは確率固有ベクトル(stochastic eigenvector)と呼ばれる。

非負行列[編集]

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


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

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

非負行列の理論においてカギとなる概念として、既約行列(irreducible matrix)と呼ばれる、ある特別な非負行列の類が存在する。それにより、自明では無い一般化が可能となる訳である。すなわち、絶対値最大を達成する固有値は一意的ではないかも知れないが、最大固有値の構造を理解することが出来るのである:それらは、h をある整数(行列の周期)とし、r を狭義正な実固有値とし、l = 0, 1, ..., h − 1 とすれば、ei2πl/hr という形式で記述することが出来る。r に対応する固有ベクトルは、狭義正の成分を持つ(これは一般的な非負行列において、成分が非負であるだけという場合と対照的である)。またそのような固有値は全て、特性多項式の単純根である。その他の性質については、下記に述べる。

行列の分類[編集]

A を、(必ずしも正あるいは実でなくてもよい)正方行列とする。行列 A既約(irreducible)であるとは、以下に述べる同値な性質のどれか一つが成立することを言う。

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

定義 2:A置換行列 P によって上三角ブロック行列に共役化されることはない:

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

ここで EG は非自明な(すなわち、ゼロよりもサイズが大きい)正方行列である。

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

定義 3:添字 ij の全てのペアに対し、(Am)ij が 0 とならないようなある自然数 m が存在する。

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

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

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

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

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

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

正の正方行列は原始的であり、原始的な行列は既約である。正行列に対するペロン=フロベニウスの定理の全ての内容は、原始的な行列に対しても依然として真である。しかし、一般的な非負既約行列 A は、A のスペクトル半径と絶対値が等しくなるような固有値を複数個持つこともあり、したがって正行列に対する定理も状況に応じて修正する必要がある。実際、そのような固有値の数は、行列の周期と等しいことが知られている。非負行列に対する結果は、1912年、フロベニウスによって初めて与えられた。

既約行列に対するペロン=フロベニウスの定理[編集]

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

  1. r は正の実数で、行列 A の固有値(ペロン=フロベニウス固有値と呼ばれる)である。
  2. ペロン=フロベニウス固有値 r は単純固有値である。r に対応する右および左の各固有空間は、一次元である。
  3. A は、固有値 r に対応する左固有ベクトル v を持ち、その成分はすべて正である。
  4. 同様に、A は固有値 r に対応する右固有ベクトル w' を持ち、その成分はすべて正である。
  5. すべての成分が正であるような固有ベクトルは、固有値 r に対応する上述のもののみである。
  6. 行列 A は、絶対値が r と等しいような複素固有値をちょうど h 個(h は行列の周期)持つ。それらはそれぞれ、特性多項式の単純根であり、rh次の1の冪根の積として与えられる。
  7. ω = 2π/h とする。このとき行列 A は行列 eA相似で、したがって A のスペクトルは e の乗算に対して不変である(その乗算は、偏角 ω による複素平面上の回転に対応する)。
  8. 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. コラッツ=ヴィーランドの補題:全ての非負かつ非ゼロなベクトル x に対し、xi ≠ 0 であるような全ての i についての [Ax]i / xi の最小値を、f(x) とする。このとき、f は、その最大がペロン=フロベニウス固有値を与えるような実数値関数である。
10. ペロン=フロベニウス固有値は、次の不等式を満たす:
\min_i \sum_{j} a_{ij} \le r \le \max_i \sum_{j} a_{ij}.

さらなる性質[編集]

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

  1. (I+A)n−1 は正行列である(Meyer [5] claim 8.3.5 p. 672を参照)。
  2. ヴィーランドの定理:|B|<A なら、ρ(B)≤ρ(A) である。等号が成立する(すなわち、μ=ρ(A)eB の固有値である)なら、ある対角ユニタリ行列 D に対して B = e D AD−1 が成立する(すなわち、D の対角成分は el に等しく、非対角成分はゼロである)[9]
  3. 行列のベキ Aq が既約であるなら、それは完全既約である。すなわち、ある置換行列 P が存在し、次が成立する:


P A P^{-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}
ここで Ai は同じ最大固有値を持つ既約行列である。これらの行列の数 d は、qh の最大公約数である。ただし h は行列 A の周期である[10]

  1. c(x)=xn+ck1 xn-k1 +ck2 xn-k2 + ... + cks xn-ks が、非ゼロの係数のみを挙げた A の特性多項式であるなら、A の周期は k1, k2, ... , ks の最大公約数に等しい[11]
  2. チェザロ平均 \lim_{k \rightarrow \infty} 1/k\sum_{i=0,...,k} A^i/r^i = ( v w^t) が成立する。ただし、A の左右の固有ベクトルは wtv = 1 が成立するように正規化されている。さらに、行列 v wtr に対応するスペクトル射影、すなわち、ペロン射影である[12]
  3. r をペロン=フロベニウス固有値とすると、(r-A) の随伴行列は正である[13]
  4. A の対角成分の少なくとも一つが非ゼロであるなら、A は原始的である[14]

また、次も成立する。

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

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

  • A を、サイズが n であるような非負の原始的行列とする。このとき、An2-2n+2 は正である。さらに、n > 1 であるなら、以下で与えられるような行列 M が存在する。全ての k < n2-2n+2 に対して Mk は正でなく(しかしもちろん、非負である)、特に (Mn2-2n+1)11=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}
[15]

応用[編集]

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

非負行列[編集]

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

PAP−1 =  \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 は転置行列であり、各 Bi は既約かゼロのいずれかであるような正方行列である。もし A が非負であるなら、各 Bi もすべて非負であり、A のスペクトルはそれらのスペクトルの合併で与えられる。したがって、A のスペクトルに関する性質の多くは、既約な Bi に対してペロン=フロベニウスの定理を適用することにより、得ることが出来る。

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

確率行列[編集]

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

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

代数的グラフ理論[編集]

ペロン=フロベニウスの定理は、特に代数的グラフ理論英語版においてよく用いられる。ある非負の n-正方行列の基礎グラフ(underlying graph)とは、1, ..., n で番号付けられた頂点と、Aij ≠ 0 であるような場合にのみ存在する弧 ij からなるグラフのことを言う。そのような行列の基礎グラフが強連結であるなら、その行列は既約であり、したがってペロン=フロベニウスの定理を適用することが出来る。特に、強連結グラフ隣接行列は、既約である[17][18]

有限マルコフ連鎖[編集]

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

コンパクト作用素[編集]

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

関連項目[編集]

注釈[編集]

参考文献[編集]

原著論文[編集]

  • 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 
  • Wielandt, Helmut (1950), “Unzerlegbare, nicht negative Matrizen”, Mathematische Zeitschrift 52 (1): 642–648, doi:10.1007/BF02230720 

図書[編集]