【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に属する正の固有ベクトルが存在する.

これら両方の主張において,固有値\alphaPerron-Frobenius根といいます.

また,\alphaのような最大の固有値を最大固有値ということもあります.

Perron-Frobeniusの定理の証明

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

以下では,

  • A=(a_{ij})N次正方行列
  • ベクトル\m{x}i成分を[\m{x}]_i
  • \m{x}\in\R^Nに対して,\|\m{x}\|:=\max\limits_{i=1,\dots,N}|[\m{x}]_i|
  • IN次単位行列

とし,6ステップに分けて証明します.

Step 1

漸化式\m{u}_{n+1}=\frac{A\m{u}_n}{\|A\m{u}_n\|}をみたす\R^Nの正ベクトルの列\{\m{u}_n\}_{n=0}^{\infty}が存在する.

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

また,\R^Nの正ベクトルの列\{\m{u}_n\}_{n=0}^{k}が定まっているとすると,Aが正行列であることと併せて

\begin{align*} \m{u}_{n+1} :=\frac{A\m{u}_n}{\|A\m{u}_n\|} \end{align*}

も正ベクトルとなる.よって,\R^Nの正ベクトルの列\{\m{u}_n\}_{n=0}^{\infty}が帰納的に定まる.

また,任意のn\in\{0,1,\dots\}に対して

\begin{align*} \|\m{u}_{n+1}\| =\nor{\frac{A\m{u}_n}{\|A\m{u}_n\|}} =\frac{1}{\|A\m{u}_n\|}\|A\m{u}_n\| =1 \end{align*}

をみたす.

のちに,この点列\{\m{u}_n\}が収束して,このときの極限\m{u}Aの固有ベクトルとなることを示します.

Step 2

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

関数f,F:\R^N\to\R

\begin{align*} f(\m{x}):=\min_{j=1,\dots,N}\frac{[A\m{x}]_j}{[\m{x}]_j},\quad F(\m{x}):=\max_{j=1,\dots,N}\frac{[A\m{x}]_j}{[\m{x}]_j} \end{align*}

で定める.

任意にn=0,1,\dotsをとる.このとき,ベクトル

\begin{align*} A\m{u}_n-f(\m{u}_n)\m{u}_n,\quad F(\m{u}_n)\m{u}_n-A\m{u}_n \end{align*}

の第i成分 (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}[\m{u}_n]_i=0, \\& F(\m{u}_n)[\m{u}_n]_i-[A\m{u}_n]_i \ge\frac{[A\m{u}_n]_i}{[\m{u}_n]_i}[\m{u}_n]_i-[A\m{u}_n]_i=0 \end{align*}

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

よって,これらに左から正行列\frac{A}{\|A\m{u}_n\|}をかけてできるベクトル

\begin{align*} A\m{u}_{n+1}-f(\m{u}_n)\m{u}_{n+1},\quad F(\m{u}_n)\m{u}_{n+1}-A\m{u}_{n+1} \end{align*}

も非負ベクトルなので,任意のi=1,\dots,Nに対して,

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

が成り立つ.また,明らかにf(\m{u}_n)\le F(\m{u}_n)だから,

