스미스 표준형

1. 개요[편집]

스미스 표준형 Smith normal form
무대	주 아이디얼 정역(PID) 위의 행렬 — $\mathbb{Z}$, $F[\lambda]$
형태	$UAV = \mathrm{diag}(d_1,\dots,d_r,0,\dots,0)$, $d_1 \mid d_2 \mid \cdots \mid d_r$
$U,V$	유니모듈러 — 그 환에서 역행렬이 존재
불변인자	$d_k = D_k / D_{k-1}$, $D_k$ = 모든 $k$ 차 소행렬식의 최대공약수
유일성	단원(unit) 배수를 제외하고 유일
동치 관계	상사가 아니라 동치($UAV$) — 층위가 다르다
실무 난점	중간 성분 폭발 → 모듈러/확률 알고리즘

실수체 위에서는 랭크 하나로 끝나는 이야기가, 정수 위에서는 수열 하나가 필요해진다.

스미스 표준형(Smith normal form, SNF)은 주 아이디얼 정역 $R$ 위의 $m\times n$ 행렬 $A$ 를 양쪽에서 유니모듈러 행렬을 곱해 도달하는 대각 형태다. 적당한 $U \in \mathrm{GL}_m(R)$, $V \in \mathrm{GL}_n(R)$ 가 존재해

$$U A V = \begin{bmatrix} d_1 & & & \\ & \ddots & & \\ & & d_r & \\ & & & \mathbf{0}\end{bmatrix}, \qquad d_1 \mid d_2 \mid \cdots \mid d_r$$

가 되고, 이때 $d_k$ 를 불변인자(invariant factor)라 한다. 대각선을 따라 나눗셈 관계가 사슬로 이어진다는 것이 핵심 — 이 사슬 조건이 없으면 대각화는 얼마든지 가능하지만 유일성이 사라진다. 1861년 헨리 존 스티븐 스미스가 정수 연립 부정방정식을 다루면서 정리했다.¹

왜 굳이 이런 물건이 필요한가? 체(field) 위에서는 $UAV$ 로 도달할 수 있는 표준형이 $\mathrm{diag}(1,\dots,1,0,\dots,0)$ 뿐이라 정보라고는 랭크밖에 없다. 그런데 정수환 $\mathbb{Z}$ 처럼 나눗셈이 자유롭지 않은 곳에서는 “2로 나뉘는가”, “3으로 나뉘는가”가 소거로 지워지지 않고 살아남는다. 그 살아남은 정보가 불변인자이고, 그것이 곧 유한생성 아벨군의 구조이자 호몰로지의 꼬임(torsion)이다.

2. 왜 불변인자가 유일한가[편집]

계산 절차보다 먼저 유일성을 짚는 것이 이해에 낫다. $D_k(A)$ 를 $A$ 의 모든 $k \times k$ 소행렬식의 최대공약수라 하자(행렬식 인자, determinantal divisor). 유니모듈러 행렬을 곱해도 각 소행렬식은 다른 소행렬식들의 $R$-계수 선형결합으로 바뀔 뿐이므로 $D_k$ 는 단원 배수를 빼면 변하지 않는다. 그리고 대각 형태에서 $D_k = d_1 d_2 \cdots d_k$ 가 자명하므로

$$d_k = \frac{D_k(A)}{D_{k-1}(A)}, \qquad D_0 := 1$$

이다. 즉 불변인자는 알고리즘의 산물이 아니라 행렬 자체가 갖고 있는 양이고, 어떤 순서로 소거하든 같은 답이 나온다. 나눗셈 사슬 $d_k \mid d_{k+1}$ 은 $D_k^2 \mid D_{k-1}D_{k+1}$ 이라는 소행렬식들 사이의 부등식에서 나온다. 물론 이 공식으로 실제 계산을 하면 $\binom{n}{k}^2$ 개의 행렬식을 다뤄야 하니 이론용이지 실용은 아니다.

계산은 가우스 소거법의 환 버전으로 한다. 행 연산과 열 연산을 둘 다 쓰되, 나눗셈이 안 되는 자리에서는 유클리드 호제법을 행/열 위에서 돌린다. 절대값이 가장 작은 0 아닌 성분을 피벗으로 올리고, 같은 행·열의 나머지 성분을 그 피벗으로 나눈 몫만큼 소거하고, 나머지가 남으면 그것을 새 피벗으로 삼아 반복 — 유클리드 호제법이 끝나듯 유한 번에 끝난다. 첫 행과 첫 열이 청소되면 $d_1$ 이 확정되고, 나머지 블록에 재귀한다. 마지막에 사슬 조건을 어기는 이웃 쌍 $(d_i, d_{i+1})$ 이 있으면 $2\times2$ 조작으로 $(\gcd, \mathrm{lcm})$ 으로 바꿔 정렬한다.

