Perron-Frobenius 정리 (강의 참고자료)

이 내용은 Worcester Polytechnic Institute의 John. Goulet 교수의 응용부분을 이상구 교수의 강의록에 보태어 마련하였다.

학생들에게 도움이 되는 자료로 쓰이기를 바란다.

서 론

 

 선형대수학과 관련된 많은 예를 보면 그 응용분야가 얼마나 넓은가를 알 수 있다. 특히 실제 사회문제에 대한 수학적 모델에 대응되는 행렬은 거의 모두 성분 모두가 음이 아닌 "Nonnegative 행렬"이고, 또한 분석에는 nonnegative 행렬의 고유값들(eigenvalues)이 매우 유용하게 쓰인다. 우리는 여기서 그러한 고유값들 중에서 dominant하는(가장 큰)고유값에 대해서 좀 더 깊이 알 필요가 있다. 실제로 10×10 행렬의 인구모델에서조차도 행렬의 모든 고유값을 구하기 위해 각종 소프트웨어를 이용하는데 어려움을 자주 겪는다. 그러나 대개의 인구모델 문제에서는 10개의 고유값 중 가장 큰 고유값이 전체 결론에 결정적인 역할을 하고 그것에 대한 연구로 충분히 찾고자 하는 결론을 이끌어 낼 수 있다. 이 과정에서 "어떻게 dominant 고유값을 구하고", "어떻게 그 값이 양수인지를 알 수 있으며", 또한 "크기가 같은 (양수이건 음수이건 복소수이건) 다른 고유값은 존재하는가?" 등등의 문제를 생각해볼 수 있다. 이 문제들에 대한 답은 "nonnegative 행렬의 Perron-Frobenius정리"에 의하여 주어진다. nonnegative 행렬의 성질을 연구하는 방법으로 "irreducible"행렬과 "primitive"행렬의 경우를 구분하여 서술하겠다.

 


 본 론

 

Irreducibility

 

[정 의]

다음의 예를 통해서 irreducibility에 대해서 좀더 알아보도록 하자.

 

1. Markov Chains

 를 Markov Chain의 transition 행렬이라고 할 때, 그 성분

         = 상태 에서 상태 로 가는 확률.

 다시 말해서 성분 상태에서 상태로 변할 확률을 뜻하며, 가령 행렬의 한 행을 보았을 때, 예를 들어 행렬 의 4행은 상태 4 에서 여러 다른 상태로 변하는 확률들을 나열한 것을 의미한다. (물론 상태 4에 머무르는 경우도 포함.)

4행의 어떤 성분이 0일 경우는 4번 상태에서부터 적어도 한 경우는 변하지 않는 것을 의미한다.

만약 다음과 같은 행렬 가 reducible이라면, 예로

 

상태 (to)      1  2   3  4  5     상태 (from)

               

 

와 같다고 하자. 이 경우, 상태 1, 2, 3은 어떤 상태로도 변할 수 있지만, 4, 5번 상태는 서로 간에만 변화가능하다는 것을 의미한다. 이런 행렬의 반복적인 곱을 관찰함으로 주어진 조건의 상태가 일정한 기간 후에 어떻게 변하는지를 보는 것이 Markov chain의 전통적인 방법이다.

 

다음의 문제를 통해서 Markov chain을 이해해보자.

 

[문제]

[풀이]

 

이와 같은 해석과정을 Markov chain이라고 부른다.

 

2. Graphs

  우리가 directed graph를 생각할 때, 그에 대응하는 nonnegative 행렬 A의 () 성분을 만일 vertex 에서 로의 arc가 존재할 때는 1로 하고 arc 가 존재하지 않으면 0으로 정의하면 A는 (0,1) 행렬이 된다.

   이때 행렬 A가 irreducible이면 임의의 vertex에서 임의의 다른 vertex로 여러 단계를 거쳐서라도 모두 이어질 수 있고, reducible이면(Markov Chain의 경우처럼) 어떤 경우에는 한 점에서 다른 점으로 이동할 수 없다는 것을 증명한다.

 

  Note : 행렬 A가 irreducible의 경우는 graph 이론에서 A의 diagraph가 "strongly connected"라는 조건과 동치이다.

 

3. Dynamical Systems

   가령 인구모델에서 다음과 같은 system을 얻을 수 있다.

 그리고, A가 reducible이면 이 관계를 부분행렬들을 이용하여 다음과 같이 표현할 수 있다.

 

 

 즉, 의 처음 r행, 의 나머지 n-r행을 의미한다.

 

 이제 "nonnegative 행렬이 irreducible일 필요충분조건에 관한 정리"를 우선 살펴보고 이에 관련하여 Perron-Frobenius 정리를 자세히 서술하도록 하자.

 

[정리]

 

  

