【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. ベクトル\m{x}i成分を[\m{x}]_iで表す.
  3. \m{x}\in\R^Nに対して,\|\m{x}\|:=\max\limits_{i=1,\dots,N}[\m{x}]_iとする.

とする.

[証明]

\m{u}_0:=\bmat{1\\\vdots\\1}\in\R^Nとする.このとき,\m{u}_0\|\m{u}_0\|=1を満たす正ベクトルである.

\R^Nの列\{\m{u}_n\}_{n=0}^{\infty}

\begin{align*} \m{u}_{n+1} :=\frac{A\m{u}_n}{\|A\m{u}_n\|}\quad (n=0,1,\dots) \end{align*}

により帰納的に定める.このとき,任意のn=0,1,\dotsに対して,\m{u}_0は正ベクトル,Aは正行列だから\m{u}_n>0であり,また\|\m{u}_n\|=1である.

また,\m{x}\in\R^Nに対して,

  • f(\m{x}):=\min\limits_{j=1,\dots,N}\frac{[A\m{x}]_j}{[\m{x}]_j}
  • g(\m{x}):=\max\limits_{j=1,\dots,N}\frac{[A\m{x}]_j}{[\m{x}]_j}

とする.

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

Step 1

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

[Step 1の証明]

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

\begin{align*} & [A\m{u}_n]_i-f(\m{u}_n)[\m{u}_n]_i \ge[A\m{u}_n]_i-\frac{[A\m{u}_n]_i}{[\m{u}_n]_i}\times[\m{u}_n]_i=0, \\& g(\m{u}_n)[\m{u}_n]_i-[A\m{u}_n]_i \ge\frac{[A\m{u}_n]_i}{[\m{u}_n]_i}\times[\m{u}_n]_i-[A\m{u}_n]_i=0 \end{align*}

だから,A\m{u}_n-f(\m{u}_n)\m{u}_n, g(\m{u}_n)\m{u}_n-A\m{u}_nは共に非負ベクトルである.

よって,これらに左から正行列\frac{A}{\|A\m{u}_n\|}をかけてできるベクトルA\m{u}_{n+1}-f(\m{u}_n)\m{u}_{n+1}, g(\m{u}_n)\m{u}_{n+1}-A\m{u}_{n+1}も非負なので,各i=1,\dots,Nに対して,

\begin{align*} f(\m{u}_n)\le\frac{[A\m{u}_{n+1}]_i}{[\m{u}_{n+1}]_i},\quad g(\m{u}_n)\ge\frac{[A\m{u}_{n+1}]_i}{[\m{u}_{n+1}]_i} \end{align*}

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

\begin{align*} f(\m{u}_0) \le f(\m{u}_1) \le f(\m{u}_2) \le\dots \le g(\m{u}_2) \le g(\m{u}_1) \le g(\m{u}_0) \end{align*}

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

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

Step 2

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

[Step 2の証明]

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

\m{u}_nは正で\|\m{u}_n\|=1だから[\m{u}_n]_j\le1である.またAも正だから,

\begin{align*} \|A\m{u}_n\| =&\max\limits_{i\in\{1,\dots,N\}}\bra{\sum_{j=1}^Na_{ij}[\m{u}_n]_j} \\\le&\max\limits_{i=\{1,\dots,N\}}\bra{\sum_{j=1}^Na_{ij}} \le M \end{align*}

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

\begin{align*} [A\m{u}_{n+1}]_i-f(\m{u}_n)[\m{u}_{n+1}]_i =&\frac{1}{\|A\m{u}_n\|}[A(A-f(\m{u}_n))\m{u}_n]_i \\=&\frac{1}{\|A\m{u}_n\|}\sum_{j=1}^Na_{ij}[(A-f(\m{u}_n))\m{u}_n]_j \\\ge&\frac{m}{\|A\m{u}_n\|}\sum_{j=1}^N[(A-f(\m{u}_n))\m{u}_n]_j \\\ge&\frac{m}{M}\|(A-f(\m{u}_n))\m{u}_n\| \end{align*}

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

\begin{align*} \frac{[A\m{u}_{n+1}]_i}{[\m{u}_{n+1}]_i} \ge f(\m{u}_n)+\frac{m}{M}\|(A-f(\m{u}_n))\m{u}_n\| \end{align*}

が分かる.よって,

\begin{align*} f(\m{u}_{n+1}) \ge f(\m{u}_n)+\frac{m}{M}\|(A-f(\m{u}_n))\m{u}_n\| \end{align*}

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

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

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

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

Step 3

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

[Step 3の証明]

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

