非負行列についてのPerron-Frobeniusの定理

はてブ上での $\TeX$ の練習と授業の復習を兼ねて.

定義1(強連結). $G = (E, V)$ を有効グラフとする. 任意の $u, v \in V$ について, $u, v$ をそれぞれ始点, 終点とする有向道が存在するとき, $G$ は強連結であるという.

定義2(既約行列). $A \in \mathbb{R}^{n \times n}$ とする. グラフ $G = (E, V)\ (V = \left\{1, 2, \cdots, n\right\})$ であって, $A$ の $(i, j)$ 成分が非零であるときに限り $i$ から $j$ へと向かう辺をもつようなものを考えたとき, $G$ が強連結となるならば, $A$ は既約行列であるという.

定理1. $A \in \mathbb{R}^{n \times n}$ を既約非負行列とする. このとき, $(I + A)^{n - 1}$ は正行列となる.

証明. 任意の零でない非負ベクトル $\boldsymbol{x}$ について, $(I + A)^{n - 1}\boldsymbol{x} \gt 0$ であることを示せば十分である. $\boldsymbol{x} = \left[\boldsymbol{x_1}\ \boldsymbol{0}\right]^\top\ (\boldsymbol{x_1} \in \mathbb{R}^k, \boldsymbol{x_1} \geq 0)$ としても一般性を失わない. また, $A$ は非負行列であるから, $A_{11} \in \mathbb{R}^{k \times k}, A_{21} \in \mathbb{R}^{(n - k) \times k}, A_{12} \in \mathbb{R}^{k \times (n - k)}, A_{22} \in \mathbb{R}^{(n - k) \times (n - k)}$ を非負行列として

$A = \begin{bmatrix}A_{11}\ A_{12} \\A_{21}\ A_{22}\end{bmatrix}$

とかける. $\boldsymbol{y} = (I + A)\boldsymbol{x}$ として, $\boldsymbol{y} = \left[\boldsymbol{y_1}\ \boldsymbol{y_2}\right]^\top\ (\boldsymbol{y_1} \in \mathbb{R}^k, \boldsymbol{y_2} \in \mathbb{R}^{n - k})$ とおくと

$\boldsymbol{y} = \begin{bmatrix}\boldsymbol{y_1} \\ \boldsymbol{y_2}\end{bmatrix} = \begin{bmatrix}\boldsymbol{x_1} \\ \boldsymbol{0}\end{bmatrix} + \begin{bmatrix}A_{11}\ A_{12} \\A_{21}\ A_{22}\end{bmatrix}\begin{bmatrix}\boldsymbol{x_1} \\ \boldsymbol{0}\end{bmatrix} = \begin{bmatrix}\boldsymbol{x_1} + A_{11}\boldsymbol{x_1} \\ A_{21}\boldsymbol{x_1}\end{bmatrix}$

となる. これより, $\boldsymbol{y_1} \gt 0$ である. また, $A$ の既約性より, $A_{21} \neq O$ であり( $A_{21} = O$ とすると, $i \in \left\{k + 1, k + 2, \cdots, n\right\}$ から $j \in \left\{1, 2, \cdots, k\right\}$ への有向道が存在しないことになり, 既約性に反する), これと $\boldsymbol{x_1} \gt 0$ より, $A_{21}\boldsymbol{x_1} \neq 0$ である. ゆえに, $\boldsymbol{y}$ は $\boldsymbol{x}$ より正の成分の個数が少ない. $\boldsymbol{x}$ は零でない非負ベクトルであったから, $(I + A)^{n - 1}\boldsymbol{x} \gt 0$ となる. $\square$

定理2(Perron-Frobeniusの定理). $A \in \mathbb{R}^{n \times n}$ を既約非負行列とする. このとき, $A$ は正の固有値であって, 正ベクトルを固有ベクトルとするものをもつ.

証明. 非負ベクトル $\boldsymbol{x}$ について, $\mu(\boldsymbol{x}) = \max\left\{\lambda \mid A\boldsymbol{x} \geq \lambda\boldsymbol{x}\right\}$ とおくと

$\displaystyle \mu(\boldsymbol{x}) = \min_{i}\left\{\frac{(A\boldsymbol{x})_i}{x_i} \ \middle|\ x_i \gt 0\right\}$

となる. $S = \left\{\boldsymbol{x} \mid \boldsymbol{x} \geq 0, \|\boldsymbol{x}\| = 1\right\}, \alpha = \sup\left\{\mu(\boldsymbol{x}) \mid \boldsymbol{x} \geq 0, \boldsymbol{x} \neq 0 \right\}$ とすると, $c\ (c \neq 0)$ について $\mu(c\boldsymbol{x}) = \mu(\boldsymbol{x})$ より

$\displaystyle \alpha = \sup_{\boldsymbol{x} \in S} \mu(\boldsymbol{x})$

となる. ここで, $\boldsymbol{1} = \left[1\ 1\ \cdots\ 1\right]^\top \in \mathbb{R}^n$ , $A$ の $(i, j)$ 成分を $a_{ij}$ とすれば

$\displaystyle \mu(\boldsymbol{1}) = \min_i \sum_{j = 1}^n a_{ij} \gt 0$

となる. ただし, 上式の不等号は $A$ の既約性より成り立つ. ゆえに, $\alpha \geq \mu(\boldsymbol{1}) \gt 0$ が成り立つ. また, $S$ 上の点列 $\left\{\boldsymbol{x_k}\right\}_{k \in \mathbb{N}}$ であって, $\lim_{k \to \infty}\boldsymbol{x_k} = \alpha$ となるようなものがとれるが, $S$ は有界閉集合であるから, 点列コンパクトであり, 収束部分列 $\left\{\boldsymbol{x_{k(l)}}\right\}_{l \in \mathbb{N}}$ がとれて, $\lim_{l \to \infty}\boldsymbol{x_{k(l)}}$ は $S$ の元となる.