30.25 거슈고린 원 정리(Gershgorin Circle Theorem)에 의한 고유값 위치 추정

1. 거슈고린 원의 정의

$n \times n$ 행렬 $A = (a_{ij})$ 에 대하여 제 $i$ 번째 **거슈고린 원(Gershgorin disc)**은 복소 평면 $\mathbb{C}$ 위의 닫힌 원반으로서

$D_i = \left\{ z \in \mathbb{C} : \lvert z - a_{ii} \rvert \leq R_i \right\}$

로 정의된다. 여기서 중심은 $A$ 의 제 $i$ 번째 대각 성분 $a_{ii}$ 이고, 반지름은 제 $i$ 번째 행의 비대각 성분의 절댓값 합

$R_i = \sum_{\substack{j=1 \\ j \neq i}}^{n} \lvert a_{ij} \rvert$

이다. $R_i$ 를 제 $i$ 행의 **삭제된 절대 행합(deleted absolute row sum)**이라 한다.

2. 거슈고린 원 정리의 진술

정리 (Gershgorin circle theorem, 1931). $n \times n$ 행렬 $A$ 의 모든 고유값은 $n$ 개의 거슈고린 원의 합집합 내에 위치한다:

$\sigma(A) \subseteq \bigcup_{i=1}^{n} D_i$

여기서 $\sigma(A)$ 는 $A$ 의 스펙트럼(고유값의 집합)이다.

증명. $\lambda$ 를 $A$ 의 고유값이라 하고 $v = (v_1, v_2, \ldots, v_n)^T$ 를 대응하는 고유벡터( $v \neq 0$ )라 하자. $\lvert v_k \rvert = \max_{1 \leq j \leq n} \lvert v_j \rvert > 0$ 인 성분 $v_k$ 를 취한다.

$Av = \lambda v$ 의 제 $k$ 번째 성분은

$\sum_{j=1}^{n} a_{kj} v_j = \lambda v_k$

이다. 대각 항을 분리하면

$a_{kk} v_k + \sum_{\substack{j=1 \\ j \neq k}}^{n} a_{kj} v_j = \lambda v_k$

$(\lambda - a_{kk}) v_k = \sum_{\substack{j=1 \\ j \neq k}}^{n} a_{kj} v_j$

양변의 절댓값을 취하면

$\lvert \lambda - a_{kk} \rvert \lvert v_k \rvert = \left\lvert \sum_{\substack{j=1 \\ j \neq k}}^{n} a_{kj} v_j \right\rvert \leq \sum_{\substack{j=1 \\ j \neq k}}^{n} \lvert a_{kj} \rvert \lvert v_j \rvert$

$\lvert v_j \rvert \leq \lvert v_k \rvert$ 이므로

$\lvert \lambda - a_{kk} \rvert \lvert v_k \rvert \leq \lvert v_k \rvert \sum_{\substack{j=1 \\ j \neq k}}^{n} \lvert a_{kj} \rvert = R_k \lvert v_k \rvert$

$\lvert v_k \rvert > 0$ 으로 양변을 나누면

$\lvert \lambda - a_{kk} \rvert \leq R_k$

따라서 $\lambda \in D_k \subseteq \bigcup_{i=1}^{n} D_i$ 이다. $\blacksquare$

증명의 핵심은 고유벡터의 최대 절댓값 성분을 선택하고, 삼각 부등식을 적용하는 것이다. 이 증명은 행렬의 대칭성이나 대각화 가능성에 무관하게 모든 행렬에 적용된다.

3. 열 거슈고린 원

거슈고린 정리는 $A$ 의 전치 $A^T$ 에 대해서도 성립한다. $A$ 와 $A^T$ 의 고유값은 동일하므로 ( $\det(A - \lambda I) = \det(A^T - \lambda I)$ ), 열 거슈고린 원(column Gershgorin discs)

$D_j' = \left\{ z \in \mathbb{C} : \lvert z - a_{jj} \rvert \leq C_j \right\}, \quad C_j = \sum_{\substack{i=1 \\ i \neq j}}^{n} \lvert a_{ij} \rvert$

에 의한 추정도 유효하다:

$\sigma(A) \subseteq \bigcup_{j=1}^{n} D_j'$

행 거슈고린 원과 열 거슈고린 원의 교집합을 취하면 더 정밀한 추정을 얻는다:

$\sigma(A) \subseteq \left(\bigcup_{i=1}^{n} D_i\right) \cap \left(\bigcup_{j=1}^{n} D_j'\right)$

4. 연결 성분에 의한 고유값 개수 추정

정리 (거슈고린 정리의 연결 성분 결과). $n$ 개의 거슈고린 원의 합집합이 $m$ 개의 연결 성분(connected component)으로 분리되면, 각 연결 성분 내에 포함되는 고유값의 개수(대수적 중복도 포함)는 해당 연결 성분을 구성하는 거슈고린 원의 개수와 같다.

증명 개요. 행렬 $A$ 를 대각 행렬 $D = \operatorname{diag}(a_{11}, \ldots, a_{nn})$ 와 비대각 부분 $N = A - D$ 로 분해한다. 매개변수 $t \in [0, 1]$ 에 대하여 $A(t) = D + tN$ 을 고려하면, $A(0) = D$ 의 고유값은 $a_{11}, \ldots, a_{nn}$ 이고 $A(1) = A$ 이다.

$t$ 가 0에서 1로 연속적으로 변할 때, $A(t)$ 의 거슈고린 원은 $\{z : \lvert z - a_{ii} \rvert \leq t R_i\}$ 이다. $t = 0$ 에서 각 원은 점(중심)으로 축소되며, $t$ 가 증가함에 따라 원이 팽창한다. 고유값은 연속적으로 이동하므로, 원이 팽창하는 과정에서 연결 성분이 합쳐지지 않는 한 각 연결 성분 내의 고유값 개수는 변하지 않는다. $\blacksquare$

따름 정리. 하나의 거슈고린 원이 나머지 모든 거슈고린 원과 분리되어 있으면(교집합이 공집합), 그 원 안에 정확히 하나의 고유값이 존재한다.

5. 수치 예시

5.1 예시 1: $3 \times 3$ 행렬

$A = \begin{pmatrix} 4 & 1 & 0 \\ 0.5 & 6 & 0.5 \\ 0 & 1 & 9 \end{pmatrix}$

거슈고린 원을 계산한다:

$D_1$ : 중심 $4$ , 반지름 $R_1 = \lvert 1 \rvert + \lvert 0 \rvert = 1$ , 즉 $[3, 5]$
$D_2$ : 중심 $6$ , 반지름 $R_2 = \lvert 0.5 \rvert + \lvert 0.5 \rvert = 1$ , 즉 $[5, 7]$
$D_3$ : 중심 $9$ , 반지름 $R_3 = \lvert 0 \rvert + \lvert 1 \rvert = 1$ , 즉 $[8, 10]$

$D_1 \cap D_2 \neq \emptyset$ ( $\{5\}$ 에서 접함)이고, $D_3$ 은 $D_1, D_2$ 와 분리되어 있다. 따라서 $D_1 \cup D_2$ 내에 정확히 2개, $D_3$ 내에 정확히 1개의 고유값이 존재한다.

$A$ 의 실제 고유값은 $\lambda_1 \approx 3.73$ , $\lambda_2 \approx 6.17$ , $\lambda_3 \approx 9.10$ 이며, 모두 각각의 거슈고린 원 내에 위치한다.

5.2 예시 2: 대각 우세 행렬

$B = \begin{pmatrix} 10 & 1 & 1 \\ 1 & 20 & 2 \\ 1 & 2 & 30 \end{pmatrix}$

$D_1$ : 중심 $10$ , 반지름 $2$ , 즉 $[8, 12]$
$D_2$ : 중심 $20$ , 반지름 $3$ , 즉 $[17, 23]$
$D_3$ : 중심 $30$ , 반지름 $3$ , 즉 $[27, 33]$

세 원이 모두 분리되어 있으므로, 각 원에 정확히 하나의 실수 고유값이 존재한다. 이 경우 거슈고린 정리는 고유값의 위치에 대한 정밀한 정보를 제공한다.

6. 대각 우세 행렬(Diagonally Dominant Matrix)

정의. 행렬 $A$ 가 **대각 우세(diagonally dominant)**라 함은 모든 $i$ 에 대하여

$\lvert a_{ii} \rvert \geq R_i = \sum_{\substack{j \neq i}} \lvert a_{ij} \rvert$

이 성립하는 것이다. **순 대각 우세(strictly diagonally dominant)**는 모든 $i$ 에 대하여 $\lvert a_{ii} \rvert > R_i$ 인 경우이다.

정리. 순 대각 우세 행렬은 가역이다.

증명. 거슈고린 정리에 의하여, 모든 고유값 $\lambda$ 는 어떤 $D_i$ 내에 있다. 순 대각 우세이면 $0 \notin D_i$ ( $\forall i$ )이다 ( $\lvert 0 - a_{ii} \rvert = \lvert a_{ii} \rvert > R_i$ 이므로 $0$ 은 어떤 거슈고린 원에도 속하지 않는다). 따라서 $\lambda \neq 0$ 이고, $\det(A) = \prod \lambda_i \neq 0$ 이다. $\blacksquare$

7. 거슈고린 추정의 개선: 유사 변환 활용

거슈고린 추정은 행렬에 대각 유사 변환(diagonal similarity transformation)을 적용하여 개선할 수 있다.

가역 대각 행렬 $D = \operatorname{diag}(d_1, d_2, \ldots, d_n)$ ( $d_i > 0$ )에 대하여, $B = D^{-1} A D$ 는 $A$ 와 동일한 고유값을 갖는다. $B$ 의 성분은

$b_{ij} = \frac{d_j}{d_i} a_{ij}$

이므로, $B$ 의 제 $i$ 행 거슈고린 반지름은

$R_i(B) = \sum_{j \neq i} \lvert b_{ij} \rvert = \sum_{j \neq i} \frac{d_j}{d_i} \lvert a_{ij} \rvert$

$D$ 의 대각 원소 $d_i$ 를 적절히 선택하면 거슈고린 원의 크기를 줄일 수 있다. 최적의 $D$ 를 구하는 것은 선형 프로그래밍 문제로 정식화된다.

모든 가역 대각 행렬 $D$ 에 대한 거슈고린 원의 교집합

$\bigcap_{D > 0} \bigcup_{i=1}^{n} D_i(D^{-1} A D)$

은 원래의 거슈고린 추정보다 정밀한 고유값 포함 영역을 제공한다.

8. 실수 대칭 행렬에서의 거슈고린 정리

실수 대칭 행렬의 고유값은 모두 실수이므로, 거슈고린 원은 실수 직선 위의 구간으로 축소된다:

$D_i = [\, a_{ii} - R_i, \; a_{ii} + R_i \,]$

이 경우 고유값의 상한과 하한을 다음과 같이 즉시 추정할 수 있다:

$\lambda_{\min}(A) \geq \min_{1 \leq i \leq n} (a_{ii} - R_i)$

$\lambda_{\max}(A) \leq \max_{1 \leq i \leq n} (a_{ii} + R_i)$

9. 브라우어 정리(Brauer’s Theorem)

거슈고린 정리의 정밀화로서 Brauer의 카시니 타원(Cassini oval) 정리가 있다.

정리 (Brauer, 1947). $A$ 의 모든 고유값은 $\binom{n}{2}$ 개의 카시니 타원의 합집합 내에 위치한다:

$\sigma(A) \subseteq \bigcup_{i < j} K_{ij}$

여기서

$K_{ij} = \left\{ z \in \mathbb{C} : \lvert z - a_{ii} \rvert \cdot \lvert z - a_{jj} \rvert \leq R_i R_j \right\}$

카시니 타원은 두 거슈고린 원의 정보를 동시에 활용하므로, 두 원이 겹치는 영역에서 거슈고린 추정보다 정밀한 결과를 제공할 수 있다.

10. 거슈고린 정리의 한계

거슈고린 추정은 다음과 같은 한계를 갖는다.

비대각 성분의 구조 무시. 반지름 $R_i$ 는 비대각 성분의 절댓값 합으로서, 성분의 부호나 상호 관계를 반영하지 않는다. 따라서 비대각 구조가 특수한 경우 추정이 지나치게 보수적일 수 있다.

근접 고유값의 분리 불가. 두 고유값이 매우 가까운 경우, 대응하는 거슈고린 원이 겹쳐서 개별 고유값의 위치를 특정할 수 없다.

정밀도의 제한. 거슈고린 추정은 고유값의 대략적 위치만을 제공하며, 정확한 고유값 계산을 대체하지 못한다.

이러한 한계에도 불구하고, 거슈고린 정리는 $O(n^2)$ 의 계산 비용(행렬 성분의 스캔)만으로 고유값의 범위를 추정할 수 있으므로, 사전 분석(preliminary analysis) 도구로서 실용적 가치가 크다.

11. 수치 예시: 거슈고린 추정과 실제 고유값의 비교

$A = \begin{pmatrix} 5 & 0.1 & 0.2 \\ 0.1 & 8 & 0.3 \\ 0.2 & 0.3 & 12 \end{pmatrix}$

행 $i$	중심 $a_{ii}$	반지름 $R_i$	거슈고린 구간	실제 고유값
1	5	0.3	$[4.7, \, 5.3]$	$\approx 4.97$
2	8	0.4	$[7.6, \, 8.4]$	$\approx 8.01$
3	12	0.5	$[11.5, \, 12.5]$	$\approx 12.02$

세 거슈고린 원이 모두 분리되어 있으므로, 각 구간에 정확히 하나의 고유값이 존재함이 보장된다. 행렬이 대각 우세에 가까울수록 거슈고린 추정은 정밀해진다.

12. 딥러닝에서의 활용

가중치 행렬의 스펙트럼 반지름 추정. 신경망의 가중치 행렬 또는 야코비안 행렬의 스펙트럼 반지름(spectral radius) $\rho(A) = \max_i \lvert \lambda_i \rvert$ 에 대한 상한을 거슈고린 정리로 빠르게 추정할 수 있다:

$\rho(A) \leq \max_{1 \leq i \leq n} \left( \lvert a_{ii} \rvert + R_i \right)$

이 추정은 $O(n^2)$ 로 계산되므로, 학습 과정에서 안정성을 실시간 모니터링하는 데 활용할 수 있다.

대각 우세 조건의 점검. 행렬이 대각 우세인지 여부를 거슈고린 반지름을 통하여 $O(n^2)$ 로 판별할 수 있으며, 이는 행렬의 가역성 보장과 수치 안정성의 사전 점검에 유용하다.

전처리(Preconditioning). 반복 수치 알고리즘에서 행렬에 대각 전처리(diagonal preconditioning)를 적용하여 거슈고린 원의 크기를 줄이면, 고유값 군집(clustering)이 개선되어 수렴 속도가 향상된다.