【SPONSORED LINK】

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

      

[Perron-Frobenius(ペロン-フロベニウス)の定理]とは,全ての成分が正または非負である正方行列の最大固有値に関する定理である.

歴史的には,全ての成分が正の行列に対する定理をOskar Perronが示し,後にFerdinand Georg Frobeniusが全ての成分が非負の行列に対する同様の定理を示した.

また,この[Perron-Frobeniusの定理]の応用範囲は非常に広い.

なお,多項式に行列を代入したときの固有値に対するFrobeniusの定理は以下を参照されたい.

【参考記事:フロベニウスの定理

【SPONSORED LINK】

Perron-Frobeniusの定理

全ての成分が正(非負)の行列を正行列(非負行列)ということにする.同様に,全ての成分が正(非負)のベクトルを正ベクトル(非負ベクトル)ということにする.

冒頭にも書いたように,Perron-Frobeniusの定理は正の正方行列に対するものと,非負の正方行列に対するものの2通りある.

[正行列に対するPerron-Frobeniusの定理] 正の正方行列Aは次を満たす正の固有値\alphaをもつ.

  1. Aの任意の固有値の絶対値\betaに対して,|\beta|<\alphaを満たす.
  2. 固有値\alphaの重複度は1であり,固有値\alphaに属する正の固有ベクトルが存在する.
  3. \alpha以外の固有値に属する正の固有ベクトルは存在しない.

[非負行列に対するPerron-Frobeniusの定理] 非負正方行列Aに対して次が成り立つ.

  1. Aは非負の固有値をもち,そのうちで最大のものを\alphaとすれば,Aの任意の固有値の絶対値は\alpha以下である.
  2. 固有値\alphaに属する正の固有ベクトルが存在する.

これら両方の主張において,固有値\alphaをPerron-Frobenius根(Perron根,Frobenius根)という.

Perron-Frobeniusの定理の証明

この記事では,正行列に対するPerron-Frobeniusの定理を証明する.非負行列に対するPerron-Frobeniusの定理は,最後に挙げた参考文献を参照されたい.ただし,以下では,

  1. AN次行列であるとし,A(i,j)成分をa_{ij}とする.
  2. ベクトル\boldsymbol{x}i成分を[\boldsymbol{x}]_{i}で表す.
  3. \boldsymbol{x}\in\mathbb{R}^Nに対して,\|\boldsymbol{x}\|:=\max\limits_{i=1,\dots,N}[\boldsymbol{x}]_iとする.

とする.

[証明]

\boldsymbol{u}_0:=\left(N^{-1/2},\dots,N^{-1/2}\right)\in\mathbb{R}^Nとする.このとき,\boldsymbol{u}_0\|\boldsymbol{u}_0\|=1を満たす正ベクトルである.\mathbb{R}^Nの列\{\boldsymbol{u}_n\}_{n=0}^{\infty}

\boldsymbol{u}_{n+1}=\dfrac{A\boldsymbol{u}_n}{\|A\boldsymbol{u}_n\|}\quad (n=0,1,\dots)

により定める.このとき,任意のn=0,1,\dotsに対して,\boldsymbol{u}_0Aが共に正であることから\boldsymbol{u}_n>0であり,また\|\boldsymbol{u}_n\|=1である.

また,\boldsymbol{x}\in\mathbb{R}^Nに対して,f(\boldsymbol{x}):=\min\limits_{j=1,\dots,N}\dfrac{[A\boldsymbol{x}]_j}{[\boldsymbol{x}]_j}g(\boldsymbol{x}):=\max\limits_{j=1,\dots,N}\dfrac{[A\boldsymbol{x}]_j}{[\boldsymbol{x}]_j}とする.

以下,Step 1〜5に分けて証明する.

Step 1

\alpha:=\lim\limits_{n\to\infty}f(\boldsymbol{u}_n)が存在し,\alpha>0が成り立つ.

[Step 1の証明]

任意にn=0,1,\dotsをとる.各i=1,\dots,Nに対して,

[A\boldsymbol{u}_n]_i-f(\boldsymbol{u}_n)[\boldsymbol{u}_n]_i\ge[A\boldsymbol{u}_n]_i-\dfrac{[A\boldsymbol{u}_n]_i}{[\boldsymbol{u}_n]_i}\times[\boldsymbol{u}_n]_i=0
g(\boldsymbol{u}_n)[\boldsymbol{u}_n]_i-[A\boldsymbol{u}_n]_i\ge\dfrac{[A\boldsymbol{u}_n]_i}{[\boldsymbol{u}_n]_i}\times[\boldsymbol{u}_n]_i-[A\boldsymbol{u}_n]_i=0

