페론-프로베니우스 정리

수치해석 통계 마지막 수정: 2026-08-02 05:41:26

1. 개요[편집]

행렬의 성분이 전부 음이 아니라는 것, 그 하나만으로 최대 고유값의 운명이 결정된다.

페론-프로베니우스 정리(Perron–Frobenius theorem)는 성분이 음이 아닌 정사각행렬에 대해 스펙트럼 반경이 그 자체로 실수 고유값이고, 대응하는 고유벡터를 전부 양수 성분으로 잡을 수 있다는 정리다. 대칭성도, 양정부호성도, 정규성도 요구하지 않는다. 요구하는 것은 오직 비음수성과 연결성뿐이다. 이 얄팍해 보이는 가정에서 마르코프 연쇄의 정상분포 존재·유일성, 거듭제곱법의 안전성, 페이지랭크의 well-posedness, 인구 모형의 안정 연령분포가 전부 따라 나온다.

역사적으로는 페론이 1907년에 성분이 모두 양수인 행렬에 대해 증명했고, 프로베니우스가 1912년에 비음수 기약행렬로 일반화하면서 주기성이라는 미묘한 층까지 밝혀냈다. 오늘날 응용에서 쓰이는 형태는 거의 전부 프로베니우스 버전이다.

2. 정확한 진술[편집]

$A \ge 0$ 을 성분별 부등식으로 쓰고, 스펙트럼 반경을 $r = \rho(A) = \max_i \lvert \lambda_i \rvert$ 라 하자.

(페론) $A > 0$ 인 경우. $r > 0$ 은 $A$ 의 고유값이고 대수적 중복도 1의 단순 고유값이다. 대응하는 좌·우 고유벡터를 성분이 모두 양수가 되게 잡을 수 있고, 다른 모든 고유값은 $\lvert\lambda\rvert < r$ 을 만족한다. 즉 유일한 최대다.

(프로베니우스) $A \ge 0$ 이고 기약(irreducible)인 경우. 기약이란 유향그래프 $G(A)$ (성분 $a_{ij}>0$ 일 때 $i\to j$ 간선)가 강연결이라는 뜻이다. 이때도 $r>0$ 은 단순 고유값이고 고유벡터는 양수다. 그러나 최대 크기 고유값이 하나뿐이라는 보장은 사라진다. 각 정점에서 자신으로 돌아오는 닫힌 경로 길이들의 최대공약수를 $h$ (주기)라 하면, 크기가 정확히 $r$ 인 고유값이 $h$ 개 있고 그것들은

\lambda_k = r\,e^{2\pi i k/h}, \qquad k = 0,1,\dots,h-1

로 복소평면 원 위에 정확히 균등 배치된다. 더 나아가 스펙트럼 전체가 $2\pi/h$ 회전에 대해 불변이다.

**원시(primitive)**란 $h=1$ , 동치로 어떤 $k$ 에 대해 $A^k > 0$ 인 경우다. 이때 비로소 페론의 결론이 전부 회복된다 — 최대 고유값이 유일하고 $\lvert\lambda_2\rvert < r$ .

$h=2$ 인 대표 예가 이분그래프의 인접행렬이다. 스펙트럼이 $\pm$ 쌍으로 나오고 $\lambda_{\min} = -\lambda_{\max}$ 가 되는 이유가 이 정리에 정확히 적혀 있다.¹

3. 마르코프 연쇄가 곧 이 정리의 응용[편집]

행 합이 전부 1인 확률행렬 $P$ 는 $P\mathbf{1} = \mathbf{1}$ 이므로 $r = 1$ 임이 즉시 나온다. 프로베니우스를 적용하면 좌 고유벡터 $\pi P = \pi$ 가 양수 성분으로 존재하고 정규화하면 유일한 정상분포가 된다. 여기서 교과서가 마르코프 연쇄에 요구하는 두 조건의 정체가 드러난다.

기약성 = 상태그래프가 강연결 = 프로베니우스 가정 그 자체.
비주기성 = $h=1$ .

기약 + 비주기 = 원시성이고, 원시성이야말로 $P^n \to \mathbf{1}\pi^\top$ 수렴을 보장하는 조건이다. 주기 $h=2$ 인 연쇄(예: 이분그래프 위 무작위걷기)는 정상분포가 여전히 유일하지만 $P^n$ 이 두 극한 사이를 영원히 진동한다. “왜 비주기성이 필요한가”에 대한 가장 정직한 답은 “고유값 $-1$ 이 살아 있어서”다.

수렴 속도는 두 번째 고유값이 정한다. $\lVert \mu P^n - \pi\rVert \sim \lvert\lambda_2\rvert^n$ 이므로

\text{스펙트럼 갭} \;=\; 1 - \lvert\lambda_2\rvert

가 클수록 빨리 섞인다. 혼합시간이 대략 $1/(1-\lvert\lambda_2\rvert)$ 스케일이라는 것이 마르코프 연쇄 몬테카를로 이론의 출발점이며, 임계점 근처에서 갭이 0으로 닫히는 것이 임계 감속(critical slowing down)의 정체다. 은닉 마르코프 모형의 전이행렬 역시 원시적이어야 장기 예측이 의미를 갖는다.

4. 응용 목록[편집]

페이지랭크. 웹 링크 행렬은 기약도 원시도 아니다(막다른 페이지, 고립된 덩어리). 감쇠계수 $\alpha=0.85$ 로 균일 순간이동을 섞어 $G = \alpha P + (1-\alpha)\frac{1}{n}\mathbf{1}\mathbf{1}^\top$ 을 만드는 조작은 성분을 전부 양수로 만들어 페론 조건을 강제로 성립시키는 장치다. 덤으로 $\lvert\lambda_2\rvert \le \alpha$ 라는 상한까지 얻어 반복 횟수를 예측할 수 있게 된다. 상세는 해당 문서로.
레온티예프 투입산출 모형. 투입계수 행렬 $A\ge0$ 에 대해 최종수요 $d$ 를 만족하는 산출 $x=(I-A)^{-1}d$ 가 비음수로 존재할 필요충분조건이 $\rho(A)<1$ 이다. 경제학의 “생산 가능성”이 스펙트럼 반경 조건으로 번역된다.
레슬리 행렬. 연령별 생존율·출산율로 짜인 인구 투영행렬의 최대 고유값이 곧 개체군의 점근 성장률 $\lambda$ 이고, 우고유벡터가 안정 연령분포, 좌고유벡터가 각 연령의 번식가치다. 초기 분포가 뭐든 시간이 지나면 우고유벡터 방향으로 수렴한다는 것이 정리의 직접 결과다.
전달행렬법과 이징 모형 1D 정확해. 1차원 이징 사슬의 분배함수는 $2\times2$ 양행렬 $T$ 에 대해 $Z_N = \mathrm{Tr}\,T^N = \lambda_+^N + \lambda_-^N$ 이고, $N\to\infty$ 에서 $\lambda_+$ 만 살아남아 자유에너지가 $-k_BT\ln\lambda_+$ 가 된다. 페론에 의해 $\lambda_+$ 는 단순하고 매개변수에 대해 해석적이므로 유한온도에서 특이점이 생길 수 없다. 1차원에 상전이가 없다는 정리의 가장 깔끔한 증명이 페론-프로베니우스다.²
거듭제곱법. $\lvert\lambda_1\rvert > \lvert\lambda_2\rvert$ 여야 수렴하는데, 일반 행렬에서 이걸 사전에 보장할 방법이 없다. 원시 비음수 행렬은 가정만으로 이 부등식이 공짜로 따라오는 거의 유일한 큰 부류다. 웹·소셜 그래프에서 거듭제곱법이 그냥 되는 이유가 요행이 아니라 정리다.

5. 무엇이 보장되지 않는가[편집]

실무에서 사고가 나는 지점은 대부분 가정을 넘겨짚는 데서 온다.

