코시 행렬

1. 개요

코시 행렬 Cauchy Matrix
정의	$C_{ij} = 1/(x_i - y_j)$
가역 조건	$x_i$ 끼리, $y_j$ 끼리 서로 다르고 $x_i \ne y_j$
행렬식	코시(1841)의 닫힌꼴 곱 공식
변위 구조	$D_xC - CD_y = \mathbf 1\mathbf 1^T$ (계수 1)
대표 사례	힐베르트 행렬 $1/(i+j-1)$
빠른 연산	행렬-벡터 곱 FMM, 풀이 $O(n^2)$ (GKO)
응용	MDS 소실 부호, 유리 보간, 구조 행렬 해법

모든 정사각 부분행렬이 가역인 행렬. 그 성질 하나로 데이터센터의 저장 장치를 지킨다.

코시 행렬(Cauchy matrix)은 두 점 집합 $\{x_i\}$, $\{y_j\}$ 로

$$C_{ij} = \frac{1}{x_i - y_j},\qquad i, j = 1, \dots, n$$

을 성분으로 갖는 행렬이다. 코시가 1841년에 그 행렬식의 닫힌꼴을 구했다. 반데르몽드 행렬, 토플리츠 행렬, 행켈 행렬과 함께 「$n^2$ 개 성분이 $O(n)$ 개 모수로 정해지는」 구조 행렬 집안의 대표 멤버다.

코시 행렬이 수치해석에서 중요한 이유는 세 가지다. 첫째, 행렬식·역행렬이 닫힌꼴로 나와 조건수가 극단적인 시험 행렬(대표가 힐베르트 행렬)을 정확히 다룰 수 있다. 둘째, 변위 계수가 1 이라 피벗팅을 포함한 가우스 소거를 $O(n^2)$ 에 할 수 있고, 토플리츠 계열을 이쪽으로 변환해 푸는 기법의 착지점이 된다. 셋째, 모든 정사각 부분행렬이 다시 코시 행렬이라 가역이므로, 유한체 위에서 최적 소실 부호의 생성 행렬로 쓰인다.

2. 행렬식과 역행렬

코시 행렬식.

$$\det C = \frac{\prod_{i<j}(x_j - x_i)(y_i - y_j)}{\prod_{i,j}(x_i - y_j)}$$

분자는 반데르몽드 행렬식 두 개의 곱 꼴이다. 그래서 $x$ 끼리, $y$ 끼리 모두 서로 다르면(그리고 분모가 정의되면) 반드시 가역이다. 4×4 무작위 예로 수치 행렬식과 공식을 비교하면 상대오차 $4\times10^{-15}$ 로 일치한다.

부분행렬도 코시다. 행 $i_1, \dots, i_k$ 와 열 $j_1, \dots, j_k$ 를 고르면 그 부분행렬은 점 집합 $\{x_{i_\cdot}\}$, $\{y_{j_\cdot}\}$ 로 만든 코시 행렬이고, 위 공식으로 행렬식이 0 이 아니다. 더 나아가 $x_1 < \cdots < x_n$, $y_1 > \cdots > y_n$, $\min x > \max y$ 이면 모든 소행렬식이 양수인 완전 양행렬(totally positive)이 된다. 5×5 예에서 251개 소행렬식을 다 계산해 확인했다¹.

명시적 역행렬.

$$(C^{-1})_{ij} = \frac{\prod_k(x_j - y_k)\,\prod_k(x_k - y_i)}{(x_j - y_i)\prod_{k\ne j}(x_j - x_k)\prod_{k\ne i}(y_i - y_k)}$$

$O(n^2)$ 에 전체 역행렬이 나온다. 분자·분모가 모두 차의 곱이라 뺄셈이 원 데이터의 차에서만 일어나고, 그 차들이 정확하면 곱셈·나눗셈만 남아 상대오차가 성분 수준에서 작게 유지된다. 조건수가 $10^{16}$ 인 행렬이라도 성분별로 정확한 역행렬을 얻을 수 있다는 뜻이다.

3. 힐베르트 행렬 — 가장 유명한 코시 행렬