だから,A\boldsymbol{u}_n-f(\boldsymbol{u}_n)\boldsymbol{u}_ng(\boldsymbol{u}_n)\boldsymbol{u}_n-A\boldsymbol{u}_nは共に非負ベクトルである.よって,これらに左から正行列\dfrac{A}{\|A\boldsymbol{u}_n\|}をかけてできるベクトルA\boldsymbol{u}_{n+1}-f(\boldsymbol{u}_n)\boldsymbol{u}_{n+1}g(\boldsymbol{u}_n)\boldsymbol{u}_{n+1}-A\boldsymbol{u}_{n+1}も非負である.したがって,各i=1,\dots,Nに対して,

f(\boldsymbol{u}_n)\le\dfrac{[A\boldsymbol{u}_{n+1}]_i}{[\boldsymbol{u}_{n+1}]_i}
g(\boldsymbol{u}_n)\ge\dfrac{[A\boldsymbol{u}_{n+1}]_i}{[\boldsymbol{u}_{n+1}]_i}

だから,f(\boldsymbol{u}_n)\le f(\boldsymbol{u}_{n+1})g(\boldsymbol{u}_n)\ge g(\boldsymbol{u}_{n+1})が成り立つ.また,明らかにf(\boldsymbol{u}_n)\le g(\boldsymbol{u}_n)だから,

f(\boldsymbol{u}_0) \le f(\boldsymbol{u}_1) \le f(\boldsymbol{u}_2) \le\dots \le g(\boldsymbol{u}_2) \le g(\boldsymbol{u}_1) \le g(\boldsymbol{u}_0)

が成り立つ.よって,\Rの列\{f(\boldsymbol{u}_n)\}は上に有界な単調増加列だから,極限\alpha:=\lim\limits_{n\to\infty}f(\boldsymbol{u}_n)が存在する.

また,任意のn=0,1,\dotsに対して0<f(\boldsymbol{u}_0)\le f(\boldsymbol{u}_n)だから,\alpha>0も示される.

Step 2

\alphaAの固有値で,固有値\alphaに属する固有ベクトルは正である.

[Step 2の証明]

M:=\sum\limits_{i,j=1}^{N}a_{ij}m:=\min\limits_{i,j\in\{1,\dots,N\}}a_{ij}とする.

A\boldsymbol{u}_nが正であることと\|\boldsymbol{u}_n\|=1から,

\|A\boldsymbol{u}_n\| =\max\limits_{i=1,\dots,N}\bra{\dsum_{j=1}^{N}a_{ij}[\boldsymbol{u}_n]_j} \le\max\limits_{i=1,\dots,N}\bra{\dsum_{j=1}^{N}a_{ij}\|\boldsymbol{u}_n\|} =M

である.よって,任意のi=1,\dots,Nに対して,

[A\boldsymbol{u}_{n+1}]_i-f(\boldsymbol{u}_n)[\boldsymbol{u}_{n+1}]_i
=\f{1}{\|A\boldsymbol{u}_n\|}[A(A-f(\boldsymbol{u}_n))\boldsymbol{u}_{n}]_i
=\f{1}{\|A\boldsymbol{u}_n\|}\dsum_{j=1}^{N}a_{ij}[(A-f(\boldsymbol{u}_n))\boldsymbol{u}_{n}]_j
\ge\f{m}{\|A\boldsymbol{u}_n\|}\dsum_{j=1}^{N}[(A-f(\boldsymbol{u}_n))\boldsymbol{u}_{n}]_j
\ge\f{m}{M}\|(A-f(\boldsymbol{u}_n))\boldsymbol{u}_{n}\|

が成り立つ.[A\boldsymbol{u}_{n+1}]_i-f(\boldsymbol{u}_n)[\boldsymbol{u}_{n+1}]_i\ge\dfrac{m}{M}\|(A-f(\boldsymbol{u}_n))\boldsymbol{u}_{n}\|の両辺を[\boldsymbol{u}_{n+1}]_i>0で割って整理し,[\boldsymbol{u}_{n+1}]_i\le1に注意すると,

\dfrac{[A\boldsymbol{u}_{n+1}]_i}{[\boldsymbol{u}_{n+1}]_i} \ge f(\boldsymbol{u}_n)+\dfrac{m}{M}\|(A-f(\boldsymbol{u}_n))\boldsymbol{u}_{n}\|

が分かる.よって,

f(\boldsymbol{u}_{n+1}) \ge f(\boldsymbol{u}_n)+\f{m}{M}\|(A-f(\boldsymbol{u}_n))\boldsymbol{u}_{n}\|

が従う.よって,両辺でn\to\inftyとすれば,0\ge\li_{n\to\infty}\f{m}{M}\|(A-f(\boldsymbol{u}_n))\boldsymbol{u}_n\|となって,\li_{n\to\infty}\|(A-f(\boldsymbol{u}_n))\boldsymbol{u}_n\|=0が分かる.

