ペロン・フロベニウスの定理|成分が正の行列の最大固有値

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

歴史的には

  • 成分が正の行列に対する場合(Oskar Perron)
  • 成分が非負の行列に対する場合(Ferdinand Georg Frobenius)

の順に示されました.

この[Perron-Frobeniusの定理]は工学から経済学まで非常に広く応用されます.

なお,多項式に行列を代入したときの固有値に対する[Frobeniusの定理]は別の定理で,これについては以下を参照してください.

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根といいます.

また,$\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\in\{1,\dots,N\}}|[\m{x}]_i|$
  • $I$を$N$次単位行列

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

Step 1

漸化式$\m{u}_{n+1}=\frac{A\m{u}_n}{\|A\m{u}_n\|}$をみたす$\R^N$の正ベクトルの列$\{\m{u}_n\}_{n=0}^{\infty}$が存在する.また,このとき,任意の$n\in\N$に対して$\|\m{u}_{n}\|=1$である.


$\m{u}_0:=[1,\dots,1]^{T}\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}_k}{\|A\m{u}_k\|} \end{align*}

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

また,任意の$n\in\N_{\ge0}$に対して

\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

関数$f:{\R_{>0}}^N\to\R$を

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

で定める.このとき,$\alpha:=\lim\limits_{n\to\infty}f(\m{u}_n)$が存在し,$\alpha>0$が成り立つ.


[1] $A$は正行列だから

\begin{align*} M:=\sum_{i,j=1}^{N}a_{ij},\quad m:=\min_{i,j\in\{1,\dots,N\}}a_{ij} \end{align*}

はいずれも正である.また,任意の$n\in\N$をとる.

$\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\}}\sum_{j=1}^{N}a_{ij}[\m{u}_n]_j \\\le&\max\limits_{i\in\{1,\dots,N\}}\sum_{j=1}^{N}a_{ij} \le M \end{align*}

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

  • $0<[\m{u}_{n+1}]_i\le1$
  • $(A-f(\m{u}_n)I)\m{u}_n$が非負ベクトル

であることに注意すれば

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

が成り立つことが分かる.

よって,この左辺において$\min\limits_{i\in\{1,\dots,N\}}$をとって

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

となるから$f(\m{u}_{n+1})>f(\m{u}_n)$を得る.

[2] 関数$F:{\R_{>0}}^N\to\R$を

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

で定める.ベクトル$F(\m{u}_n)\m{u}_n-A\m{u}_n$の第$i$成分 ($i=1,\dots,N$)は

\begin{align*} [F(\m{u}_n)\m{u}_n-A\m{u}_n]_i =&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*}

だから$F(\m{u}_n)\m{u}_n-A\m{u}_n$は非負ベクトルである.よって,これに左から正行列$\frac{A}{\|\m{x}\|}$をかけてできる$F(\m{u}_n)\m{u}_{n+1}-A\m{u}_{n+1}$は非負ベクトルである.

よって,この第$i$成分($i=1,\dots,N$)を考えると

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

だから,この右辺で$\max\limits_{i\in\{1,\dots,N\}}$をとれば$F(\m{u}_n)\ge F(\m{u}_{n+1})$を得る.

[1]と[2]を併せて,$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*}

が成り立つ.

よって,実数列$\{f(\m{u}_n)\}$は上に有界な非減少列だから,極限$\alpha:=\lim\limits_{n\to\infty}f(\m{u}_n)$が存在する.

また,任意の$n\in\N$に対して$0<f(\m{u}_0)\le f(\m{u}_n)$だから,$\alpha>0$である.

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

Step 3

$\alpha$は$A$の固有値で,固有値$\alpha$に属する正の固有ベクトルが存在する.


[Step 2]で得られた

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

の左辺で極限$n\to\infty$をとると

\begin{align*} \lim_{n\to\infty}\{f(\m{u}_{n+1})-f(\m{u}_n)\} =\alpha-\alpha =0 \end{align*}

なので,$\frac{m}{M}\|(A-f(\m{u}_n)I)\m{u}_n\|>0$と併せると,はさみうちの原理より

\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$をみたすから$\m{u}\neq\m{0}$である.

このとき,$\brb{(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*}

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

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

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

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$なので$\anb{\m{v},\m{u}}\neq0$である.よって,$\alpha=\lambda$が成り立つ.

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

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

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

よって,$\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 4]での$A^T$の固有値$\alpha$の固有ベクトル$\m{v}$を考えると

\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$が成り立つ.

Step 6

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


$\m{z}$を$A$の固有値$\beta$に属する固有ベクトルとする:$A\m{z}=\beta\m{z}$, $\m{z}\neq\m{0}$.

このとき,$A\m{z}=\beta\m{z}$の第$i$成分について,三角不等式を用いると

\begin{align*} \sum_{j=1}^{N}a_{ij}\abs{[\m{z}]_j} =&\sum_{j=1}^{N}\abs{a_{ij}[\m{z}]_j} \ge\abs{\sum_{j=1}^{N}a_{ij}[\m{z}]_j}\quad\dots(*) \\=&\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\quad\dots(**) \\=&|\beta|\sum_{i=1}^{N}[\m{v}]_i\abs{[\m{z}]_i} \end{align*}

となる.$\m{z}\neq\m{0}$と$\m{v}$が正ベクトルであることから$\sum_{i=1}^N[\m{v}]_i\abs{[\m{z}]_i}\neq0$なので$\alpha\ge|\beta|$が従う.

よって,あとは$\alpha\neq|\beta|$を示せばよく,これを背理法により示す.

もし$\alpha=|\beta|$であれば,$(**)$で等号が成り立つから$(*)$でも等号が成り立つ.

一般に,複素数$\xi_1,\dots,\xi_n$に対して三角不等式$\abs{\sum_{k=1}^{n}\xi_k}\le\sum_{k=1}^{n}|\xi_k|$で等号が成り立つのは$\arg{\xi_1}=\dots=\arg{\xi_n}$の場合に限るから,$\m{z}$の各成分の偏角は全て等しい(ただし,偏角は$[-\pi,pi)$に定める).

$\m{z}$の各成分の偏角を$\theta$とすると

\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$は固有ベクトル$e^{-i\theta}\m{z}$を持つ.

また,$A$は正行列だから$A(e^{-i\theta}\m{z})$は正ベクトルなので,$e^{-i\theta}\m{z}$は正ベクトルだから[Step 5]から$\beta=\alpha$となる.

これは仮定$\beta\neq\alpha$に矛盾するから$\alpha=|\beta|$は誤りで$\alpha>|\beta|$が従う.

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

参考文献

線型代数入門

(齋藤正彦 著,東京大学出版会)

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

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

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

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

内容は理論系(特に数学系)の学部生であれば,確実に理解しておきたいレベルです(非理論系の人はここまで必要ないかもしれません).

なお,本書については,以下の記事で書評としてまとめています.

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

参考になった方は是非シェアをお願いします!

フォローする

関連記事

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

記事一覧は

こちら

Twitterを

フォロー

大学院入試

解答例

大学受験

解説ブログ