페론-프로베니우스 정리｜모든 성분이 음수가 아닌 기약 행렬은 모든 성분이 양수인 고유값과 고유벡터를 가진다.

모든 성분이 음수가 아닌 정사각 행렬 $A$에 대해서 각 성분 $A_{ij}$마다 $A^k_{ij}$가 양수인 $k_{ij}$를 잡을 수 있으면 irreducible이라 하고 $A^k$의 모든 성분이 양수인 $k$를 잡을 수 있으면 primitive라 한다. $\R^n$보다 일반적인 벡터 공간에서는

• $A_{ij}\neq 0$일 때 node $i$에서 node $j$로 잇는 digraph를 생각하여, 각 edge의 방향을 따라서 두 node 사이에 어떤 것이 목적지인지에 관계없이 언제나 경로를 줄 수 있으면 irreducible matrix이다.
• $A$의 symmetric permutation $P^TAP$가 정사각 행렬들로 이루어진 block upper triangular matrix가 되게 하는 permutation matrix $P$를 잡을 수 있을 때 irreducible matrix이다.
• nonnegative matrix $A$가 irreducible이고 maximum eigenvalue가 하나이면 primitive matrix이다. 즉 $A^k$가 aperiodic이어야 primitive matrix가 될 수 있다.

모든 성분이 음수가 아닌 $n\times n$ 행렬 $A$에 대해서 $A^k_{ij}$는 index $c$들에 대해서 $a_{ic_1}a_{c_1c_2}\cdots a_{c_{k-1}j}$와 같이 나타나는 곱셈들의 모든 합이므로 $A$로 만든 digraph를 생각할 때 node $i$에서 node $j$로 가는 경로가 있으면 $A^{k}_{ij}>0$이다. 따라서 $A$가 irreducible matrix이면 그러한 $k<n$가 있어야 하므로 $\displaystyle (A+I)^{n-1}_{ij}=\sum_{k}{n-1 \choose k}A_{ij}^k>0$이다. 이 $A$에 대해서 다음 Perron–Frobenius theorem이 성립한다:

• $A$는 모든 성분이 양수인 고유벡터를 가진다. 이는 양수인 고유값 $\lambda$에 대응하는 고유벡터이다.
• $A$의 모든 고유값의 길이는 $\lambda$와 같거나 그보다 작다.
• 모든 성분이 음수가 아닌 벡터 $x\neq 0$들의 집합을 positive orthant(분면)라 한다. 이 제1 $2^n$분면에 속하는 열벡터 $x$와 scalar $\mu$에 대해서 $Ax$의 모든 성분이 $\mu x$와 같거나 그보다 작으면 $x$의 모든 성분은 $0$보다 크고 $A$의 positive maximum eigenvalue $\lambda$는 $\mu$와 같거나 그보다 작다. $Ax\leq \lambda x$를 만족하는 $x$들은 $\lambda$에 대응하는 고유벡터들뿐이다. 따라서 모든 성분이 음수가 아닌 $A$의 고유벡터들은 모두 $\lambda$의 고유공간에 있다.
• 모든 성분이 음수가 아닌 행렬 $B\neq A$의 모든 성분이 $A$와 같거나 그보다 작을 때 $B$의 모든 고유값의 길이는 $\lambda$보다 작다. 예를 들어 $A$의 같은 index의 행과 열을 $0$으로 대체한 행렬의 고유값의 길이는 $\lambda$보다 작다.
• $\lambda$는 simple eigenvalue이다.
• $A$가 primitive matrix이면 $A$의 $\lambda$가 아닌 모든 고유값의 길이는 $\lambda$보다 작다.

증명

행렬 또는 벡터 $A$의 각 성분이 모두 행렬 또는 벡터 $B$와 같거나 그보다 작을 때 $A\leq B$로, 모두 $B$보다 작을 때 $A<B$로 쓰고, 행렬 또는 벡터 $A$의 각 성분에 모두 절댓값을 씌운 것을 $|A|$라 쓰겠다. positive orthant의 벡터 $p$에 대해서

