2020/07/26 12:05 更新
Perron-Frobenius根の性質
436 いいね ブックマーク
目次

前提知識


本題

主定理の紹介

今回は,既約な非負行列のPerron-Frobenius根に関する次の性質を取り上げます.

定理 1. $A$を周期が$\sigma$であるような既約な非負行列とする.このとき,$A$の固有値$\lambda$であって,$\left|\lambda\right| = \rho(A)$となるものはちょうど$\sigma$個しかない.

ここで$\rho(A)$は$A$のスペクトル半径で,$A$の固有値の絶対値の最大値を指します.
ちなみにこの$\sigma$個の固有値は

$$\begin{aligned} \lambda^{(k)} = \rho(A) \mathrm{e}^{2 \pi \mathrm{i} k/\sigma}, && \text{($k \in \left\{ 0, \dots, \sigma-1 \right\}$) } \end{aligned}$$

で尽くされることが知られています.

証明のための準備

さて, 定理1. の証明を始めます.まずは特別な場合から始めましょう.

命題 2. $A$を周期が$1$であるような既約な非負行列とする.このとき,$A$の固有値$\lambda$であって,$\left|\lambda\right| = \rho(A)$となるものはちょうど$1$個 (Perron-Frobenius根) しかない.

証明.
既約な非負行列に対するPerron-Frobeniusの定理より,$\rho = \rho(A)$は$A$の単純固有値.
$A$の周期が1なので,

$$\exists M \in \mathbb{N},\; A^{M} > 0.$$

この$A^{M}$の任意の固有値$\lambda^{\prime}$はある$A$の固有値$\lambda$の$M$乗に等しいので,正行列に対するPerron-Frobeniusの定理から,$\rho^{M}$は$A^{M}$の単純固有値であり,また,その他の固有値の絶対値は$\rho^{M}$より真に小さくなる.つまり,$A$のPerron-Frobenius根でない任意の固有値$\lambda$について $\left|\lambda\right|^{M} < \rho^{M}$.これより$\left| \lambda \right| < \rho$である.証明終.



大事な部分をすべて既存の定理に押し付けてしまう華麗な (?) 技でした.
ここでのポイントは 既約かつ周期が$1$の非負行列であれば,何乗かすれば正行列になる ということです.
既約な正方行列について周期が$1$であることを「原始的 (primitive) 」というのでした.


詳細は割愛しますが,一般の周期$\sigma$の既約な非負行列に対しては次の 命題3.補題4. が成立します.

命題 3. $A$が周期$\sigma$の既約な非負行列であるとき,ある置換行列$P$が存在して,$P^{\top} A P$は次のような形をもつ.:

$$P^{\top} A P = \begin{pmatrix} O & A_{1} & \\ \vdots & & A_{2} \\ \vdots &&&\ddots \\ O &&&&A_{\sigma-1} \\ A_{\sigma} & O & \cdots & \cdots &O \end{pmatrix}$$

ここで,$A_{1}, \dots, A_{\sigma}$は既約かつ原始的な非負行列.

補題 4. 命題3. の状況で,$A_1 \cdots A_\sigma$は既約かつ原始的な非負行列である.

これらは行列に対応するグラフ上で周期の概念を考えると理解できます.今回はその証明を割愛します.命題3. のような行列の形を$\sigma$-巡回的 ($\sigma$-cyclic) というようです.


さて,置換行列は直交行列なので,$P^{\top} A P$の固有値は$A$の固有値と重複度を含めて完全に一致します.:

$$\det (P^{\top} A P - \lambda I) = \det (A - \lambda I).$$

そのため, 定理1. を考えるときに初めから$A$は 命題3. に示したような形をしていると仮定しても差し支えありません.

以上を踏まえて定理1.の証明に向かいましょう.


主定理の証明

証明.
周期が$\sigma$の既約な非負行列$A$を考える.但し,$A$は 命題3. に示したような$\sigma$-巡回的な行列であると仮定する.計算により,

$$A^{\sigma} = \begin{pmatrix} A_1 \cdots A_\sigma & \\ & A_2 \cdots A_1 & \\ && \ddots \\ &&& A_\sigma \cdots A_{\sigma-1} \end{pmatrix}$$

と分かる.これは周期が$\sigma$であることの意味をグラフ的に捉えても理解できる.

このブロック対角行列について$A_1 \cdots A_\sigma$の非零の固有値を$\lambda_1, \dots, \lambda_t$とする.但し,重複している場合はその個数分だけ$\lambda_{*}$に含める.

このとき,例えば$A_1 \cdots A_\sigma$の非零固有値$\lambda_i$に属する固有ベクトル$\bm{x}^{(i)}$をとり,$\bm{y}^{(i)} = A_\sigma \bm{x}^{(i)}$とおくと,

$$\begin{aligned} &A_1 A_2 \cdots A_\sigma \bm{x}^{(i)} = A_1 \cdots A_{\sigma-1} \bm{y}^{(i)} = \lambda_i \bm{x}^{(i)}, \\ &A_\sigma A_1 \cdots A_{\sigma - 1} \bm{y}^{(i)} = A_{\sigma} (\lambda_i \bm{x}^{(i)}) = \lambda_i \bm{y}^{(i)}. \end{aligned}$$