2.1. 작은 예제 둘[편집]

$2\times2$ 대각행렬 두 개면 이 개념의 요점이 전부 드러난다.

$$A = \begin{bmatrix} 2 & 0 \\ 0 & 3\end{bmatrix}, \qquad B = \begin{bmatrix} 2 & 0 \\ 0 & 2\end{bmatrix}$$

둘 다 이미 대각이지만 둘 다 스미스 표준형이 아니다(정확히는 $B$ 만 맞다). $A$ 는 $2 \nmid 3$ 이라 사슬 조건을 어긴다. $D_1(A) = \gcd(2,0,0,3) = 1$, $D_2(A) = |{\det A}| = 6$ 이므로 불변인자는 $(1, 6)$ 이고, 실제로 행·열 연산 몇 번이면 $\mathrm{diag}(1,6)$ 에 도달한다. 군으로 읽으면 $\mathbb{Z}/2 \oplus \mathbb{Z}/3 \cong \mathbb{Z}/6$ — 중국인의 나머지 정리 그 자체다. 반면 $B$ 는 $D_1 = 2$, $D_2 = 4$ 라 $(2,2)$ 가 그대로 답이고, 군은 $\mathbb{Z}/2 \oplus \mathbb{Z}/2$ 로 $\mathbb{Z}/4$ 와 다르다.

행렬식은 둘 다 우변에 있는 정보를 다 담지 못한다는 점도 여기서 보인다. $\mathrm{diag}(1,4)$ 와 $\mathrm{diag}(2,2)$ 는 행렬식이 같지만 서로 동치가 아니고, 대응하는 군도 다르다. 불변인자는 행렬식보다 진짜로 더 많은 것을 안다.

3. 응용 1 — 유한생성 아벨군과 격자[편집]

SNF의 존재 이유 1번은 유한생성 아벨군의 구조정리다. 아벨군 $G$ 를 생성원 $n$ 개와 관계식 $m$ 개로 제시하면 관계행렬 $A \in \mathbb{Z}^{m\times n}$ 이 나오고 $G \cong \mathbb{Z}^n / A^{\top}\mathbb{Z}^m$ 이다. 여기에 $UAV$ 를 걸면 생성원과 관계식을 동시에 좌표변환하는 것이 되어

$$G \;\cong\; \mathbb{Z}^{\,n-r} \oplus \mathbb{Z}/d_1 \oplus \mathbb{Z}/d_2 \oplus \cdots \oplus \mathbb{Z}/d_r$$

가 즉시 읽힌다. $d_i = 1$ 인 항은 자명군이라 사라지고, 남은 것이 꼬임 부분, $n - r$ 이 자유 랭크다. 교과서가 “구조정리”라 부르며 한 장을 쓰는 내용이 행렬 하나를 대각화하는 절차로 환원되는 것이다. 유한생성 아벨군의 분류가 곧 SNF라고 말해도 크게 틀리지 않는다.

격자(lattice) 쪽에서도 같은 도구가 쓰인다. $\Lambda' \subseteq \Lambda \subseteq \mathbb{Z}^n$ 인 부분격자의 지수는 $[\Lambda : \Lambda'] = \prod_i d_i$ 이고, 두 격자가 같은지 판정하는 것도 불변인자 비교로 끝난다. 다만 여기서 자주 혼동되는 이웃이 있다 — 에르미트 표준형(HNF)은 열 연산만 쓰는 한쪽 표준형이라 격자의 정규 기저를 주고, SNF는 양쪽을 다 써서 부분격자 쌍의 관계를 준다. 정수 선형계 $Ax = b$ 의 정수해 존재 판정과 일반해 기술은 두 형태 모두로 가능하지만, 정수해 하나를 구하는 실무는 대개 HNF 쪽이 싸다. 정수계획법에서 절단면을 유도할 때 등장하는 것도 보통 HNF다.

4. 응용 2 — 호몰로지 계산[편집]

위상수학 쪽 응용은 더 기계적이다. 단체 복합체의 경계 사상 $\partial_k : C_k \to C_{k-1}$ 을 $\mathbb{Z}$ 성분 행렬로 쓰고 각각의 SNF를 구하면, 호몰로지군

$$H_k = \ker \partial_k / \mathrm{im}\,\partial_{k+1}$$

의 구조가 랭크와 불변인자만으로 나온다. 베티 수는 $\beta_k = \dim\ker\partial_k - \mathrm{rank}\,\partial_{k+1}$ 이고, $\partial_{k+1}$ 의 1이 아닌 불변인자들이 그대로 꼬임 계수가 된다. 클라인 병에서 $H_1 = \mathbb{Z}\oplus\mathbb{Z}/2$ 의 그 $\mathbb{Z}/2$ 가 어디서 나오냐면, 경계행렬 SNF의 대각선에 앉은 2에서 나온다.

