페론-프로베니우스 정리 (Perron-Frobenius theorem)

개요

• A = (a_ij) 가 n × n 양행렬, 즉  1 ≤ i, j ≤ n  에 대하여 a_ij > 0 가 성립한다고 가정하자
• 다음이 성립한다
  
  • A의 고유값 \(r>0\) 이 존재하여, 다른 고유값 λ에 대하여 부등식 |λ| < r가 성립한다.
    
  • r 에 대응되는 고유벡터공간은 1차원이다
    
  • r에 대응되는 모든 성분이 양수인 고유벡터 v = (v₁,…,v_n) 가 존재한다. 즉 A v = r v,  1 ≤ i ≤ n 에 대하여 v_i > 0 이 성립하도록 하는 v를 찾을수 있다
    

 

예

카르탄 행렬 \(\mathcal{C}(A_5)\) 의 역행렬은

\(\left( \begin{array}{ccccc} \frac{5}{6} & \frac{2}{3} & \frac{1}{2} & \frac{1}{3} & \frac{1}{6} \\ \frac{2}{3} & \frac{4}{3} & 1 & \frac{2}{3} & \frac{1}{3} \\ \frac{1}{2} & 1 & \frac{3}{2} & 1 & \frac{1}{2} \\ \frac{1}{3} & \frac{2}{3} & 1 & \frac{4}{3} & \frac{2}{3} \\ \frac{1}{6} & \frac{1}{3} & \frac{1}{2} & \frac{2}{3} & \frac{5}{6} \end{array} \right)\)로 양행렬이다.

이 행렬의 고유값은 \(2+\sqrt{3},1,\frac{1}{2},\frac{1}{3},2-\sqrt{3}\)로 주어진다.

벡터 \(\left( \begin{array}{c} 1 \\ \sqrt{3} \\ 2 \\ \sqrt{3} \\ 1 \end{array} \right)\) 는 고유값이 \(2+\sqrt{3}\)인 고유벡터이다.

 

 

 

브라우어 부동점 정리의 응용

\(A\geq 0\) : non-negative 행렬

\(\sigma(A)\) : A 의 스펙트럼, 즉 A의 고유값의 집합 \(\sigma(A)=\{\lambda_1,\cdots, \lambda_{k}\}\)

\(\rho(A)\) : A 의 spectral radius, \(\{|\lambda_1|,\cdots, |\lambda_{k}|\}\) 에서의 최대값

\(\|\mathbf{x}\|_{1}\) : L^1-norm of x, 즉 \(\mathbf{x}=(x_1,\cdots, x_k)\) 이면, \(\|\mathbf{x}\|_{1}=|x_1|+\cdots+|x_k|\)

 

(정리)

\(\rho(A)\) 는 A의 고유값이며, \(\mathbf{x}\geq 0\) 인 고유벡터가 존재한다.

 

(증명)

\(K =\{\mathbf{x}\in\mathbb{R}^n|\mathbf{x}\geq 0,\|\mathbf{x}\|_{1}=1, A\mathbf{x}\geq \rho(A)\mathbf{x}\}\) 라 두자.

\(\lambda\) 를 \(|\lambda|=\rho(A)\) 를 만족시키는 A의 고유값이라 하고, \(\mathbf{v}\) 를 대응되는 고유벡터라 두자. \(\|\mathbf{v}\|_{1}=1\) 로 둘 수 있다.

\(\rho(A)|\mathbf{v}|=|\lambda \mathbf{v}|=|A \mathbf{v}|\leq A|\mathbf{v}|\) 이므로, \(|\mathbf{v}|\in K\) 이고, K는 공집합이 아니다.

따라서 K는 compact, convex, non-empty.

 

이제 두 가지 경우로 나눌 수 있다.

(1) \(A\mathbf{x} = 0\) 인 \(\mathbf{x}\in K\)가 존재하는 경우

(2) 모든 \(\mathbf{x}\in K\) 에 대하여 \(A\mathbf{x} \neq 0\) 가 성립하는 경우

 

(1) 의 경우는, \(\rho(A)=0\) 이 되어 증명이 끝난다.

(2) 의 경우를 생각하자.

\(f : K\to \mathbb{R}^{n}\) 을 \(f(\mathbf{x})=\frac{A\mathbf{x}}{\|A\mathbf{x}\|_1}\) 로 정의하자.

\(f(\mathbf{x})\geq 0\), \(\|f(\mathbf{x})\|_{1}=1\) 임을 쉽게 알 수 있다. 또한,

\(Af(\mathbf{x})=\frac{A (A\mathbf{x})}{\|A\mathbf{x}\|_1}\geq \frac{A (\rho(A)\mathbf{x})}{\|A\mathbf{x}\|_1}=\rho(A)f(\mathbf{x})\) 이므로, \(f(K)\subseteq K\).

 

따라서 브라우어 부동점 정리 에 의해, \(f(\mathbf{y})=\mathbf{y}\) 인 \(\mathbf{y}\in K\) 가 존재한다.

\(f(\mathbf{y})=\frac{A\mathbf{y}}{\|A\mathbf{y}\|_1}=\mathbf{y}\) 이므로, \(\|A\mathbf{y}\|_1=r\) 로 두면, \(A\mathbf{y}=r\mathbf{y}\) 이다. 

또한 \(\mathbf{y}\in K\) 이므로, \(A\mathbf{y}=r\mathbf{y}\geq \rho(A)\mathbf{y}\). 

따라서 \(r=\rho(A)\)은 A의 고유값이며, \(\mathbf{y}\geq 0\) 는 대응되는 고유벡터이다. ■

 

 

역사

 

• http://www.google.com/search?hl=en&tbs=tl:1&q=
• 수학사 연표

 

 

메모

• http://people.ciram.unibo.it/~sgallari/Meetings/Matrix_day/benzi.ps

 

관련된 항목들

• inverse positive matrix
• 브라우어 부동점 정리

 

매스매티카 파일 및 계산 리소스

• https://docs.google.com/file/d/0B8XXo8Tve1cxTGpWWGN0dGhudUU/edit?pli=1

   

사전 형태의 자료

• http://en.wikipedia.org/wiki/Perron–Frobenius_theorem
• http://en.wikipedia.org/wiki/Nonnegative_matrix

 

리뷰, 에세이, 강의노트

• Hawkins, Thomas. 2008. “Continued Fractions and the Origins of the Perron–Frobenius Theorem.” Archive for History of Exact Sciences 62 (6) (November 1): 655–717. doi:10.1007/s00407-008-0026-x.
• http://www.imsc.res.in/~sunder/pf.pdf
  
  • 페론-프로베니우스 in graph theory, fusion algebra, ...

 

관련논문

• Costa, Robert, Patrick Dynes, and Clayton Petsche. “A P-Adic Perron-Frobenius Theorem.” arXiv:1509.01702 [math], September 5, 2015. http://arxiv.org/abs/1509.01702.
• Meyer, Carl D. “Continuity of the Perron Root.” Linear and Multilinear Algebra, July 3, 2014, 1–5. doi:10.1080/03081087.2014.934233.

 

관련도서

• Henryk Minc, Nonnegative matrices, John Wiley&Sons, New York, 1988, ISBN 0-471-83966-3