$x_i = i$, $y_j = 1 - j$ 로 두면 $x_i - y_j = i + j - 1$ 이므로

$$H_{ij} = \frac{1}{i + j - 1}$$

인 힐베르트 행렬이 된다. 단항식 $\{1, t, t^2, \dots\}$ 의 $[0,1]$ 위 그람 행렬이라, 단항식 기저로 최소제곱 다항식 맞춤을 하면 자연스럽게 나온다. 위 정렬 조건을 만족하므로 완전 양행렬이다. 조건수는

$n$	4	8	10	12	13
$\kappa_2(H_n)$ (배정밀도 계산값)	$1.6\times10^{4}$	$1.5\times10^{10}$	$1.6\times10^{13}$	$1.6\times10^{16}$	$4.5\times10^{18}$

로 대략 $e^{3.5n}$ 씩 커진다. $n = 12$ 부터는 $1/\epsilon_{\text{mach}}$ 를 넘으므로 이 표의 마지막 두 값 자체가 이미 믿을 수 없는 숫자다. $n = 10$ 에서 해가 모두 1 인 방정식을 부분 피벗 가우스 소거로 풀면 최대 오차가 $4.4\times10^{-5}$ 다. 반면 역행렬은 정수 행렬이어서($n = 5$ 의 첫 행은 $25, -300, 1050, -1400, 630$) 위 닫힌꼴로 정확히 쓸 수 있다. 「조건수가 크다」와 「정확히 계산할 수 없다」 는 같은 말이 아니라는 교재용 증거다².

조건수 실측이나 가우스 소거법의 성장 인자 시험에 힐베르트 행렬이 국룰처럼 쓰이는 이유가 이것이다. 정답을 정확히 알고, 크기 하나로 조건수를 마음대로 올릴 수 있다.

4. 변위 구조와 빠른 해법

$D_x = \mathrm{diag}(x_i)$, $D_y = \mathrm{diag}(y_j)$ 라 하면 $(x_i - y_j)C_{ij} = 1$ 이므로

$$D_x C - C D_y = \mathbf 1\mathbf 1^T$$

이다. 오른쪽의 계수(변위 계수)가 1 이다. 오른쪽이 계수 $r$ 인 $\mathbf g\mathbf h^T$ 꼴 합이면 「코시 유사」 행렬이라 부르고, $C_{ij} = \mathbf g_i^T\mathbf h_j/(x_i - y_j)$ 처럼 $O(rn)$ 개 숫자(생성자)로 저장된다.

GKO 알고리즘. 고흐베르크·카일라스·올셰브스키(1995)는 가우스 소거 한 단계가 코시 유사 구조를 보존한다는 점을 이용해, 행렬을 만들지 않고 생성자만 갱신하며 $O(rn^2)$ 에 LU 분해를 한다. 핵심은 행 교환이 구조를 깨지 않는다는 것이다. 행을 바꾸면 $D_x$ 의 대각 순서만 바뀌기 때문이다. 토플리츠 행렬의 레빈슨류 해법은 피벗팅을 못 해서 부분행렬이 특이에 가까우면 불안정해지는데, 토플리츠 행렬을 고속 푸리에 변환으로 코시 유사 행렬로 바꾼 다음 GKO 로 풀면 피벗팅이 있는 $O(n^2)$ 해법이 된다. 「구조를 바꿔서 피벗팅을 산다」 는 발상이다.

행렬-벡터 곱. $\sum_j q_j/(x_i - y_j)$ 는 복소평면에서 점전하의 퍼텐셜 장(2차원 쿨롱 핵)과 같은 꼴이다. 그대로 계산하면 $O(n^2)$ 이지만, 제라술리스(1988)가 다항식 연산으로 $O(n\log^2 n)$ 을 보였고, 실무에서는 고속 다중극자법이 고정 정밀도에서 $O(n)$ 에 계산한다. 1차원 FMM 과 계층 행렬 문헌에서 코시 핵은 「멀리 떨어진 블록이 저계수」 라는 성질을 설명하는 가장 단순한 예다 — $x$ 와 $y$ 가 잘 분리돼 있으면 $1/(x-y)$ 를 짧은 급수로 분리할 수 있어 블록이 저랭크 근사된다.

