순환 행렬

1. 개요

순환 행렬 Circulant Matrix
정의	각 행이 윗 행을 오른쪽으로 한 칸 순환 이동
고유벡터	성분과 무관하게 언제나 푸리에 모드
고유값	첫 열의 DFT
풀이·곱·역	FFT 로 O(n log n)
성질	정규 행렬, 서로 교환 가능
등장처	주기 경계 이산화, 원형 합성곱, 토플리츠 전처리

고유벡터를 미리 알고 있는 행렬족. 고유값 문제의 시험지를 답안지와 함께 받은 셈이다.

순환 행렬(circulant matrix)은 첫 열 $\mathbf{c} = (c_0, c_1, \dots, c_{n-1})$ 로 정해지고, 각 열이 앞 열을 아래로 한 칸 순환 이동한 정사각행렬이다.

$$C = \mathrm{circ}(\mathbf{c}) = \begin{pmatrix} c_0 & c_{n-1} & \cdots & c_2 & c_1 \\ c_1 & c_0 & c_{n-1} & & c_2 \\ \vdots & c_1 & c_0 & \ddots & \vdots \\ c_{n-2} & & \ddots & \ddots & c_{n-1} \\ c_{n-1} & c_{n-2} & \cdots & c_1 & c_0 \end{pmatrix}, \qquad C_{ij} = c_{(i-j) \bmod n}.$$

토플리츠 행렬의 특수한 경우로, 대각선이 끝에서 끊기지 않고 반대편으로 감겨 들어간다. 순환 이동 치환 행렬 $P$ 로 쓰면 $C = \sum_k c_k P^k$ — 즉 순환 행렬은 정확히 $P$ 의 다항식들이다.

이 감김이 물리적으로는 주기 경계다. 원환 위의 격자, 주기 경계조건을 건 상수계수 차분 연산자, 원형 합성곱이 모두 순환 행렬이다. 그리고 순환 행렬은 이산 푸리에 변환(DFT) 행렬로 정확히 대각화되기 때문에, 곱셈·풀이·역행렬·고유값이 전부 고속 푸리에 변환 몇 번으로 끝난다. 원형 합성곱과 순환 겹침(wrap-around)의 신호처리 쪽 이야기는 합성곱 정리가 다뤘으니, 이 문서는 선형대수와 수치해석 쪽 — 대수 구조, 특이성, 폰 노이만 해석과의 관계, 2차원 영상 복원 — 을 정리한다.

2. 대각화 — 왜 푸리에 모드인가

$P$ 의 고유벡터는 $\mathbf{f}_j = (1, \omega^j, \omega^{2j}, \dots, \omega^{(n-1)j})^\top$, $\omega = e^{-2\pi i/n}$ 이다(한 칸 밀면 $\omega^{-j}$ 가 곱해질 뿐이다). $C$ 는 $P$ 의 다항식이므로 고유벡터를 그대로 물려받는다. 따라서

$$C = F^{-1}\, \mathrm{diag}(\hat{\mathbf{c}})\, F, \qquad \lambda_j = \hat c_j = \sum_{k=0}^{n-1} c_k\, \omega^{jk},$$

여기서 $F$ 는 DFT 행렬이다. 고유벡터는 $\mathbf{c}$ 와 무관하고, 고유값은 첫 열의 DFT 다.

예: 주기 경계 1차원 라플라시안 $\mathrm{circ}(2, -1, 0, \dots, 0, -1)$ 의 고유값은 $\lambda_j = 2 - 2\cos(2\pi j/n) = 4\sin^2(\pi j/n)$ 이다. $n = 8$ 로 조밀 고유값 솔버, FFT, 공식 세 가지를 비교하면 $0,\ 0.5858,\ 0.5858,\ 2,\ 2,\ 3.4142,\ 3.4142,\ 4$ 로 모두 일치한다. $j$ 와 $n-j$ 가 같은 값을 주어 0과 4를 빼고는 전부 중복도 2다. 디리클레 경계의 토플리츠판 $\mathrm{tridiag}(-1,2,-1)$ 이 $2-2\cos(j\pi/(n+1))$ 을 주는 것과 대조된다 — 경계를 감느냐 자르느냐가 고유값의 격자 간격을 바꾼다.

3. 대수 구조

$n\times n$ 순환 행렬 전체는 교환 가능한 대수를 이룬다. 모두 같은 $F$ 로 대각화되기 때문에 다음이 공짜로 따라온다¹.