いま,\set{\boldsymbol{x}\in\R^{N}}{|\boldsymbol{x}|=1}N次元ユークリッド空間\R^N上の有界閉集合だから,点列コンパクトである.よって,\{\boldsymbol{u}_n\}_{n=0}^{\infty}の部分列で極限uを持つものが存在する.

したがって,A\boldsymbol{u}=\alpha\boldsymbol{u}となって,\alphaAの固有値であり,\boldsymbol{u}は固有値\alphaの固有ベクトルであることが示された.

また,\{\boldsymbol{u}_n\}の定め方から\boldsymbol{u}は零ベクトルでない非負ベクトルで,Aは正ベクトルだから,A\boldsymbol{u}は正ベクトルである.よって,\alpha\boldsymbol{u}は正ベクトルだから,\alpha>0と併せて\boldsymbol{u}は正ベクトルであることが分かる.

Step 3

固有値\alphaの重複度は1であり,固有値\alphaに属する正の固有ベクトルが存在する.

[Step 3の証明]

Aの転置行列A^Tは正行列だから,Step 1よりA^Tの正固有値\lambdaと,固有値\lambdaに属する正固有ベクトル\boldsymbol{u}'が存在する.このとき,

\alpha\boldsymbol{u}'^T\boldsymbol{u} =\boldsymbol{u}'^T(\alpha\boldsymbol{u}) =\boldsymbol{u}'^T(A\boldsymbol{u}) =(A^T\boldsymbol{u}')^T\boldsymbol{u} =(\lambda\boldsymbol{u}')^T\boldsymbol{u} =\lambda\boldsymbol{v}^T\boldsymbol{u}

である.\boldsymbol{u}\boldsymbol{u}'は共に正だから,\boldsymbol{u}'^T\boldsymbol{u}>0なので\boldsymbol{u}'^T\boldsymbol{u}\neq0である.よって,\alpha=\lambdaが成り立つ.

ここで,固有値\alphaに属する任意の固有ベクトル\boldsymbol{v}をとり,任意a\in\Rに対して\boldsymbol{u}-a\boldsymbol{v}\neq\boldsymbol{o}であると仮定する.

\boldsymbol{u}-0\times\boldsymbol{v}=\boldsymbol{u}が正ベクトルであることとスカラー倍の連続性から,あるa\in\Rが存在して,\boldsymbol{u}-a\boldsymbol{v}の成分の少なくとも1つは0であり,他の成分は0以上となる.したがって,\alpha(\boldsymbol{u}-a\boldsymbol{v})も成分の少なくとも1つは0であり,他の成分は0以上となる.

一方,Aが正行列であることからA(\boldsymbol{u}-a\boldsymbol{v})=\alpha(\boldsymbol{u}-a\boldsymbol{v})は正ベクトルとなって矛盾する.

よって,あるa\in\R\setminus\{\boldsymbol{o}\}が存在して,\boldsymbol{u}-a\boldsymbol{v}=\boldsymbol{o}が成り立つ.これにより,\alphaの固有空間の次元は1である.したがって,AをJordan標準形に変形したとき,固有値\alphaに関するJordan細胞J(\alpha)の個数は1である.

もし,J(\alpha)の次数が2以上であれば,\boldsymbol{u}Aの固有値\alphaに属する固有ベクトルであることから,\boldsymbol{w}\in\R^Nが存在してA\boldsymbol{w}=\alpha\boldsymbol{w}+\boldsymbol{u}が成り立つ.よって,

0<\boldsymbol{u}'^T\boldsymbol{u} =\boldsymbol{u}'^T(A\boldsymbol{w}-\alpha\boldsymbol{w})
=(A^T\boldsymbol{u}')^T\boldsymbol{w}-\alpha\boldsymbol{u}'^T\boldsymbol{w}
=(\lambda\boldsymbol{u}')^T\boldsymbol{w}-\alpha\boldsymbol{u}'^T\boldsymbol{w} =0

となって矛盾するから,J(\alpha)の次数は1である.

Step 4

\alpha以外の固有値に属する正の固有ベクトルは存在しない.

[Step 4の証明]

Aの固有値\muが正の固有ベクトル\boldsymbol{v}'を持つとする.このとき,[2]から\boldsymbol{u}'A^Tの固有値\alphaの固有ベクトルだったから,

\mu\boldsymbol{u}'^T\boldsymbol{v}' =\boldsymbol{u}'^T(\mu\boldsymbol{v}') =\boldsymbol{u}'^T(A\boldsymbol{v}') =(A^T\boldsymbol{u}')^T\boldsymbol{v}' =(\alpha\boldsymbol{u}')^T\boldsymbol{v}' =\alpha\boldsymbol{u}'^T\boldsymbol{v}'

である.\boldsymbol{u}'\boldsymbol{v}'は共に正だから,\boldsymbol{u}'^T\boldsymbol{v}'>0なので\boldsymbol{u}'^T\boldsymbol{v}'\neq0である.よって,\alpha=\muが成り立つ.

ここで,任意b\in\mathbb{R}\setminus\{0\}に対して\boldsymbol{u}-b\boldsymbol{v}'\neq0であると仮定する.

このとき,\boldsymbol{u}-0\times\boldsymbol{v}'=\boldsymbol{u}が正ベクトルであることとスカラー倍の連続性から,あるb\in\mathbb{R}が存在して,\boldsymbol{u}-b\boldsymbol{v}'の成分の少なくとも1つは0であり,他の成分は0以上となる.したがって,\alpha(\boldsymbol{u}-b\boldsymbol{v}')も成分の少なくとも1つは0であり,他の成分は0以上となる.

一方,Aが正行列であることからA(\boldsymbol{u}-b\boldsymbol{v}')=\alpha(\boldsymbol{u}-b\boldsymbol{v}')は正ベクトルとなって矛盾する.

よって,あるa\in\mathbb{R}が存在して,\boldsymbol{u}-a\boldsymbol{v}'=\boldsymbol{o}が成り立つから,

\mu\boldsymbol{v}' =A\boldsymbol{v}' =\dfrac{1}{a}A\boldsymbol{u} =\dfrac{\alpha}{a}\boldsymbol{u} =\alpha\boldsymbol{v}'

となって,\boldsymbol{v}'\neq\boldsymbol{o}から\alpha=\muとなる.

Step 5

Aの任意の固有値の絶対値\betaに対して,|\beta|<\alphaを満たす.

[Step 5の証明]

固有値\betaAの任意の固有値とする.\boldsymbol{z}を固有値\betaに属する固有ベクトルであるとする.このとき,A\boldsymbol{z}=\beta\boldsymbol{z}の第i成分について,三角不等式を用いると,

\dsum_{j=1}^{N}a_{ij}\abs{[\boldsymbol{z}]_{j}} \ge\abs{\dsum_{j=1}^{N}a_{ij}[\boldsymbol{z}]_{j}} =\abs{[A\boldsymbol{z}]_{i}} =\abs{[\beta\boldsymbol{z}]_{i}} =|\beta|\abs{[\boldsymbol{z}]_{i}}

だから,A^Tの固有値\alphaに属する正の固有ベクトル\boldsymbol{u}'を用いると,

\alpha\dsum_{j=1}^{N}[\boldsymbol{u}']_{j}\abs{[\boldsymbol{z}]_{j}} =\dsum_{j=1}^{N}[\alpha\boldsymbol{u}']_{j}\abs{[\boldsymbol{z}]_{j}} =\dsum_{j=1}^{N}[A^T\boldsymbol{u}']_{j}\abs{[\boldsymbol{z}]_{j}}
=\dsum_{j=1}^{N}\bra{\dsum_{i=1}^{N}a_{ij}[\boldsymbol{u}']_{i}}\abs{[\boldsymbol{z}]_{j}} =\dsum_{i=1}^{N}\bra{\dsum_{j=1}^{N}a_{ij}\abs{[\boldsymbol{z}]_{j}}}[\boldsymbol{u}']_{i}
\ge\dsum_{i=1}^{N}\bra{|\beta|\abs{[\boldsymbol{z}]_{i}}}[\boldsymbol{u}']_{i} =|\beta|\dsum_{i=1}^{N}[\boldsymbol{u}']_{i}\abs{[\boldsymbol{z}]_{i}}

となって,\alpha\ge|\beta|が従う.ここで,もし\alpha=|\beta|であれば,上の三角不等式で等号が成り立つから,\boldsymbol{z}の各成分の偏角は全て等しい.この偏角を\thetaとすると,e^{-i\theta}\boldsymbol{z}は正ベクトルで,

A(e^{-i\theta}\boldsymbol{z}) =e^{-i\theta}A\boldsymbol{z} =e^{-i\theta}\beta\boldsymbol{z} =\beta(e^{-i\theta}\boldsymbol{z})

だから,\betaは正の固有ベクトルを持つことになり,[Step 4]から\beta=\alphaとなる.よって,\beta\neq\alphaであれば,\alpha>|\beta|が従う.

[証明終]

参考文献

関連記事

【良いと思ったらシェアを!】

最後まで読んでいただきありがとうございました!

良ければシェアボタンから共有をお願いします!

コメントを残す

*

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください