거슈고린 원판 정리

1. 개요

거슈고린 원판 정리 Gershgorin Circle Theorem
주장	모든 고유값은 원판 Di = { z : |z − aii| ≤ Ri } 들의 합집합 안에 있다
반지름	Ri = 행 i 의 비대각 성분 절댓값 합 (열 판도 성립)
강화판	k 개 원판의 합집합이 나머지와 떨어져 있으면 그 안에 고유값이 정확히 k 개
발표	S. A. 거슈고린, 1931 (독일어)
뿌리	레비-데플랑크 정칙성 정리 (엄격 대각 우세 ⇒ 정칙)
쓰임	양해법 안정 시간 간격, 고유값 초기 추정, 섭동 한계, 정치성 판정

고유값을 계산하지 않고도 “대충 어디쯤” 있는지 행렬을 쳐다보는 것만으로 안다. 행렬 해석계의 관상학.

거슈고린 원판 정리(Gershgorin circle theorem)는 정사각 행렬 $A = (a_{ij}) \in \mathbb{C}^{n\times n}$ 의 모든 고유값이 복소평면에서 중심 $a_{ii}$, 반지름 $R_i = \sum_{j\ne i} \lvert a_{ij}\rvert$ 인 $n$ 개 원판의 합집합 안에 들어 있다는 정리다. 소련 수학자 세묜 아로노비치 거슈고린(Семён Аронович Гершгорин, 1901–1933)이 1931년 독일어 논문으로 발표했다.

계산 비용은 행렬을 한 번 훑는 $O(\text{nnz})$ 가 전부다. 고유값 문제를 실제로 푸는 데는 $O(n^3)$ 이 드는데, 거슈고린은 그 전에 “고유값이 이 영역 밖으로는 절대 안 나간다”는 증명된 울타리를 공짜로 준다. 양해법의 안정 시간 간격, 거듭제곱법·역반복의 이동값 선택, 행렬이 양정치인지의 빠른 판정이 모두 이 울타리 위에서 이루어진다.

이 정리는 사실 대각 우세 행렬의 정칙성 정리(레비-데플랑크)를 $A - \lambda I$ 에 적용한 것과 정확히 같은 내용이다. 타우스키(1949)가 이 사실을 두고 「되풀이해 재발견되는 정리」라는 제목의 논문을 쓴 것은 유명하다¹.

2. 정리와 증명

$\lambda$ 를 $A$ 의 고유값, $\mathbf{x}$ 를 대응 고유벡터라 하고, 절댓값이 가장 큰 성분의 번호를 $i$ 라 하자($\lvert x_i\rvert \ge \lvert x_j\rvert$, $x_i \ne 0$). 고유값 방정식의 $i$ 번째 행

$$\sum_j a_{ij} x_j = \lambda x_i$$

에서 대각항을 넘기고 $x_i$ 로 나누면

$$\lvert \lambda - a_{ii}\rvert = \Bigl\lvert \sum_{j\ne i} a_{ij}\,\frac{x_j}{x_i} \Bigr\rvert \le \sum_{j\ne i} \lvert a_{ij}\rvert = R_i$$

이다. 즉 $\lambda$ 는 적어도 하나의 원판 $D_i$ 안에 있다. 증명 끝. 세 줄짜리지만 어느 원판인지는 모른다는 점이 중요하다 — 고유벡터의 최대 성분이 어느 자리인지에 달려 있어서다.

$A$ 와 $A^{\mathsf T}$ 는 고유값이 같으므로, 열 합으로 만든 원판 $C_j$ (반지름 $\sum_{i\ne j}\lvert a_{ij}\rvert$)의 합집합에도 모든 고유값이 들어간다. 따라서 고유값은 행 원판 합집합과 열 원판 합집합의 교집합 안에 있다. 행렬이 대칭이면 둘이 같고, 고유값이 실수이므로 원판은 실수축 위의 구간 $[a_{ii} - R_i,\ a_{ii} + R_i]$ 로 줄어든다.

2.1. 강화판 — 고립된 원판에는 몇 개가 들어가나

거슈고린 정리의 진짜 힘은 두 번째 주장에 있다.

$k$ 개 원판의 합집합이 나머지 $n-k$ 개 원판의 합집합과 겹치지 않으면, 그 $k$ 개 원판 안에 고유값이 중복도를 세어 정확히 $k$ 개 있다.

증명은 연속성 논법이다. $A(t) = D + t(A - D)$ ($D$ 는 $A$ 의 대각부분, $0 \le t \le 1$)를 생각하면 $t = 0$ 에서 고유값은 원판 중심 $a_{ii}$ 그 자체이고, $t$ 가 커지면서 원판 반지름 $tR_i$ 가 부풀 뿐 중심은 그대로다. 고유값은 $t$ 의 연속함수(특성다항식 근의 연속성)이므로 고립된 영역 안에서 출발한 $k$ 개 고유값은 경계를 건너 다른 영역으로 넘어갈 수 없다 — 두 영역 사이에는 원판이 없는 틈이 있기 때문이다.

특히 원판 하나가 홀로 떨어져 있으면 그 안에 고유값이 정확히 하나 있다. 실수 행렬이면 복소 고유값은 켤레쌍으로 나오므로, 실수축에 중심을 둔 고립 원판 안의 그 하나는 실수여야 한다. 고유값 계산 없이 “이 행렬은 실고유값을 적어도 몇 개 갖는다”를 증명할 수 있다.

2.2. 예

$$A = \begin{pmatrix} 4 & 1 & 0 & 0.5 \\ 0.5 & -2 & 0.5 & 0 \\ 0.2 & 0.3 & 7 & 0.4 \\ 0 & 1 & 0.5 & -6 \end{pmatrix}$$

$i$	중심 $a_{ii}$	행 반지름	열 반지름
1	4	1.5	0.7
2	−2	1.0	2.3
3	7	0.9	1.0
4	−6	1.5	0.9

행 원판 네 개가 서로 전혀 겹치지 않는다($[2.5, 5.5]$, $[-3, -1]$, $[6.1, 7.9]$, $[-7.5, -4.5]$ 를 지름으로 하는 원판). 그러니 각 원판에 실고유값이 정확히 하나씩 있다. 실제 고유값은 $-6.005$, $-2.112$, $4.078$, $7.039$ 로 모두 중심에서 0.11 이내다. 행 원판과 열 원판 중 작은 쪽을 고르면 첫 번째 고유값의 울타리가 반지름 1.5 에서 0.7 로 줄어든다.

3. 대각 닮음으로 원판 조이기

원판이 너무 크면 $D = \mathrm{diag}(d_1, \dots, d_n)$, $d_i > 0$ 으로 닮음변환한 $D^{-1}AD$ 에 정리를 다시 적용한다. 고유값은 그대로인데 $(i,j)$ 성분이 $a_{ij}\, d_j / d_i$ 로 바뀌므로, $d_i$ 를 키우면 $i$ 번째 행 원판은 줄고 나머지 행의 $i$ 열 기여는 커진다. 한 원판을 조이는 대신 다른 원판들을 부풀리는 거래다.

이 거래가 얼마나 유리한지 보여 주는 고전 예제가 있다. $A = \mathrm{diag}(1, 2, 3) + \varepsilon(\mathbf{1}\mathbf{1}^{\mathsf T} - I)$, $\varepsilon = 0.1$ 이면 원판 반지름이 모두 $2\varepsilon = 0.2$ 다. 그런데 실제 첫 고유값은 $0.98608$ 로, 중심 1에서 $0.0139$ 밖에 안 떨어져 있다 — 비대각 성분이 $\varepsilon$ 인데 고유값 이동은 $O(\varepsilon^2)$ 이기 때문이다(대칭 행렬의 2차 섭동).

$d_1 = d$ 만 키우면 첫 원판 반지름은 $2\varepsilon/d$, 다른 두 원판 반지름은 $\varepsilon(d + 1)$ 이 된다.

$d$	1	2	5	8
첫 원판 반지름	0.2	0.1	0.04	0.025
둘째 원판 반지름	0.2	0.3	0.6	0.9
첫 원판 고립 여부	예	예	예	예

$d = 8$ 이면 첫 원판 $[0.975, 1.025]$ 가 둘째 원판 $[1.1, 2.9]$ 와 떨어져 있으므로, 고유값이 정확히 하나 $\lvert\lambda - 1\rvert \le 0.025$ 안에 있다는 것이 증명된다. 실제 오차 0.0139 와 같은 자릿수다. $d \approx 1/\varepsilon$ 근처까지 밀면 반지름이 $O(\varepsilon^2)$ 꼴이 되어 2차 섭동의 크기를 거슈고린만으로 재현할 수 있다($d = 9$ 에서는 원판이 닿아 고립이 깨진다).

$D$ 를 최적으로 고르는 문제는 M-행렬 이론과 이어진다. $\lvert A\rvert$ 의 비대각 부분이 기약 비음 행렬이면 페론 벡터로 $D$ 를 잡아 모든 원판 반지름을 한꺼번에 최소화할 수 있다 — 바르가(2004)가 정리한 「최소 거슈고린 집합」이 이 방향이다.

4. 변형들

• 브라우어의 카시니 타원(1947). 원판 $n$ 개 대신 두 행을 짝지은 영역 $\{z : \lvert z - a_{ii}\rvert\,\lvert z - a_{jj}\rvert \le R_i R_j\}$ $n(n-1)/2$ 개를 쓴다. 이 합집합은 거슈고린 원판 합집합에 항상 포함되므로 더 좁은 울타리다. 세 행 이상으로 일반화하면 오히려 고유값을 놓칠 수 있다는 반례가 있어 실용판은 둘씩 짝짓는 데서 멈춘다.
• 블록 거슈고린. 행렬을 블록으로 나누고 대각 블록의 스펙트럼 주변에 비대각 블록 노름만큼의 영역을 친다. 대각 블록이 이미 잘 풀린 영역 분할법·다물리 연성 계에서 결합 효과를 어림할 때 쓴다.
• 오스트로프스키 원판. 행 합과 열 합의 가중 기하평균 $R_i^{\alpha} C_i^{1-\alpha}$ 를 반지름으로 쓴다($0 \le \alpha \le 1$).

어느 판이든 핵심은 같다 — “대각이 비대각보다 충분히 크면 고유값이 대각 근처에 붙어 있다”.

5. 시뮬레이션에서의 쓰임

5.1. 양해법의 안정 시간 간격

1차원 열방정식 $u_t = u_{xx}$ 를 2차 중앙차분하면 반이산 계 $\dot{\mathbf u} = L\mathbf u$ 의 행렬 $L$ 이 대각 $-2/h^2$, 비대각 $1/h^2$ 인 삼중대각이다. 원판은 모두 중심 $-2/h^2$, 반지름 $2/h^2$ 이므로 고유값은 $[-4/h^2, 0]$ 안에 있다. 전진 오일러의 안정 조건 $\lvert 1 + \Delta t\,\lambda\rvert \le 1$ 에 넣으면

$$\Delta t \le \frac{h^2}{2}$$

— 교과서의 확산 CFL 조건이 고유값을 하나도 계산하지 않고 나온다. 실제로 $n = 50$ 에서 $h^2\lambda$ 는 $[-3.996, -0.004]$ 라 울타리가 거의 빡빡하다. 폰 노이만 안정성 해석은 주기 경계와 상수 계수가 필요하지만 거슈고린은 비균일 격자·변계수·임의 경계조건에도 그대로 적용된다. 실무 코드가 국소 시간 간격을 셀마다 $\Delta t_i \le 2/(\lvert a_{ii}\rvert + R_i)$ 꼴로 잡는 것이 정확히 이 논리다.

5.2. 정치성 판정과 이동값