높은 상대 정확도. 데멜(1999)은 코시 행렬과 그 친척들의 SVD 를 조건수와 무관하게 모든 특이값을 높은 상대 정확도로 계산하는 알고리즘을 냈다. 앞서 본 대로 소행렬식이 원 데이터의 차의 곱으로 정확히 표현되기 때문에 가능한 일이다. 힐베르트 행렬의 가장 작은 특이값($n = 20$ 이면 $10^{-28}$ 급)까지 유효숫자를 지킨다.

5. 소실 부호 — 부분행렬 가역성의 보상

$k$ 개 데이터 블록에 $m$ 개 패리티 블록을 붙여 아무 $m$ 개가 사라져도 복구하려면, 생성 행렬 $[\,I_k;\ P\,]$ 에서 $P$ 의 모든 정사각 부분행렬이 가역이어야 한다(MDS 조건). 코시 행렬은 정의상 이 조건을 만족한다. 유한체 $\mathrm{GF}(2^w)$ 에서 서로 다른 원소 $x_1, \dots, x_m$, $y_1, \dots, y_k$ 를 고르면 $P_{ij} = 1/(x_i + y_j)$ (표수 2 에서는 뺄셈이 덧셈) 가 그대로 MDS 패리티 행렬이 된다.

블뢰머 등(1995)의 코시 리드-솔로몬 부호는 여기에 한 단계를 더해, $\mathrm{GF}(2^w)$ 원소 곱셈을 $w\times w$ 비트 행렬로 바꿔 인코딩·디코딩을 XOR 연산만으로 하게 만들었다. 유한체 곱셈표가 필요 없어 CPU 에서 빠르고, 분산 저장 시스템의 소실 부호 라이브러리(Jerasure 등)가 이 방식을 구현한다. 「행렬식 공식에서 0 이 안 나온다」 는 1841년의 대수 항등식이 RAID-6 너머의 저장 시스템을 지탱하는 셈이다³.

6. 유리 보간과의 연결

점 $y_j$ 에 극을 둔 유리함수 $r(x) = \sum_j c_j/(x - y_j)$ 로 데이터 $(x_i, f_i)$ 를 보간하면 연립방정식의 행렬이 정확히 코시 행렬이다. 분자에도 자유도를 주는 일반화가 뢰브너 행렬 $L_{ij} = (f_i - g_j)/(x_i - y_j)$ 이고, 최근 유리 근사 알고리즘(AAA)과 모형 축약의 뢰브너 프레임워크가 이 행렬의 특이값 분해 위에서 돌아간다. 바리센트릭 보간의 가중치 공식이 코시 행렬식의 비와 같은 모양인 것도 우연이 아니다.

7. 관련 문서

• 반데르몽드 행렬 · 토플리츠 행렬 · 행켈 행렬 · 순환 행렬
• 조건수 · 가우스 소거법 · 바리센트릭 보간 · 저랭크 근사
• 고속 다중극자법 · 계층 행렬 · 고속 푸리에 변환
• 힐베르트 행렬 · 리드-솔로몬 부호 · AAA 알고리즘

8. Footnotes

1. 완전 양행렬은 구조해석의 진동 이론(갠트마허-크레인)에서도 나온다. 보의 강성 행렬 역행렬이 진동 행렬이 되어 고유모드의 마디 개수가 정해진다는 이야기는 또 다른 문서감. ↩

2. 힐베르트 행렬로 자작 선형 솔버를 시험하다가 $n = 13$ 에서 해가 엉망이 되면 솔버 버그를 의심하기 전에 조건수부터 찍어 봐라. 솔버는 무죄인 경우가 대부분이다. ↩

3. 디스크 두 개가 동시에 죽어도 버티는 RAID-6 의 다음 단계가 「아무 $m$ 개」 다. 데이터센터 운영자에게 코시 행렬식은 수학이 아니라 퇴근 시간이다. ↩