非負行列・正行列のペロン・フロベニウスの定理とは、証明

どうも、木村(@kimu3_slime)です。

今回は、非負行列・正行列、ペロン・フロベニウスの定理とは何か、その証明を紹介します。

 

非負行列、正行列

ペロン・フロベニウスの定理は、非負行列・正行列と呼ばれる行列の固有値に関する主張です。

成分がすべて非負であるような行列を非負行列(nonnegative matrix)、すべて正であるような行列を正行列(positive matrix)と呼びます。

例えば、

\[ \begin{pmatrix} 0.8 & 0.3\\0.2 & 0.7 \end{pmatrix}\]

は正行列で、

\[ \begin{pmatrix} 0 & \frac{1}{3} & 1 & 0 & 1 \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 \\0 & \frac{1}{3} & 0 & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{3} & 0 & 0 & 0  \end{pmatrix} \]

は非負行列です。当然、すべての正行列は非負行列です(逆は成り立ちません)。

特に上に挙げた例では、各列のすべての成分の和が\(1\)になっています。このような非負行列は、確率行列(stochastic matrix)、マルコフ行列(Markov matrix)と呼ばれるものです。

非負行列や正行列は、行列をかけることを状態の変化とみなすことで、幅広い応用を持っています。

参考:なぜ線形代数を学ぶ? Googleのページランクに使われている固有値・固有ベクトルの考え方なぜ線形代数を学ぶか:人々の移動予測とマルコフ過程なぜ線形代数を学ぶ? 経済波及効果の分析を例に

 

非負行列・正行列という用語は、正定値行列・半正定値行列と似ていますが、全くの別物なので注意しましょう。非負行列は行列の各成分に注目した言葉で、正定値行列はそこから定まる2次形式の符号を意識した言葉です。

 

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

非負行列・正行列が応用されているのは、その固有値が特別な特徴を持っているからでしょう。

例えば上に挙げた確率行列は、どちらも固有値1を持ち、その固有ベクトルの成分はすべて非負となっていました。これは偶然ではなく、次のように一般化されます。

ペロン・フロベニウスの定理(Perron–Frobenius theorem)

\(A\)を正行列とする。次のことが成り立つ。

  • 次のような正の実数の固有値\(\lambda_{\mathrm{PF}}>0\)が存在する。
    1. \(\lambda_{\mathrm{PF}}\)の代数的重複度は1(単純固有値)。 特に、対応する固有空間は1次元である。
    2. \(A\)のすべての固有値\(\lambda\)の大きさは、それ以下である\(|\lambda| \leq \lambda_{\mathrm{PF}}\)。(\(A\)のスペクトル半径は\(\lambda_{\mathrm{PF}}\))

この\(\lambda_{\mathrm{PF}}\)を\(A\)のペロン・フロベニウス固有値(Perron–Frobenius eigenvalue)、支配的固有値(dominant eigenvalue)という。

正行列でなく非負行列についても同様の主張が成り立つ。

 

正行列について証明していきましょう。非負行列については齋藤「線型代数入門」を参照。

結論から言うと、ペロン・フロベニウス固有値は、非負ベクトル\(x \neq 0\)に対して何度も\(A\)をかけていった\(A^k x \)の極限として見つけることができます(べき乗法)。

 

\(L:=\{t \in \mathbb{R} \mid ある正のx によりAx \geq tx が成り立つ\}\)という集合を考えましょう。

この実数の集合\(L\)は、空でなく、上に有界です。なぜか。

\(\varepsilon := \min _{i,j}a_{ij}\)と置くと、\(\varepsilon \in L\)が言えます。\(A\)は正行列なので、\(\varepsilon>0\)です。各成分を計算すると、

\[\begin{eqnarray} (Ax)_i &=&\sum _{k=1}^n a_{ik}x_k \\&\geq& \varepsilon \sum_ {k=1}^n x_k \\&\geq& \varepsilon x_i \end{eqnarray} \]

となるので、\(Ax \geq \varepsilon x\)がわかりました。