대칭 행렬의 모든 원판이 양의 실수축에 있으면($a_{ii} > R_i$) 행렬은 양정치다. 엄격 대각 우세 + 양의 대각 ⇒ 양정치라는 흔한 판정법이 이것이다. 촐레스키 분해가 실패할지 미리 알고 싶을 때, 또는 고유값 해법에서 스펙트럼 양 끝 $\min_i(a_{ii} - R_i)$, $\max_i(a_{ii} + R_i)$ 를 이동값·체비쇼프 가속 구간으로 쓸 때 쓴다. 란초스 알고리즘이나 체비쇼프 반복은 스펙트럼 구간의 추정이 필요한데, 거슈고린 한계가 가장 싸고 틀리지 않는 추정이다.

5.3. 반복법의 수렴 판정

야코비 반복 행렬 $G = I - D^{-1}A$ 의 원판은 모두 원점 중심, 반지름 $R_i/\lvert a_{ii}\rvert$ 다. 그러니 엄격 대각 우세면 스펙트럼 반지름 $\rho(G) < 1$ 이고 야코비 반복법이 수렴한다. 대각 우세가 반복법 수렴의 충분조건인 이유를 한 줄로 설명하는 것도 거슈고린이다.

5.4. 고유값 섭동

$A$ 가 대각화 가능하고 $A = V\Lambda V^{-1}$ 이면, $V^{-1}(A + E)V = \Lambda + V^{-1}EV$ 에 거슈고린을 적용해 섭동된 고유값이 $\lambda_i$ 중심, 반지름 $\lVert V^{-1}EV\rVert_\infty$ 인 원판들 안에 있음을 얻는다. 이것을 노름으로 정리하면 바우어-파이크 정리 $\min_i \lvert\mu - \lambda_i\rvert \le \kappa(V)\lVert E\rVert$ 가 된다. 고유벡터 행렬의 조건수 $\kappa(V)$ 가 크면(비정규 행렬) 작은 섭동에도 고유값이 크게 움직일 수 있다는 경고가 여기서 나온다².

6. 한계

• 원판이 겹치면 개수 정보가 사라진다. 겹친 덩어리 안에 고유값이 몇 개인지는 알 수 있지만 어느 원판에 있는지는 모른다. 원판 하나가 비어 있는 일도 흔하다.
• 비대각이 크면 쓸모없다. 대각 우세와 거리가 먼 행렬(예: 힐베르트 행렬, 대류 지배 이산화의 중앙차분)에서는 원판이 스펙트럼보다 훨씬 커서 원점을 덮어 버린다. 그럴 때는 대각 닮음으로 조이거나, 아예 QR 알고리즘으로 계산하는 게 맞다.
• 하한은 주지 않는다. 원판은 고유값이 있을 수 있는 곳의 바깥 울타리다. 가장 작은 고유값의 절댓값 하한(원점에서 떨어진 거리)은 원점이 모든 원판 밖에 있을 때만 나온다 — 그게 곧 엄격 대각 우세 조건이다³.

7. 관련 문서

• 고유값 문제 · 대각 우세 행렬 · M-행렬 · 스펙트럼 반지름
• CFL 조건 · 폰 노이만 안정성 해석 · 열방정식
• 거듭제곱법 · 란초스 알고리즘 · QR 알고리즘 · 조건수
• 바우어-파이크 정리 · 야코비 반복법 · 영역 분할법

8. Footnotes

1. 레비(1881), 데플랑크(1887), 민코프스키(1900), 아다마르(1903)가 제각각 같은 정칙성 결과를 냈고, 거슈고린은 그걸 고유값 위치로 돌려 읽었다. 타우스키 논문 제목 자체가 “또 나왔다”는 뉘앙스라 사실상 점잖은 공개 저격이다. 국룰 재발견 정리. ↩

2. 비정규 행렬에서 거슈고린 원판이 실제 고유값보다 터무니없이 커 보이는 건 원판이 틀려서가 아니라, 그 행렬의 고유값이 원래 그만큼 불안정해서다. 원판은 일종의 「섭동받은 행렬까지 다 포함한 보험」이다. ↩

3. 그래서 원점이 원판에 걸리는 순간 거슈고린은 “이 행렬이 특이할 수도 있음”이라는 말 말고는 할 말이 없어진다. 특이하다는 게 아니라 모른다는 뜻이다. 모르는 걸 모른다고 말하는 정직한 정리. ↩