$L(p)=\max\{\lambda \mid Ap \geq \lambda p \}=\min\{(Ap)_i/p_i\mid p_i\neq 0\}$

이라 하면 모든 $c>0$에 대해서 $L(cp)=L(p)$이다. $(A+I)^{n-1}$는 모든 성분이 양수이고 $(A+I)^{n-1}A=A(A+I)^{n-1}$이다. $Ap\geq \lambda p$이면 $A(A+I)^{n-1}p \geq \lambda(A+I)^{n-1}p$이고 따라서 $L((A+I)^{n-1}p)\geq L(p)$이다. 두 벡터 $a,\ b$에 대해서 $a\leq b$이고 $a\neq b$일 때 행렬 곱셈에 따라서 모든 성분이 양수인 행렬 $P$를 양변에 곱하면 $Pa<Pb$이므로 $L(p)p\neq Ap$이면 $L(p)(A+I)^{n-1}p<A(A+I)^{n-1}p$에서 $L((A+I)^{n-1}p)>L(p)$이다. $L(p)p=Ap$이면 $L(p)$는 $A$의 eigenvalue이고 $p$는 $L(p)$에 대응하는 eigenvector이다.

positive orthant와 unit sphere의 intersection을 $C_p$라 할 때 이는 compact set이고 image $(A+I)^{n-1}(C_p)$는 모든 원소의 모든 성분이 양수이다. 함수 $L$은 이 image에서 continuous function이므로 $L((A+I)^{n-1}(C_p))$는 최댓값을 가진다. 모든 $c>0$에 대해서 $L((A+I)^{n-1}p)\geq L(cp)$이므로 $(A+I)^{n-1}(C_p)$에서 $L(p)$의 최댓값은 positive orthant 전체에서 $L(p)$의 최댓값이다. 즉 $x\in C_p$에서 그러한 최댓값이 $L(x)$일 때 $L((A+I)^{n-1}x)=L(x)$이다. 이는 $L(x)x=Ax$를 의미하므로 $(A+I)^{n-1}x=(L(x)+1)^{n-1}x>0$에서 $x>0$이고, $A$가 irreducible matrix이므로 $x>0$일 때 $Ax>0$이어서 $L(x)>0$이다. $Ap=\lambda p$이면 $\displaystyle \sum_j A_{ij}|p_j|\geq \left|\sum_j A_{ij}p_j\right|=|\lambda||p_i|$이므로 $L(|p|)\geq |\lambda|$이고 $A$의 모든 고유값의 길이는 $L(x)$와 같거나 그보다 작다. $L(x)=0$이면 모든 고유값이 $0$이어서 $A$가 nilpotent가 되고 irreducible이 아니다.

$Ap=\lambda p,\ A^Tp'=\lambda' p'$이면 $p'^T(Ap)=\lambda p'^Tp,\ (p'^TA)p=\lambda' p'^Tp$이고 $\lambda,\ \lambda'$가 $A,\ A^T$의 positive maximum eigenvalue이면 $p'^Tp>0$이므로 $\lambda=\lambda'$이다. 마찬가지로 $Ap\leq \mu p$이면 $p'^TAp=\lambda p'^Tp$이고 $p'^TAp\leq \mu p'^Tp$이므로 $\lambda \leq \mu$이고, $0<(A+I)^{n-1}p\leq (\mu+1)^{n-1}p$이므로 $p>0$이다. $Ap=\mu p$이면 $\lambda=\mu$이고, 역으로 $\mu=\lambda$이면 $p'^TAp=\lambda p'^Tp$이고 $Ap\leq \lambda p$이므로 $p'^T(Ap-\lambda p)=0$에서 $Ap=\lambda p$이다.