\begin{align*} f(\m{u}_0) \le f(\m{u}_1) \le f(\m{u}_2) \le\dots \le F(\m{u}_2) \le F(\m{u}_1) \le F(\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である.

この\alphaが定理の最大固有値となります.

Step 3

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

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 =&[A\m{u}_{n+1}-f(\m{u}_n)\m{u}_{n+1}]_i \\=&\frac{1}{\|A\m{u}_n\|}[A^2\m{u}_n-f(\m{u}_n)A\m{u}_n]_i \\=&\frac{1}{\|A\m{u}_n\|}[A(A-f(\m{u}_n)I)\m{u}_n]_i \\=&\frac{1}{\|A\m{u}_n\|}\sum_{j=1}^Na_{ij}[(A-f(\m{u}_n)I)\m{u}_n]_j \\\ge&\frac{m}{\|A\m{u}_n\|}\sum_{j=1}^N[(A-f(\m{u}_n)I)\m{u}_n]_j \\\ge&\frac{m}{M}\|(A-f(\m{u}_n)I)\m{u}_n\| \end{align*}

が成り立つ.よって,0<[\m{u}_{n+1}]_i\le1に注意すると

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

が従う.両辺で上極限をとると,

\begin{align*} 0=\alpha-\alpha\ge\varlimsup_{n\to\infty}\frac{m}{M}\|(A-f(\m{u}_n)I)\m{u}_n\| \end{align*}

となって,0\ge\varlimsup\limits_{n\to\infty}\|(A-f(\m{u}_n)I)\m{u}_n\|が分かる.また,もとより

\begin{align*} \varlimsup_{n\to\infty}\|(A-f(\m{u}_n)I)\m{u}_n\| \ge\varliminf_{n\to\infty}\|(A-f(\m{u}_n)I)\m{u}_n\| \ge0 \end{align*}

だから,極限\lim\limits_{n\to\infty}\|(A-f(\m{u}_n)I)\m{u}_n\|が存在して

\begin{align*} \lim_{n\to\infty}\|(A-f(\m{u}_n)I)\m{u}_n\|=0 \end{align*}

が成り立つ.よって,ノルム\|\cdot\|の連続性から

\begin{align*} \lim_{n\to\infty}(A-f(\m{u}_n)I)\m{u}_n=\m{0}\quad\dots(*) \end{align*}

が成り立つ.

いま,\R^Nの単位球面\set{\m{x}\in\R^N}{|\m{x}|=1}は有界閉集合(点列コンパクト)だから,\{\m{u}_n\}_{n=0}^{\infty}の収束部分列\{\m{u}_{n(k)}\}_{k=0}^{\infty}が存在する.

このときの極限を\m{u}とすると,\|\m{u}\|=1をみたす.

このとき,\{(A-f(\m{u}_n)I)\m{u}_n\}_{n=0}^{\infty}の部分列\{(A-f(\m{u}_{n(k)})I)\m{u}_{n(k)}\}_{k=0}^{\infty}の極限は

\begin{align*} \lim_{k\to\infty}(A-f(\m{u}_{n(k)})I)\m{u}_{n(k)} =(A-\alpha I)\m{u}\quad\dots(**) \end{align*}

となる.一般に元の点列の極限が存在すれば,部分列の極限と一致するから,(*)(**)より

\begin{align*} (A-\alpha I)\m{u}=\m{0} \iff A\m{u}=\alpha\m{u} \end{align*}

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

また,\{\m{u}_n\}の定め方から\m{u}は零ベクトルでない非負ベクトルで,Aは正ベクトルだから,A\m{u}は正ベクトルである.

よって,\alpha\m{u}は正ベクトルだから,\alpha>0と併せて\m{u}は正ベクトルであることが分かる.

なお,途中で上極限を考えたのは,普通の極限\lim\limits_{n\to\infty}\|(A-f(\m{u}_n)I)\m{u}_n\|が存在するかどうか定かではないからです.

そこで,

\begin{align*} 0\ge\varlimsup_{n\to\infty}\|(A-f(\m{u}_n)I)\m{u}_n\| \ge\varliminf_{n\to\infty}\|(A-f(\m{u}_n)I)\m{u}_n\| \ge0 \end{align*}

を示すことにより,極限が存在して0であることが分かったというわけですね.

Step 4

固有値\alphaの重複度は1である.

\m{x},\m{y}\in\R^nの標準内積を\anb{\m{x},\m{y}}で表す.

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

\begin{align*} (\alpha-\lambda)\anb{\m{v},\m{u}} =&\anb{\m{v},\alpha\m{u}}-\anb{\lambda\m{v},\m{u}} \\=&\anb{\m{v},A\m{u}}-\anb{A^T\m{v},\m{u}} =0 \end{align*}

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

ここで,固有値\alphaの固有空間の次元が1でないと仮定すると,固有値\alphaの固有ベクトル\m{u},\m{v}\in\R^nが存在して任意a\in\Rに対して\m{u}-a\m{v}\neq\m{0}となる.

\m{u}-0\times\m{v}=\m{u}が正ベクトルであることとスカラー倍の連続性から,あるk>0が存在して\m{u}-k\m{v}の成分の少なくとも1つは0であり,仮定から\m{u}-k\m{v}は零ベクトルではない.

したがって,\alpha(\m{u}-k\m{v})も成分の少なくとも1つは0であり,零ベクトルではない.

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

よって,\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<&\anb{\m{v},\m{u}} \\=&\anb{\m{v},A\m{w}-\alpha\m{w}} \\=&\anb{A^T\m{v},\m{w}}-\alpha\anb{\m{v},\m{w}} \\=&\anb{\lambda\m{v},\m{w}}-\alpha\anb{\m{v},\m{w}} =0 \end{align*}

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

Step 5

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

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

\begin{align*} (\mu-\alpha)\anb{\m{v},\m{v}'} =&\anb{\m{v},\mu\m{v}'}-\anb{\alpha\m{v},\m{v}'} \\=&\anb{\m{v},A\m{v}'}-\anb{A^T\m{v},\m{v}'} =0 \end{align*}

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

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

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

したがって,\alpha(\m{u}-b\m{v}')も成分の少なくとも1つは0であり,他の成分は0以上となる.

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

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

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

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

Step 6

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

固有値\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{v}を用いると,

\begin{align*} \alpha\sum_{j=1}^N[\m{v}]_j\abs{[\m{z}]_j} =&\sum_{j=1}^N[\alpha\m{v}]_j\abs{[\m{z}]_j} =\sum_{j=1}^N[A^T\m{v}]_j\abs{[\m{z}]_j} \\=&\sum_{j=1}^N\bra{\sum_{i=1}^Na_{ij}[\m{v}]_i}\abs{[\m{z}]_j} =\sum_{i=1}^N\bra{\sum_{j=1}^Na_{ij}\abs{[\m{z}]_j}}[\m{v}]_i \\\ge&\sum_{i=1}^N\bra{|\beta|\abs{[\m{z}]_i}}[\m{v}]_i =|\beta|\sum_{i=1}^N[\m{v}]_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 5]から\beta=\alphaとなる.よって,\beta\neq\alphaであれば,\alpha>|\beta|が従う.

以上で正行列に対する[Perron-Frobeniusの定理]が示されましたね.

参考文献

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

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

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

「線型代数をとりあえず使えるようにするための教科書」ではなく「線形代数を理解するための教科書」のため,論理的に非常に詳しく書かれているのが特徴です.

内容のレベルも理論系(特に数学系)の学部生であれば,確実に理解しておきたいところです.

なお,著者の齋藤正彦氏は本書で日本数学会出版賞を受賞しています.

シェアする

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

フォローする

最後までありがとうございました!

以下の関連記事もいかがですか?

SPONSORED LINK
関連記事

記事一覧はこちらからどうぞ!

コメント

  1. TT より:

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

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

    • yama-taku より:

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

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

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

      となりますね.

      誤りを修正しました.

記事一覧は

こちら

Twitterを

フォロー

大学院入試

解答例

大学受験

解説ブログ