규모 감각을 위해 덧붙이면, 실제 계산에서 경계행렬은 극도로 희소하다. $k$-단체 하나의 경계는 $k+1$ 개 면뿐이므로 열마다 0 아닌 성분이 상수 개다. 그런데 소거를 진행하면 채움(fill-in) 이 폭발적으로 일어나 밀집 행렬이 되어 버리고, 그 순간 메모리가 먼저 죽는다. 그래서 위상 데이터 분석 쪽 구현은 소거 순서를 채움 최소화 기준으로 고르거나, 아예 공동경계(coboundary) 방향으로 계산하는 등 희소행렬 직접법에서 하던 고민을 그대로 반복한다. 정확 산술이라 반올림 걱정은 없는 대신, 채움과 성분 폭발이 두 배로 온다.

여기서 실용적인 갈림길이 하나 있다. 요즘 데이터 분석에서 쓰는 지속 호몰로지는 대개 체 위에서 계산한다($\mathbb{Z}/2$ 가 국룰). 체 위에서는 꼬임이 원리적으로 존재하지 않아 SNF가 랭크 계산으로 붕괴하고, 대신 훨씬 빠른 소거를 쓸 수 있기 때문이다. 즉 ”$\mathbb{Z}$ 대신 $\mathbb{Z}/2$ 로 계산한다”는 선택은 편의가 아니라 정보를 일부 버리고 속도를 사는 거래다. 전자기 수치해석의 이산 미분형식·트리-코트리 분해에서 코호몰로지 생성원을 뽑을 때도 같은 계산이 등장하며, 이쪽은 꼬임이 없다는 것이 사전에 보장되는 경우가 많아 정수 SNF까지 갈 일이 드물다.

5. 성분 폭발 — 이 알고리즘의 진짜 적[편집]

교과서 절차를 그대로 코딩하면 반드시 터진다. 최종 답의 성분은 작은데 중간 계산의 성분이 천문학적으로 커지는 현상, 곧 성분 폭발(entry explosion / intermediate expression swell)이다. 성분이 두세 자리인 $20\times20$ 정수 행렬에서 중간 항이 수백~수천 자리로 자라는 일이 예사롭게 일어난다. 부동소수점의 반올림 오차와는 정반대 성격의 재앙이다 — 답은 정확한데 시간과 메모리가 죽는다.²

원인은 단순하다. 소거 한 번마다 성분이 두 수의 곱 규모로 커지는데, 정확 산술에서는 그것이 반올림으로 잘리지 않고 그대로 쌓인다. 처방은 세 갈래다.

• 피벗 전략. 절대값이 가장 작은 성분을 피벗으로 고르고, 나눗셈이 딱 떨어지는 자리를 우선한다. 공짜로 몇 자릿수를 아끼지만 최악의 경우를 막지는 못한다.
• 모듈러 알고리즘. 마지막 불변인자 $d_r$ 은 $D_r$ 의 약수이고 $D_r$ 은 계산 가능한 상계를 가지므로, 적당한 법 $N$ ($d_r$ 의 배수)을 잡아 $\mathbb{Z}/N$ 위에서 소거하면 성분 크기가 원천적으로 묶인다. 도미치-칸난-트로터(1987)의 아이디어이고, 여러 소수로 나눠 계산한 뒤 중국인의 나머지 정리로 합치는 변형이 표준이다.
• 다항식 시간 보장. 칸난-바켐(1979)이 HNF/SNF를 성분 크기까지 포함해 다항식 시간에 계산할 수 있음을 처음 보였고, 스토르요한(1990년대)의 라스베이거스 알고리즘이 행렬 곱 지수에 가까운 복잡도까지 끌어내렸다. 오늘날 SageMath·PARI·LinBox 같은 컴퓨터 대수 시스템 안에 들어 있는 것이 이 계열이다.

선택지를 한 표로 정리하면 이렇다.

방법	성분 크기	특징
교과서 소거 (피벗 없음)	폭발	손계산·증명용. 코드로 쓰면 죽는다
최소 성분 피벗	완화	구현이 쉽고 작은 문제엔 충분
모듈러 + 중국인의 나머지	유계	실무 표준. 법을 잘못 고르면 재시도
라스베이거스 (스토르요한)	유계	무작위성 사용, 점근 최적에 근접
부동소수점	—	하면 안 된다