부호가 섞이면 전부 무효. 성분에 음수가 하나라도 들어가면 최대 고유값이 복소수일 수도, 중복일 수도, 고유벡터가 부호 혼합일 수도 있다. “대충 비슷하니까 되겠지”가 통하지 않는다. 상관행렬·차분행렬처럼 음수 성분이 있는 행렬에 이 정리를 갖다 대는 것은 오류다.
양정부호성과는 무관하다. 비음수 행렬은 대칭일 필요조차 없고, 대칭 비음수 행렬이 준양정부호일 이유도 없다. 두 개념은 서로 포함관계가 없다.
기약성 없이는 단순성이 깨진다. 블록 대각 구조(가약행렬)에서는 최대 고유값이 여러 블록에서 동시에 나와 중복이 되고, 고유벡터에 0 성분이 생긴다. 그래프가 강연결인지부터 확인하는 것이 순서다.
조건수를 개선해 주지는 않는다. 최대 고유값이 잘 분리돼 있어도 나머지 스펙트럼이 뭉쳐 있으면 아놀디 알고리즘 같은 크릴로프 방법의 수렴은 여전히 나쁠 수 있다. 대칭이 아니므로 란초스 알고리즘을 그대로 쓸 수도 없고 비대칭 계열로 가야 한다.

대비해 두면 좋은 것이 스펙트럴 군집화와 피들러 벡터다. 그래프 라플라시안 $L = D - W$ 에서 흥미로운 정보는 가장 작은 비자명 고유값 쪽에 있고, 그 고유벡터는 반드시 부호가 섞인다(첫 고유벡터 $\mathbf{1}$ 과 직교해야 하므로). 여기 페론-프로베니우스는 최대 쪽 이야기다. 다만 무관하지 않다 — $L$ 의 최소 고유쌍은 $cI - L \ge 0$ 의 최대 고유쌍과 같으므로, 이동(shift)으로 비음수 행렬을 만들어 두 세계를 이어 붙일 수 있다. 라플라시안 최소 고유값 0이 단순할 조건이 “그래프가 연결”인 것도 결국 같은 기약성 논리다.

6. 콜라츠-비란트로 값을 조이기[편집]

정리는 존재만 말하지 않는다. 임의의 양벡터 $x>0$ 에 대해

\min_i \frac{(Ax)_i}{x_i} \;\le\; r \;\le\; \max_i \frac{(Ax)_i}{x_i}

이 성립하고, 실제로 $r = \max_{x>0}\min_i (Ax)_i/x_i$ 라는 변분 특성이 있다. 이것이 콜라츠-비란트 부등식이다. 실용적으로 강력한데, $x=\mathbf{1}$ 을 넣으면 곧바로 “최소 행합 $\le r \le$ 최대 행합”이라는 공짜 구간이 나오고, 거듭제곱법 반복 벡터를 넣으면 반복마다 $r$ 을 위·아래에서 동시에 조이는 구간이 갱신된다. 잔차 노름으로 수렴을 판정하는 것과 달리 이건 보장된 포함구간이라, 조기 종료해도 값의 범위를 말할 수 있다.³ 두 경계의 폭이 곧 현재 벡터가 페론 벡터에서 얼마나 벗어났는지의 척도이므로 정지 조건으로도 쓸 만하다.⁴

7. 관련 문서[편집]

그래서 이분그래프인지 아닌지를 인접행렬 스펙트럼만 보고 판정할 수 있다. 스펙트럼이 원점 대칭이면 이분, 아니면 아니다. 그래프를 그려 보지 않고 고유값만으로 알아내는 몇 안 되는 구조 정보. ↩
여기서 유혹이 하나 생긴다. “그럼 2차원도 전달행렬 쓰면 되잖아?” 된다. 다만 2D의 전달행렬은 크기가 $2^L$ 로 폭발하고, 온사게르가 1944년에 그걸 실제로 대각화해서 상전이를 증명했다. 그 논문이 통계역학 역사상 가장 읽기 어려운 계산 중 하나로 꼽히는 데는 이유가 있다. ↩
강의에서는 “존재 정리라 계산에는 못 쓴다”고 넘어가는 경우가 많은데, 콜라츠-비란트는 그야말로 세 줄짜리 코드로 구현되는 실전 도구다. 거듭제곱법 루프 안에 min/max 두 줄 추가하면 끝난다. ↩
물론 실전에서 가장 흔한 사고는 정리를 오해하는 게 아니라 행렬이 사실 비음수가 아니었던 것이다. 데이터에서 만든 인접행렬에 음수 가중치가 몇 개 섞여 있는데 그걸 모르고 페론 벡터를 뽑아 “중요도 순위”라고 발표하는 일. 그럴 때 순위표에는 음수 점수가 조용히 앉아 있다. ↩