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

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

歴史的には

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

の順に示されました．

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

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

フロベニウスの定理を例題から解説｜正方行列と多項式と固有値

正方行列Aと多項式f(x)に対し，行列f(A)の固有値を求めるときに便利な定理として，フロべニウスの定理があります．Aの固有値が分かれば，f(A)の固有値は直ちに得られます．この記事では，フロべニウスの定理の証明をしています．

Perron-Frobeniusの定理
Perron-Frobeniusの定理の証明
参考文献
1. 線型代数入門

Perron-Frobeniusの定理

この記事では

全ての成分が正(非負)の行列を正行列(非負行列)
全ての成分が正(非負)のベクトルを正ベクトル(非負ベクトル)

ということにします．

冒頭にも書いたように，[Perron-Frobeniusの定理]は

正行列の場合
非負行列の場合

の２通りあります．

正行列の場合は以下の通りです．

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

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

一方，条件を非負行列に弱めると，以下のように結論が少し弱くなります．

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

$A$は非負の固有値をもち，そのうちで最大のものを$\alpha$とすれば，$A$の任意の固有値の絶対値は$\alpha$以下である．
固有値$\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$次単位行列

とし，６ステップに分けて証明します．

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

証明を表示

[１]　$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)$を得る．

[２]　関数$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})$を得る．

[１]と[２]を併せて，$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$の重複度は１である．

証明を表示

$\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$の固有空間の次元が１でないと仮定すると，固有値$\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}’$は成分の少なくとも１つが$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$の固有空間の次元は１だから，$A$のJordan標準形の固有値$\alpha$に関するJordan細胞$J(\alpha)$の個数は１である．

もし，$J(\alpha)$の次数が２以上であれば，$\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)$の次数は１である．すなわち，$\alpha$の重複度は１である．

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*}$