$B\leq A$이면 $Bp\leq Ap$이므로 $L_B(p)\leq L_A(p)$이다. 또한 $B\neq A$이고 $Bp=\lambda p$이면 $\displaystyle \sum_j A_{ij}|p_j|\geq \sum_j B_{ij}|p_j|\geq|\lambda||p_i|$이다. 따라서 $L_A(|p|)\geq |\lambda|$이므로 $L_A(x)=|\lambda|$라고 가정하면 $L_A(x)=L_A(|p|)$이다. 즉 $|p|>0$이고 $\displaystyle \sum_j A_{ij}|p_j|= \sum_j B_{ij}|p_j|=|\lambda||p_i|$이어야 하지만 $B\neq A$이므로 $(A-B)|p|=0$일 수 없고 $L_A(x)>|\lambda|$이다.

Jacobi's formula에 의해서 $\displaystyle \frac{d}{d\lambda}\det(\lambda I-A)=\tr\operatorname{adj}(\lambda I-A)$이므로 $A$의 $i$번째 행과 열을 $0$으로 대체한 행렬 $M_{ii}$에 대해서 $\displaystyle \frac{d}{d\lambda}\det(\lambda I-A)=\sum_i \det(\lambda I-M_{ii})$이다. $\lambda=L_A(x)$를 대입하면 각 minor는 양수이어야 하므로 $A$의 특성 다항식의 도함수는 $L_A(x)$를 zero로 가지지 않는다. 따라서 $L_A(x)$는 대수적 중복도와 기하적 중복도가 $1$이다.

$A$의 고유값 $\mu$에 대해서 $|\lambda|^k\neq |\mu|^k$이면 $|\lambda|\neq|\mu|$이므로 $A^1>0$이라고 가정할 수 있다. $\lambda=1,\ |\mu|=1,\ Ax=\mu x$일 때 $|Ax|\leq |A||x|=A|x|$이므로 $|x|\leq A|x|$이다. $A|x|-|x|\neq 0$이라고 가정하면 $A(A|x|-|x|)>0$이므로 $A(A|x|-|x|)>\epsilon A|x|$를 만족하는 $\epsilon>0$을 잡을 수 있다. 따라서 $\displaystyle \frac{A}{\epsilon +1}A|x|>A|x|$이고 $\displaystyle \left(\frac{A}{\epsilon +1}\right)^nA|x|>A|x|$에서 $A$의 eigenvalue의 절댓값이 $1$과 같거나 그보다 작으므로 $n$이 커질수록 좌변은 $0$으로 수렴한다. 즉 $0\geq A|x|$에서 $A|x|=|x|$이어야 하고 $|x|$는 $\lambda=1$에 대응하는 eigenvector이다. 또한 $|Ax|=|x|$이므로 $A|x|=|Ax|$이고 $x$의 모든 성분이 양수이어야 한다. 즉 $|x|=x$이고 $\mu=1$이다.

$A$의 모든 성분이 음수가 아닐 때 각 열과 행들 중에 zero가 있으면 irreducible matrix가 아니다. 따라서 $A$가 primitive matrix이면 $A^k>0$일 때 $A^{k+i}>0$이고 maximum eigenvalue는 하나뿐이다. 이러한 $k$들 가운데 가장 작은 것은 $(n-1)^2+1$과 같거나 그보다 작다. $L(p)=\min\{(Ap)_i/p_i\mid p_i\neq 0\}$는 Collatz–Wielandt formula(콜라츠-빌란트 공식)라 한다. dominant eigenvalue $L_A(x)$는 $A$의 각 열의 합들 가운데 가장 큰 것과 같거나 그보다 작고, 가장 작은 것과 같거나 그보다 크다.

참고 자료

• https://www.math.miami.edu/~armstrong/685fa12/sternberg_perron_frobenius.pdf
• https://arxiv.org/pdf/1306.0729.pdf
• http://kadm.kmath.ru/files/pfproof.pdf