つまり,$A_{\sigma} A_{1} \cdots A_{\sigma -1}$も固有値$\lambda_{i}$を持つ.このことは他の行列$A_{k} \cdots A_{k-1}$ (※巡回的な積) に対しても同様なので,結局,$A^{\sigma}$の対角ブロックに現れる各ブロック行列は$\lambda_{1}, \dots, \lambda_{t}$だけを固有値にもつと分かる.更に

$$\begin{aligned} \det (A^{\sigma} - \lambda I) &= \det \begin{pmatrix} A_1 \cdots A_{\sigma} - \lambda I & & \\ & \ddots & \\ & & A_{\sigma} \cdots A_{\sigma-1} - \lambda I \end{pmatrix} \\ &= \prod_{i=1}^{\sigma} \det (A_i \cdots A_{i-1} - \lambda I) \end{aligned}$$

であるから,$A^{\sigma}$の非零固有値は$\lambda_{1}, \dots, \lambda_{t}$により構成される.

ここで$A$の固有値を$\mu_{1}, \dots, \mu_{\ell}$とすれば$A^{\sigma}$の固有値はこれらの積のどれかにならざるを得ないので,逆に言えば,$A$の非零固有値は

$$\begin{aligned} \lambda_1^{1/\sigma},&&\lambda_1^{1/\sigma}\omega_{\sigma},&&\cdots,&&\lambda_1^{1/\sigma}\omega_{\sigma}^{\sigma-1}, \\ \lambda_2^{1/\sigma},&&\lambda_2^{1/\sigma}\omega_{\sigma},&&\cdots,&&\lambda_2^{1/\sigma}\omega_{\sigma}^{\sigma-1}, \\ \vdots&&&&\vdots \\ \lambda_t^{1/\sigma},&&\lambda_t^{1/\sigma}\omega_{\sigma},&&\cdots,&&\lambda_t^{1/\sigma}\omega_{\sigma}^{\sigma-1} \end{aligned}$$

のどれかになっている.ここに$\omega_{\sigma}$は$\mathrm{e}^{2 \pi \mathrm{i} /\sigma}$とする.

ここで,$\rho$を$A$の固有値のうち絶対値が最大のものとすると,これは非零の固有値である.また,$\rho^{\sigma}$は$A^{\sigma}$の非零固有値であるから,一般性を欠かずに$\lambda_1 = \rho^{\sigma}$であるとしてよい.

補題4. に示したように$A_1 \cdots A_\sigma$は既約かつ原始的である.よって,既約な非負行列に対するPerron-Frobeniusの定理より,$\rho^{\sigma}$は$A_1\cdots A_\sigma$の単純固有値である.

少し補足です.$A$のPerron-Frobenius根以外の固有値を$\lambda$とおくと,$\left| \lambda \right| \le \rho$が成り立ちます.これらの$\sigma$乗は$A^{\sigma}$の固有値になるので,$\left| \lambda^{\sigma} \right| \le \rho^{\sigma}$が成り立ちます.先に述べたように$A^{\sigma}$の固有値と$A_{1} \cdots A_{\sigma}$の固有値は値としては一致するので,この不等式を$A_{1} \cdots A_{\sigma}$の固有値に関する不等式とみれば,$\rho^{\sigma}$が$A_{1} \cdots A_{\sigma}$のPerron-Frobenius根であることが分かります.

そして,命題2. (原始的な場合に限った主定理) より,$\lambda_2, \dots, \lambda_t$については絶対値が$\rho^{\sigma}$より真に小さいことが分かる.:

$$\forall i > 1,\; \left| \lambda_i \right| < \rho^{\sigma}.$$

$A$の固有値はみなその大きさが$\left| \lambda_{i} \right|^{1/\sigma}$に等しいため,$A$の固有値であって,$\rho$と絶対値が同じものは,$\lambda_{1}^{1/\sigma}$を回転させた形をもつ高々$\sigma$個しかない.

ところで,冒頭に述べたようにこのような固有値は常に$\sigma$個は存在する.以上より,主張が従う.証明終.


跋文

今回のテーマは夏学期に受けた講義の中で生まれた疑問から始まりました.
講義後に「OK, google」とSiriに呼びかけAIに不機嫌になられながらもいくつかの文献を検索して最終的に上に述べた主張を使ってその疑問を解決しました.あの時は,私の質問の仕方が悪かったために方々にご迷惑をおかけした気がしてなりませんが,最終的に丁寧な回答をいただけたので非常に良かったです.

今回ここに記した証明は,特に 補題4. を使ったあたりから何をしているのか煩雑で意味が分からなくなりそうだと感じますから,初めから公式にいただいた回答を参考にしたほうが良かったかもしれないですね……


参考文献

[1] Helene Shapiro: Linear Algebra and Matrices: Topics for a Second Course (Pure and Applied Undergraduate Texts) , AMS, Providence, Rhode Island, 2015.
[2] Wikipedia: ペロン=フロベニウスの定理, URL: https://ja.wikipedia.org/wiki/ペロン=フロベニウスの定理