그람 행렬

1. 개요

그람 행렬 Gram matrix
정의	$G_{ij} = \langle v_i, v_j\rangle$ — 벡터(함수)들의 내적 표
행렬 꼴	$G = A^{\mathsf T}A$ ($v_i$ 가 $A$ 의 열)
성질	대칭 양의 준정부호, $\mathrm{rank}\,G = \mathrm{rank}\,A$
행렬식	$\det G$ = $v_i$ 가 만드는 평행체 부피의 제곱
조건수	$\kappa_2(G) = \kappa_2(A)^2$
다른 이름	질량 행렬(FEM), 커널 행렬(기계학습), 정규방정식 행렬

내적만 알면 기하가 다 나온다. 길이·각도·부피·거리 전부가 이 표 하나에 들어 있다. 대신 조건수가 제곱으로 들어간다는 청구서가 붙는다.

그람 행렬(Gram matrix)은 내적 공간의 벡터 $v_1, \dots, v_n$ 에 대해 성분이 $G_{ij} = \langle v_i, v_j\rangle$ 인 $n\times n$ 행렬이다. 벡터가 $\mathbb{R}^m$ 의 열벡터이고 그것을 $A = [v_1 \cdots v_n]$ 로 묶으면 $G = A^{\mathsf T}A$ 다. 이름은 덴마크 수학자 외르겐 페데르센 그람(1883년 최소자승 급수 전개 논문)에서 왔다 — 그람-슈미트 직교화의 그 그람이다.¹

시뮬레이션 코드에서 그람 행렬은 이름표를 바꿔 달고 곳곳에 나온다. 최소자승법의 정규방정식 행렬 $A^{\mathsf T}A$, 유한요소법의 질량 행렬 $M_{ij} = \int \phi_i\phi_j$, 커널 기계학습의 커널 행렬 $K_{ij} = k(x_i, x_j)$, 힐베르트 행렬(단항식의 그람), 동적 모드 분해·적합직교분해의 스냅숏 상관 행렬이 모두 그람 행렬이다. 이 문서는 그 공통 구조 — 양의 준정부호성, 행렬식의 기하학, 조건수 제곱, 그리고 「그람을 만들까 말까」의 수치적 판단 — 를 다룬다.

2. 기본 성질

• 양의 준정부호. $x^{\mathsf T}Gx = \|\sum x_iv_i\|^2 \ge 0$. 등호는 $\sum x_iv_i = 0$ 일 때뿐이므로 $G$ 가 양의 정부호 ⇔ $v_i$ 가 선형독립이다. 거꾸로 모든 대칭 양의 준정부호 행렬은 어떤 벡터들의 그람 행렬이다($G = LL^{\mathsf T}$ 의 $L$ 의 행을 쓰면 된다). 즉 「양의 준정부호 행렬」과 「그람 행렬」은 같은 집합이다.
• 랭크. $\mathrm{rank}\,G = \mathrm{rank}\,A$, $\ker G = \ker A$.
• 촐레스키 = 그람-슈미트. $A = QR$ 이면 $G = R^{\mathsf T}R$. 즉 그람 행렬의 촐레스키 분해 인수가 $A$ 의 QR 분해의 $R$ 이다(부호 관례 제외). 정확 산술에서 그람-슈미트와 그람의 촐레스키는 같은 계산이다.
• 고유값 = 특이값 제곱. $G$ 의 고유값은 $A$ 의 특이값의 제곱이다. 여기서 $\kappa_2(G) = \kappa_2(A)^2$ 가 나온다.

3. 그람 행렬식 — 부피

$\det G$ 를 그람 행렬식(Gramian)이라 부른다. $\det G = \mathrm{vol}(v_1,\dots,v_n)^2$, 곧 $v_i$ 들이 만드는 $n$ 차원 평행체 부피의 제곱이다. $n=2$ 이면 $\|v_1\|^2\|v_2\|^2 - \langle v_1,v_2\rangle^2$ 이라 코시-슈바르츠 부등식이 「$\det G \ge 0$」 한 줄로 요약된다.

여기서 바로 아다마르 부등식 $\det G \le \prod_i G_{ii} = \prod_i \|v_i\|^2$ 이 나온다. 평행체 부피는 변 길이의 곱을 넘지 못하고, 등호는 직교일 때다. 실제로 무작위 $5\times3$ 행렬의 그람에서 $\det G = 11.5$, 대각곱 $24.0$ 이었다. 비율 $\det G/\prod G_{ii}$ 는 「얼마나 직교에 가까운가」의 척도가 되는데, 실험계획법의 D-최적 설계가 정보 행렬(그람 행렬)의 행렬식을 최대화하는 것이 같은 직관이다.

부분공간까지의 거리도 그람 행렬식의 비로 쓴다. $v$ 에서 $\mathrm{span}(v_1, \dots, v_n)$ 까지의 거리 $d$ 는

$$d^2 = \frac{\det G(v_1,\dots,v_n,v)}{\det G(v_1,\dots,v_n)}$$

이다. 뮌츠-사스 정리 계열의 근사 이론 증명이 이 식으로 굴러간다.