• 합·곱이 순환 행렬이고 곱셈 순서를 바꿔도 된다($AB = BA$).
• 정칙이면 역행렬도 순환 행렬이다. 무작위 $6\times6$ 순환 행렬로 확인하면 역행렬이 자기 첫 열로 만든 순환 행렬과 일치한다.
• 행렬식은 고유값의 곱 $\det C = \prod_j \hat c_j$ 다(같은 행렬에서 조밀 계산 $-0.0437997$ 과 일치).
• 모든 순환 행렬은 정규 행렬이다. 그래서 특이값이 $\lvert \hat c_j \rvert$ 이고, 2-노름 조건수가 $\max\lvert\hat c_j\rvert / \min\lvert\hat c_j\rvert$ 로 바로 읽힌다.
• $\mathbf{c}$ 가 실수면 $\hat c_{n-j} = \overline{\hat c_j}$, 대칭($c_k = c_{n-k}$)이면 고유값이 전부 실수다.

4. 풀이와 특이성

$C\mathbf{x} = \mathbf{b}$ 는

$$\mathbf{x} = F^{-1}\bigl(\hat{\mathbf{b}} \,./\, \hat{\mathbf{c}}\bigr)$$

로 FFT 두 번과 원소별 나눗셈, $O(n\log n)$ 에 끝난다. 소거도 피벗도 없다.

문제는 $\hat c_j = 0$ 인 모드다. 주기 라플라시안은 $\lambda_0 = 0$ — 상수 벡터가 영공간이다. 물리적으로는 「주기 영역의 포아송 방정식은 해가 상수만큼 정해지지 않고, 우변의 평균이 0이어야 해가 존재한다」는 양립 조건이다. FFT 풀이에서는 $\hat b_0 = 0$ 을 확인하고 $\hat x_0$ 에 원하는 평균(보통 0)을 넣으면 끝난다. $\hat c_j$ 가 0은 아니지만 아주 작으면 그 모드에서 잡음이 $1/\lvert\hat c_j\rvert$ 배로 증폭되는데, 이게 아래 영상 복원의 핵심 문제다.

4.1. 실측 — FFT 는 이산 문제를 정확히 푼다

$-u'' = \sin 2\pi x + \tfrac12\cos 6\pi x$ 를 주기 경계 2차 중앙차분으로 이산화하고 FFT 로 풀어 정확해와 비교했다.

$n$	64	128	256	512
최대 오차	$2.82\times10^{-5}$	$7.07\times10^{-6}$	$1.77\times10^{-6}$	$4.42\times10^{-7}$

격자를 두 배로 할 때마다 정확히 4배씩 준다 — 2차 수렴이다. FFT 는 이산계를 반올림 오차까지 정확히 풀었고, 남은 오차는 전부 차분의 절단오차다. 같은 FFT 를 쓰면서 심볼 $4\sin^2(\pi j/n)/h^2$ 대신 $(2\pi j)^2$ 로 나누면 그게 스펙트럴 방법이고, 매끄러운 해에서 오차가 지수적으로 떨어진다. 「FFT 를 썼다」와 「스펙트럴 정확도」는 다른 말이다².

5. 폰 노이만 해석의 정체

주기 경계에서 상수계수 시간전진 도식 $\mathbf{u}^{n+1} = G\mathbf{u}^n$ 의 갱신 행렬 $G$ 는 순환 행렬이다. 그러면 폰 노이만 안정성 해석에서 계산하는 증폭 인자 $g(\theta)$ 는 정확히 $G$ 의 고유값이고, 푸리에 모드는 정확히 그 고유벡터다.

예를 들어 1차 풍상 이류 $u_i^{n+1} = (1-\nu)u_i^n + \nu u_{i-1}^n$ 은 $G = \mathrm{circ}(1-\nu, \nu, 0, \dots, 0)$ 이고 고유값은 $1 - \nu + \nu e^{-i\theta_j}$, $\theta_j = 2\pi j/n$ — 중심 $1-\nu$, 반지름 $\nu$ 인 원 위의 점들이다. 이 원이 단위원 안에 들어가는 조건이 $0 \le \nu \le 1$, 곧 CFL 조건이다.

여기서 순환 행렬이 정규라는 사실이 결정적이다. 정규 행렬은 $\lVert G^n \rVert_2 = \rho(G)^n$ 이므로 주기 경계에서는 폰 노이만 조건이 안정성의 필요충분조건이다. 경계가 주기가 아니면 $G$ 는 토플리츠에 경계 행이 붙은 비정규 행렬이 되고, 고유값이 모두 단위원 안이어도 $\lVert G^n\rVert$ 가 한동안 크게 자랄 수 있다. 그 과도 성장은 고유값이 아니라 의사스펙트럼으로 봐야 보이며, 이것이 행렬 안정성 해석이 폰 노이만 해석과 따로 존재하는 이유다³.