同様の議論で、\(Ax \leq \|A\|_1 x\)なので、\(L\)は上に有界です。(\(\|A\|_1\)は絶対値ノルム

実数の公理より、\(L\)は上限を持ちます。\(\alpha :=\sup L\)と置くと、\(\varepsilon>0\)より\(\alpha >0\)です。

 

\(\alpha \in L\)、つまり\(Ax \geq  \alpha x\)を満たす\(x\)が存在することを示しましょう。

上限の定義より、\(n\)を大きく取ると\(\alpha – \frac{1}{n} \in L\)です。したがって、\(Ax[n] \geq (\alpha-\frac{1}{n})x[n]\)を満たす\(x[n]\)が存在します。両辺を\(\|x[n]\| \)で割ることで、\(\|x[n]\|=1\)と正規化しておくことができます。ここで、点列\((x[n])_{n=1}^\infty\)は有界なので、収束する部分列を持ちます(ボルツァーノ・ワイエルシュトラスの定理)。その極限を\(x\)とすると、不等式において極限を取れば、\(Ax \geq \alpha x\)が得られました。

さらに、\(Ax =\alpha x\)が成り立っています。背理法として、仮に\(Ax >\alpha x\)としましょう。\(A\)が正行列であるから、

\[\begin{eqnarray}  A(Ax)&>&A(\alpha x)\\&=&\alpha Ax\end{eqnarray}\]

を満たします。そして、\(Ax\)は非負です。真の不等号が成り立っていることから、\(A(Ax) \geq (\alpha+\delta)x\)となる\(\delta >0\)が存在します。よって、\(\alpha+\delta \in L\)。これは\(\alpha\)が\(L\)の上限であることに矛盾しました。

 

固有値\(\alpha\)に対応する固有ベクトル\(y\)は、その定数倍しかないことを確かめましょう。

\(x\)を\(Ax =\alpha x\)を満たし、\(y- cx \neq 0 \)であるような任意の正のベクトルとします。\(A(y-cx)=\alpha y -c \alpha x =\alpha(y-cx)\)なので、\(y-cx\)は\(\alpha\)に対する固有ベクトルです。左辺は\(A\)が正行列であることからすべての成分が正です。\(c\)を大きくしたとき、\(y-cx \)のある成分は0となります。\(A(y-cx)=\alpha (y-cx)\)において、0であり0でない成分が存在することになり、矛盾しました。

よって、固有値\(\alpha\)に対応する固有空間は1次元で、代数的重複度はそれ以下なので1です。

 

固有値の大きさを確かめましょう。

\(Ax= \lambda x\)を満たすとします。絶対値を取ると、三角不等式から

\[ \begin{eqnarray} |\lambda||x| &=& |Ax| \\ &\leq&\sum _{k=1}^n a_{ik}|x_k|\\ &\leq& A|x| \end{eqnarray}\]

となります。\(|x|\)は非負のベクトルで\(A|x|\geq |\lambda| x\)を満たすので、\(|\lambda| \in L\)です。\(L\)の上限が\(\alpha \)だったので、\(|\lambda| \leq \alpha\)が言えました。

 

以上、非負・正行列とは何か、ペロン・フロベニウスの定理とその証明を紹介してきました。

成分がすべて正の行列には、正の固有値が必ずあって、対応する固有ベクトルも正になります。

ステップを踏んで変化していく現象を行列のべき乗と\(A^k x\)と見立てたとき、最大の固有値が\(1\)か、それ以上か、それ以下かによって最終的な状態は大きく変わってきます。そんな議論がしやすい行列として、非負・正行列を意識してみてはいかがでしょうか。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

明解演習 線形代数 (明解演習シリーズ)
平治, 小寺(著)
共立出版 (1982-07-09T00:00:01Z)
5つ星のうち4.0
¥788 (中古品)

 

世界標準MIT教科書 ストラング:線形代数イントロダクション
ギルバート ストラング(著), 松崎 公紀(翻訳), 新妻 弘(翻訳)
近代科学社 (2015-12-22T00:00:01Z)
5つ星のうち4.6
¥14,721 (コレクター商品)

 

基礎数学1線型代数入門

基礎数学1線型代数入門

posted with AmaQuick at 2021.05.20
齋藤正彦(著)
東京大学出版会 (2019-03-08T00:00:00.000Z)
5つ星のうち4.3
¥1,870

 

こちらもおすすめ

なぜ線形代数を学ぶ? Googleのページランクに使われている固有値・固有ベクトルの考え方

なぜ線形代数を学ぶか:人々の移動予測とマルコフ過程

なぜ線形代数を学ぶ? 経済波及効果の分析を例に

pノルムとは:絶対値ノルム、最大値ノルム、同値なノルム

lim 1/n=0はなぜ? ε-n_0論法とアルキメデスの性質