\begin{align*} \alpha\m{u}'^T\m{u} =\m{u}'^T(\alpha\m{u}) =\m{u}'^T(A\m{u}) =(A^T\m{u}')^T\m{u} =(\lambda\m{u}')^T\m{u} =\lambda\m{v}^T\m{u} \end{align*}

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

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

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

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

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

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

\begin{align*} 0<&\m{u}'^T\m{u} \\=&\m{u}'^T(A\m{w}-\alpha\m{w}) \\=&(A^T\m{u}')^T\m{w}-\alpha\m{u}'^T\m{w} \\=&(\lambda\m{u}')^T\m{w}-\alpha\m{u}'^T\m{w} =0 \end{align*}

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

Step 4

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

[Step 4の証明]

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

\begin{align*} \mu\m{u}'^T\m{v}' =\m{u}'^T(\mu\m{v}') =\m{u}'^T(A\m{v}') =(A^T\m{u}')^T\m{v}' =(\alpha\m{u}')^T\m{v}' =\alpha\m{u}'^T\m{v}' \end{align*}

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

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

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

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

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

\begin{align*} \mu\m{v}' =A\m{v}' =\frac{1}{a}A\m{u} =\frac{\alpha}{a}\m{u} =\alpha\m{v}' \end{align*}

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

Step 5

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

[Step 5の証明]

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

\begin{align*} \sum_{j=1}^Na_{ij}\abs{[\m{z}]_j} \ge\abs{\sum_{j=1}^Na_{ij}[\m{z}]_j} =\abs{[A\m{z}]_i} =\abs{[\beta\m{z}]_i} =|\beta|\abs{[\m{z}]_i} \end{align*}

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

\begin{align*} \alpha\sum_{j=1}^N[\m{u}']_j\abs{[\m{z}]_j} =&\sum_{j=1}^N[\alpha\m{u}']_j\abs{[\m{z}]_j} =\sum_{j=1}^N[A^T\m{u}']_j\abs{[\m{z}]_j} \\=&\sum_{j=1}^N\bra{\sum_{i=1}^Na_{ij}[\m{u}']_i}\abs{[\m{z}]_j} =\sum_{i=1}^N\bra{\sum_{j=1}^Na_{ij}\abs{[\m{z}]_j}}[\m{u}']_i \\\ge&\sum_{i=1}^N\bra{|\beta|\abs{[\m{z}]_i}}[\m{u}']_i =|\beta|\sum_{i=1}^N[\m{u}']_i\abs{[\m{z}]_i} \end{align*}

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

\begin{align*} A(e^{-i\theta}\m{z}) =e^{-i\theta}A\m{z} =e^{-i\theta}\beta\m{z} =\beta(e^{-i\theta}\m{z}) \end{align*}

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

[証明終]

参考文献

線型代数入門 (齋藤正彦 著,東京大学出版会)

線形代数の教科書として半世紀に渡って売れ続けている超ロングセラーの教科書.

本書が発行されて以来,多くの教科書が本書を真似て書かれてきたといっても過言ではないほど,日本の線形代数の指導方針にインパクトを与えた名著である.

「線型代数をとりあえず使えるようにするための教科書」ではなく,「線形代数を理解するための教科書」である.

そのため,論理的に非常に詳しく書かれているのが特徴である.

内容のレベルも数学系の学部生であれば,確実に理解しておきたい.

【参考記事:【書評】線型代数入門(齋藤正彦著,東京大学出版会)

関連記事

【SPONSORED LINK】

シェアする

  • このエントリーをはてなブックマークに追加

フォローする

コメント

  1. TT より:

    解説ありがとうございます。
    証明を追っていていくつかわからないところがありますので、教えていただけないでしょうか。

    1)u_0は全ての成分が1のベクトルではないのですか?
    2)MAの全成分の和となっていますが、step2の証明の3行目の不等式の右側を見ると、Aの行和の最大値となっていると思います。どちらが正しいでしょうか?

    • yama-taku より:

      ご指摘をありがとうございます.

      (1) u_{0}\|\cdot\|ノルムが1,すなわちu_0の最大の成分が1の正ベクトルとするべきなので,仰るように例えばu_0=(1,\dots,1)などとするのが良いですね.
      (2) 正しくは不等式です.行和の最大値よりも,全ての成分の和の方が大きいので,

          \begin{align*} \max\limits_{i\in\{1,\dots,N\}}\bra{\dsum_{j=1}^{N}a_{ij}\|u_{n}\|} =\max\limits_{i\in\{1,\dots,N\}}\bra{\dsum_{j=1}^{N}a_{ij}} \le M \end{align*}

      となりますね.

      誤りを修正しました.

記事一覧は

こちら

Twitterを

フォロー

大学院入試

解答例