6. 2차원 — BCCB 와 영상 복원

2차원 주기 격자 위의 연산자는 블록 순환-순환 블록(BCCB) 행렬이다. 블록 단위로 순환이고 각 블록도 순환이다. 2차원 FFT 가 이를 정확히 대각화한다.

주기 경계를 가정한 영상 흐림(blur)이 대표 사례다. 점퍼짐함수(PSF)로 만든 흐림 연산자 $A$ 의 고유값은 PSF 의 2차원 DFT 다. 가우스 PSF($\sigma = 2$ 픽셀, 한 변 128)의 1차원 심볼을 재면 고유값이 최대 $1$, 최소 $5.35\times10^{-9}$ 다. 1차원만으로 조건수가 $1.9\times10^8$ 이고, 2차원 고유값은 1차원 고유값 두 개의 곱이라(가우스 PSF 는 분리 가능하다) 조건수가 정확히 그 제곱이 된다. 흐린 영상 $\mathbf{b}$ 를 $\hat{\mathbf{b}}./\hat{\mathbf{a}}$ 로 그냥 나누면 고주파 모드의 잡음이 억 배로 증폭되어 영상이 모래폭풍이 된다.

그래서 디컨볼루션은 거의 항상 정칙화와 함께 간다. 티호노프 정규화를 쓰면 해가

$$\hat x_j = \frac{\overline{\hat a_j}\ \hat b_j}{\lvert \hat a_j\rvert^2 + \alpha}$$

로 여전히 원소별 연산이라 $O(n\log n)$ 이다. 위너 필터·절단 SVD 필터도 같은 틀에서 필터 인자만 바꾼 것이다. 실제 사진은 주기적이지 않으므로 가장자리에서 반대편이 섞이는 경계 결함이 생기는데, 반사 경계로 바꾸면 BCCB 대신 이산 코사인 변환으로 대각화되는 구조가 된다.

7. 변형과 쓰임

• 비틀린 순환(skew-circulant): 감겨 들어갈 때 부호가 바뀐다($C_{ij} = -c_{n+i-j}$, $i<j$). 가중 DFT 로 대각화된다. 더 일반적으로 감김에 $\omega$ 를 곱하는 $\omega$-순환 행렬도 같은 성질을 가진다.
• 토플리츠 분해: 임의의 토플리츠 행렬은 순환 행렬 하나와 비틀린 순환 행렬 하나의 합으로 쓸 수 있다. 둘 다 FFT 로 곱할 수 있으니 토플리츠 곱셈의 또 다른 빠른 경로다.
• 토플리츠 전처리: 토플리츠 계를 순환 행렬로 근사해 전처리기로 쓰는 스트랭·T. 챈 전처리기는 토플리츠 행렬 문서에 실측과 함께 있다.
• 순환 삼중대각: 주기 경계 스플라인·암시적 차분에서 나오는 띠 순환 계는 셔먼-모리슨 보정을 붙인 토머스 알고리즘으로 $O(n)$ 에 푼다. 띠가 좁으면 FFT 보다 이쪽이 싸다.
• 다중격자의 국소 모드 해석: 스무더의 감쇠율을 푸리에 모드별로 계산하는 것도 무한·주기 격자의 순환 구조를 가정한 계산이다.

8. 관련 문서

• 토플리츠 행렬 · 합성곱 정리 · 고속 푸리에 변환 · 블루스타인 알고리즘 · 이산 코사인 변환
• 폰 노이만 안정성 해석 · 행렬 안정성 해석 · 주기경계조건 · 스펙트럴 방법
• 포아송 방정식 · 토머스 알고리즘 · 전처리기 · 다중격자법
• 디컨볼루션 · 티호노프 정규화 · 역문제 · 위너 필터

9. Footnotes

1. 순환 행렬만으로 책 한 권(데이비스, 1979)이 나온다. 고유벡터가 고정이라 증명이 대부분 한 줄로 끝나는데, 그 한 줄짜리들을 책 한 권 분량으로 모아 놓은 것이 이 책의 묘미다. ↩

2. 「포아송 솔버를 FFT 로 짰으니 스펙트럴 정확도겠지」는 학회 질의응답에서 꽤 자주 박살 나는 착각이다. 어떤 심볼로 나눴는지가 정확도를 정하고, FFT 는 그냥 빠른 배달부다. ↩

3. 주기 경계에서 멀쩡하던 도식이 실제 유입·유출 경계를 붙이자마자 터지는 이유의 상당수가 여기 있다. 폰 노이만이 「안정」이라고 도장 찍어 준 건 원환 위의 세계뿐이다. 경계가 있는 현실 버전의 판정은 GKS 이론 쪽이 맡는다. ↩