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

どうも、木村（@kimu3_slime）です。

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

非負行列、正行列
ペロン・フロベニウスの定理
こちらもおすすめ

非負行列、正行列

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

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

例えば、

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

は正行列で、

\[ \begin{aligned} \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} \end{aligned} \]

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

特に上に挙げた例では、各列のすべての成分の和が\(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{aligned} (Ax)_i &=\sum _{k=1}^n a_{ik}x_k \\& \geq \varepsilon \sum_ {k=1}^n x_k \\& \geq \varepsilon x_i \ \end{aligned} \]

となるので、\(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{aligned} A(Ax)&>&A(\alpha x)\\&=\alpha Ax\end{aligned} \]

を満たします。そして、\(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{aligned} |\lambda||x| &= |Ax| \\ & \leq\sum _{k=1}^n a_{ik}|x_k|\\ & \leq A|x| \end{aligned} \]

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

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

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

木村すらいむ（@kimu3_slime）でした。ではでは。