부동소수점 연산으로는 SNF를 계산하지 않는다. 불변인자는 성분에 대해 극단적으로 불연속이라($\mathrm{diag}(2,2)$ 에서 성분 하나를 1만큼 흔들면 대각이 $(1, 4)$ 로 바뀔 수 있다) 반올림이 한 번만 끼어도 답이 완전히 달라진다. 최소다항식이나 조르당 표준형이 부동소수점에서 계산 불가인 것과 같은 종류의 불연속이며, 여기서는 아예 정확 산술이 대안이 아니라 유일한 선택지다.

6. 다항식 행렬 — 그리고 조르당과의 층위 차이[편집]

$R = F[\lambda]$ 로 무대를 옮기면 곧바로 선형대수로 되돌아온다. $\lambda I - A$ 의 SNF를 구하면 불변인자 $d_1 \mid \cdots \mid d_n$ 이 나오고

• $d_n$ = $A$ 의 최소다항식,
• $d_1 d_2 \cdots d_n$ = 특성다항식,
• 1이 아닌 불변인자들 → 유리 표준형의 동반행렬 블록

이 된다. 그리고 결정적인 정리 하나가 두 세계를 잇는다.

$A$ 와 $B$ 가 $F$ 위에서 상사($B = S^{-1}AS$) $\iff$ $\lambda I - A$ 와 $\lambda I - B$ 가 $F[\lambda]$ 위에서 동치($\lambda I - B = U(\lambda)(\lambda I - A)V(\lambda)$).

여기서 층위를 반드시 구분해야 한다. SNF 자체는 상사 불변량이 아니다. 성분이 수인 행렬 $A$ 의 SNF를 $\mathbb{Z}$ 나 $F$ 위에서 구하면 그것은 동치류의 불변량일 뿐이고, 체 위에서는 랭크밖에 안 나온다. 상사 정보를 뽑으려면 반드시 $\lambda I - A$ 라는 다항식 행렬로 한 층 올라가야 한다. “스미스 표준형과 조르당 표준형이 어떻게 다르냐”는 질문의 정답은 “둘 다 표준형이지만 동치 관계가 다르다”이고, 굳이 짝을 지으면 $\lambda I - A$ 의 SNF ↔ 유리 표준형, 그 불변인자를 기약 인수로 쪼갠 초등인자 ↔ 조르당 형이다.³

일반 다항식 행렬 $P(\lambda)$ 의 SNF는 제어공학에서 그대로 쓰인다. 유리 전달함수 행렬 $G(\lambda) = N(\lambda)/d(\lambda)$ 에 같은 축약을 걸면 스미스-맥밀런 형이 나오고, 그 대각 성분의 분자·분모가 다변수 시스템의 영점과 극점을 정의한다. SISO에서는 자명하던 “극점과 영점”이 MIMO에서 왜 그렇게 까다로운지, 왜 전달함수 성분마다 따로 세면 안 되는지가 여기서 설명된다 — 구조적 특이값 기반 강건제어 문헌이 첫 장에서 이 형태를 깔고 시작하는 이유다.

7. 관련 문서[편집]

• 유리 표준형 · 조르당 표준형 · 최소다항식 · 케일리-해밀턴 정리
• 행렬식 · 수반행렬 · 가우스 소거법 · 유클리드 호제법
• 유한생성 아벨군 · 호몰로지 · 에르미트 표준형 · 정수계획법
• 부동소수점 연산 · 조건수 · 구조적 특이값

8. Footnotes[편집]

1. 스미스는 정수론 쪽 사람이었고, 논문 제목도 “On systems of linear indeterminate equations and congruences”(1861)로 부정방정식이 주인공이다. 100년 넘게 지나 위상수학자와 컴퓨터 대수 하는 사람들이 이 정리를 주력 도구로 쓰게 될 줄은 본인도 몰랐을 것이다. 참고로 여기서 말하는 스미스는 스미스 예측기의 오토 스미스와 다른 사람이다. 이 바닥에 스미스가 너무 많다. ↩

2. 정확 산술을 처음 다루는 사람이 반드시 겪는 문화 충격이다. 부동소수점에서는 “숫자가 커지면 지수부가 커질 뿐”이라 시간이 변하지 않는데, 다중정밀 정수는 자릿수에 비례해(곱셈은 그 이상으로) 느려진다. while 루프가 도는 동안 메모리 사용량 그래프가 지수로 치솟는 것을 보고 나서야 “아, 이건 알고리즘이 아니라 산술이 문제구나”를 깨닫는다. ↩

3. 이 구분을 놓치면 “실수 행렬의 스미스 표준형을 구해 고유값을 얻자”는 식의 시도가 나온다. 실수체 위에서 $A$ 의 SNF는 가역이면 무조건 단위행렬이므로 아무 정보도 없다. 얻어지는 것은 “랭크가 $n$ 이다” 뿐인데, 그건 애초에 알고 있던 사실이다. ↩