4. 조건수 제곱 — 정규방정식의 함정

$\kappa(G) = \kappa(A)^2$ 는 그람 행렬을 만드는 순간 정보를 잃는다는 뜻이다. 최소자승 $\min\|Ax - b\|$ 를 정규방정식 $A^{\mathsf T}Ax = A^{\mathsf T}b$ 로 풀면 오차가 $\kappa(A)^2u$ 로 자란다. 반면 QR 분해나 SVD 로 직접 풀면 (잔차가 작은 문제에서) $\kappa(A)u$ 다. 배정밀도에서 특이값을 지정한 $100\times10$ 행렬로 재면:

$\kappa(A)$	$\kappa(A^{\mathsf T}A)$	정규방정식 상대오차	QR/SVD 상대오차
$10^4$	$1.0\times10^{8}$	$4.0\times10^{-10}$	$8.2\times10^{-14}$
$10^8$	$8.9\times10^{15}$	$3.8\times10^{-2}$	$6.2\times10^{-10}$

$\kappa(A) = 10^8$ 에서 정규방정식은 두 자리밖에 못 건진다.² 게다가 $\kappa(A) \gtrsim u^{-1/2} \approx 10^8$ 이면 계산된 $A^{\mathsf T}A$ 가 반올림만으로 양의 정부호성을 잃어 촐레스키가 실패할 수 있다. ($\kappa(G)$ 가 $10^{16}$ 이 아니라 $8.9\times10^{15}$ 로 찍히는 것부터가 이미 반올림에 먹힌 값이다.)

그래도 그람을 만드는 쪽이 이기는 경우가 있다.

• $A$ 가 매우 길쭉할 때($m \gg n$). $A^{\mathsf T}A$ 는 한 번의 행렬곱(BLAS-3)이고 병렬로 쪼개 더하면 통신이 $n\times n$ 하나뿐이다. 이게 그람-슈미트 문서의 CholeskyQR 이다. 직교성 손실이 $\kappa^2u$ 라는 약점은 한 번 더 돌리는 CholeskyQR2(후카야 외 2014)로 메우는데, 첫 번째 결과가 망가지지 않을 만큼($\kappa(A) \lesssim u^{-1/2}$) 조건이 좋을 때만 통한다.
• 문제가 원래 그람 형태로 주어질 때. 커널 방법·갈레르킨 방법에서는 $A$ 가 없고 내적만 있다. 그 경우 조건수 제곱은 「만드는 과정」의 손실이 아니라 문제 자체의 조건이다.

5. 함수의 그람 — 질량 행렬과 기저 선택

함수 공간에서 기저 $\phi_1,\dots,\phi_n$ 의 $L^2$ 그람 행렬 $M_{ij} = \int\phi_i\phi_j\,dx$ 를 FEM 에서는 질량 행렬이라 부른다. $L^2$ 최적 근사 $\min\|f - \sum c_j\phi_j\|$ 의 정규방정식이 $Mc = b$, $b_i = \int f\phi_i$ 이고, 시간 의존 문제 $M\dot u + Ku = f$ 에서도 시간미분 앞에 이 행렬이 붙는다.

그람의 조건수는 기저가 얼마나 직교에 가까운가를 잰다. 극단적인 두 경우를 비교하면 이렇다.

• 단항식 $1, x, \dots, x^{n-1}$ on $[0,1]$. 그람이 힐베르트 행렬이고 $n=10$ 에서 $\kappa \approx 1.6\times10^{13}$ 이다. 기저가 거의 평행하다.
• 1차 모자 함수(P1) on 균일 격자. 질량 행렬이 $\tfrac{h}{6}\,\mathrm{tridiag}(1,4,1)$ 이고 조건수가 $n=10$ 에서 2.84, $n=100$ 에서 2.998, $n=1000$ 에서 3.000 이다. 격자를 아무리 촘촘히 해도 3 으로 묶인다. 와튼(1987)은 이를 일반화해, 준균일 격자의 질량 행렬은 대각 성분으로 스케일하면 요소 질량 행렬의 고유값 범위로 조건수가 묶임을 보였다. 강성 행렬이 $O(h^{-2})$ 로 나빠지는 것과 대조적이고, 그래서 질량 행렬은 켤레기울기법에 대각 전처리기만 붙여도 반복 몇 번에 풀린다.

고차 요소에서는 요소 안 기저 선택이 다시 문제가 된다. $[-1,1]$ 의 등간격 절점 라그랑주 기저로 요소 질량 행렬 조건수를 재면 차수 $p = 1, 2, 4, 8$ 에서 각각 $3.0$, $6.9$, $14$, $220$ 이다. 직교 르장드르 다항식 기저로 바꾸면 그람이 대각이 되어 조건수는 정규화 상수 비뿐이다. 스펙트럴 요소법이 가우스-로바토 절점과 직교 기저를 쓰는 이유의 절반이 이것이다.

6. 커널 행렬 — 내적을 직접 정의할 때