Perron-Frobenius 정리 (Lecture Note of Prof. S.-G.Lee)

 

[Def]

 

즉, 위의 이 nonnegative irreducible matrix 의 maximal ev임을 보일수 있다.

다음 이에 대응하는 는 positive vector임을 보일 수 있고 더 보태어, 이 simple(중근이 없는) ev 임을 알 수 있다.

 

이 수 에 대한 연구가 Perron-Frobenius 정리이다.

 

[Lemma]

[Pf.]

  

[Note]

 

[Def]

 

[Note]

 

[Def]

 

[Remark]

 

이것을 Frobenius가 nonnegative (irreducible) matrix로 확장했는데, 그것을 위한 정의와 fact가 여기에 서술될 것이다.

 

[Thm] (Perron-Frobenius 정리 Part I)

[Pf.]

 

[Exs.]

[Pf.]

 

[Thm]

[Pf.]

 

[요약]

 

 

Primitive 행렬에 대한 Perron-Frobenius 정리

 

[Def.]

 

[Proposition]

 

[Thm] (Perron-Frobenius Theorem for Primitive Matrices)

 

Other Applications

 

Application #1 : Raking of Football Teams.

Utah 대학 수학과의 James P. Keener 교수는 대학 미식축구 팀의 ranking에 대한 아래의 모델을 제시하였다.

  그 논문을 살펴보면 다음의 흥미로운 문제가 소개되었다.

  거기서는 "실력이 같지 않은 2팀씩의 게임에서 팀의 ranking을 다루는 네 가지 방법을 소개하였고, 각각의 방법이 Perron-Frobenius 정리를 어떻게 적용하는가"를 보였다. 가령 첫번째 방법은 다음과 같다.

⑴       ( : 팀에 대한 score

                         : 팀의 능력을 측정한 값

                         : 팀과 팀과의 게임에서 얻은 nonnegative 정보

                         : 총 경쟁하는 팀의 수

                         : 팀이 하는 게임의 수   )

각 팀의 능력 값인 은 score 에 비례한다고 가정할 때, Perron-Frobenius 정리에서 , 를 이용하면 주어진 경기의 정보를 얻을 수 있다.

그러나 이 방법은 몇 가지 단점을 가지고 있다. 가령 아주 강한 팀이 약한 팀들과 경기를 할 경우, 이 결과로는 적당한 ranking을 얻을 수 없다. 따라서 우선 ⑴의 식을 다음과 같은 식으로 바꿔본다.

⑵     

        : 단조증가인 연속함수 with )

세 번째, 네 번째 방법은 팀이 팀을 이길 확률을 이용하여 least square method 와 maximum 값 추정 등의 방법을 쓴다. 이런 식으로 ranking을 정할 때 nonnegative 행렬에 관한 성질이 이용될 수 있다.

 

Application #2 : Graphs

그래프의 개념에서 그래프의 cycle들의 length(길이)에 대한 결과는 그에 대응하는 adjacency 행렬이 primitive인지 아닌지에 따라 결정된다.

 

⑴ 만약 행렬이 primitive이면(dominant 고유값 이 다른 모든 고유값들보다 크면) 모든 cycle들의 length의 gcd(최대공약수)는 1이다.

 

⑵ 만약 행렬이 irreducible 이지만 primitive는 아니라면, 모든 cycle들의 length의 gcd(최대공약수)는 dominant 고유값 과 크기가 같은 고유값들의 수와 같다.

irreducible지만 primitive는 아닌 행렬을 imprimitive라고도 하는데, 여기서 gcd는 그래프의 index를 뜻한다. 다시 말해서 dominant 고유값인 과 크기가 같은 index의 수만큼의 개수의 고유값이 반지름이 인 복소 평면상의 원 위에 같은 거리를 가지고 위치한다는 것을 의미한다.

 


 

 결 론

 

 Perron-Frobenius정리는 이산모델에서 생긴 nonnegative 행렬을 연구하는데 강력한 결과이다. 또한 그 행렬이 irreducible인지 primitive인지에 따른 결과를 주의 깊게 살펴야 한다. dominant 고유값과 고유벡터는 매우 유용하고 구하기가 쉬운데 반해 "spectral radius" 이외의 값들은 상대적으로 불필요하고 구하기도 어렵다. 따라서 우리 주위의 수학적 모델의 성질을 이해하는데 nonnegative 행렬에 대한 주요 정리인 Perron-Frobenius 정리가 어떻게 이용될 수 있는지를 알 수 있었다.

 


 

 참고서적


 Typed by T.A. Yang Jeong Mo at June 2000 under Prof. S.-G. Lee's  supervision.

 Home    ⓒ 2000 Prof. S.G.Lee, Dept. of Math of SungKyunKwan University