커널 방법은 특징 벡터 $\varphi(x)$ 를 만들지 않고 $k(x, y) = \langle\varphi(x), \varphi(y)\rangle$ 만 정의한다. 데이터 점들의 커널 행렬 $K_{ij} = k(x_i, x_j)$ 가 곧 보이지 않는 특징 벡터들의 그람 행렬이다. 그래서 「유효한 커널」의 조건은 모든 유한 점 집합에서 $K$ 가 양의 준정부호인 것이다(머서 조건). 서포트 벡터 머신·가우시안 프로세스·크리깅이 이 행렬을 쓴다.

수치적으로는 앞의 이야기가 그대로 반복된다. 가우스 커널에서 점이 촘촘하거나 폭이 넓으면 행이 거의 같아져 $K$ 가 수치적으로 특이해지고, 실무에서는 대각에 작은 「너깃」(nugget) $\epsilon I$ 를 더해 촐레스키를 살린다. $n$ 이 커서 $O(n^3)$ 촐레스키가 안 되면 나이스트룀 근사나 무작위 푸리에 특징으로 저랭크 그람을 대신 쓴다.

7. 거리에서 그람으로 — 고전적 MDS

점들 사이의 거리만 알 때도 그람 행렬을 복원할 수 있다. $D^{(2)}_{ij} = \|p_i - p_j\|^2$ 이고 $J = I - \tfrac1n\mathbf{1}\mathbf{1}^{\mathsf T}$ (중심화 행렬)이면

$$G = -\tfrac12\, J\,D^{(2)}J$$

가 무게중심을 원점으로 옮긴 점들의 그람 행렬이다. 쇤베르크(1935)의 정리는 이걸 뒤집는다 — 대칭 비음수 행렬 $D^{(2)}$ 가 유클리드 공간의 점 배치에서 온 거리 제곱 행렬일 필요충분조건은 $-\tfrac12 JD^{(2)}J$ 가 양의 준정부호인 것이고, 그때의 랭크가 필요한 최소 차원이다. 평면의 6개 점으로 해 보면 $G$ 의 고유값이 $(0, 0, 0, 0, 1.109, 3.357)$ 로 정확히 둘만 남는다(나머지 넷은 $10^{-15}$ 수준).

다차원 척도법의 고전판(토거슨 1952)은 이 $G$ 의 상위 $k$ 개 고유쌍으로 점을 $k$ 차원에 놓는다. 거리가 유클리드가 아니면(측지 거리, 비유사도) 음의 고유값이 나오고, 그 크기가 「유클리드로 얼마나 못 펴지는가」의 척도다. 다양체 학습의 아이소맵이 측지 거리로 이 계산을 한다.

8. 열린 질문 — 양수 그람

모든 성분이 비음수인 벡터들(즉 $v_i \in \mathbb{R}^m_{\ge0}$)의 그람 행렬을 완전 양행렬(completely positive matrix)이라 한다. 「양의 준정부호이고 성분이 비음수」(이중 비음수)는 필요조건일 뿐이고, $5\times5$ 부터는 충분하지 않다. 주어진 행렬이 완전 양인지 판정하는 문제는 NP-난해로 알려져 있고, 조합 최적화 문제를 이 행렬 원뿔 위의 선형계획으로 정확히 다시 쓸 수 있다는 점에서 최적화 이론의 관심사다. 반정부호 계획법이 양의 준정부호 원뿔 위에서 다루기 쉬운 이유와, 완전 양 원뿔 위에서 어려운 이유가 대조를 이룬다³.

9. 관련 문서

• 그람-슈미트 · 촐레스키 분해 · QR 분해 · 최소자승법 · 조건수 · 특이값 분해
• 힐베르트 행렬 · 유한요소법 · 르장드르 다항식 · 스펙트럴 요소법 · 전처리기
• 서포트 벡터 머신 · 가우시안 프로세스 · 나이스트룀 근사 · 다차원 척도법 · 다양체 학습
• 반정부호 계획법 · 완전 양행렬 · 코시-슈바르츠 부등식 · D-최적 설계

10. Footnotes

1. 그람은 수학자이면서 보험계리사였고 덴마크 보험회사를 직접 세웠다. 최소자승 급수 전개 논문도 사망률 표를 맞추려다 나왔다는 게 정설. 현생이 연구를 낳은 모범 사례. ↩

2. 수치해석 수업에서 「정규방정식으로 최소자승을 풀지 마라」는 거의 십계명급으로 반복된다. 그런데 $\kappa(A)$ 가 $10^3$ 쯤인 문제에서는 정규방정식도 열 자리를 건지고 훨씬 빠르다. 계명이 아니라 「$\kappa^2 u$ 를 계산해 보고 결정하라」가 정확한 버전이다. ↩

3. 이름이 헷갈리는 3종 세트: 양의 정부호(positive definite), 양행렬(positive matrix, 성분이 다 양수), 완전 양(completely positive). 셋 다 「양」인데 전부 다른 뜻이다. 「총양행렬」(totally positive, 모든 소행렬식이 양수)까지 끼면 4종 세트가 되며, 이건 또 반데르몽드 행렬·코시 행렬 쪽 이야기다. ↩