스미스 표준형

1. 개요

스미스 표준형은 주 아이디얼 정역 R 위의 m×n 행렬 A에 대해 가역 행렬 P와 Q, 그리고 R의 원소 d1, d2, ..., dr을 사용하여 PAQ 꼴로 변환한 형태를 말한다. 여기서 di는 0이 아니고 d1은 d2를, d2는 d3을 나누는 관계를 가지며, 이러한 di는 가역원 곱셈까지 유일하게 결정된다. 스미스 표준형은 행렬의 불변 인자를 계산하고, 알고리즘을 통해 구할 수 있으며, 유한 생성 가군의 구조, 호몰로지 계산, 제어 이론, 닮음 판별 등 다양한 분야에 응용된다. 이 정리는 헨리 존 스티븐 스미스의 이름을 따서 명명되었다.

2. 정의

주 아이디얼 정역 $R$ (예를 들어, 정수환 $\backslash mathbb\; Z$ 또는 체 계수 일변수 다항식환 $K[x]$) 위의 임의의 $m\backslash times\; n$ 행렬 $A\backslash in\backslash operatorname\{Mat\}(m,n;R)$에 대하여, 다음 조건을 만족시키는 가역 행렬 $P\backslash in\backslash operatorname\{GL\}(m;R)$와 $Q\backslash in\backslash operatorname\{GL\}(n;R)$ 및 유한 개의 원소 $d\_1,d\_2,\backslash dots,d\_r\backslash in\; R$가 존재한다.

:$PAQ=$
\begin{pmatrix}
d_1 \\
& d_2 \\
&& \ddots \\
&&& d_r \\
&&&& 0_{(m-r)\times(n-r)} \\
\end{pmatrix}

:$d\_i\backslash ne\; 0\backslash qquad(i=1,2,\backslash dots,r)$

:$d\_1\backslash mid\; d\_2\backslash mid\backslash cdots\backslash mid\; d\_r$

(여기서 $0\_\{(m-r)\backslash times(n-r)\}$는 $(m-r)\backslash times(n-r)$ 영행렬이다.)

이때, $d\_1,\; d\_2,\; \backslash dots,\; d\_r$은 가역원배의 차이를 무시하면 유일하며, 이를 $A$의 스미스 표준형이라고 한다. 이 원소들은 기본 약수, 불변량 또는 불변 인수라고도 불린다.

2.1. 불변 인자 계산

영역 $R$에 대한 0이 아닌 $m\; \backslash times\; n$ 행렬 $A$가 주어졌을 때, 다음을 만족하는 가역 $m\; \backslash times\; m$ 행렬 $S$와 $n\; \backslash times\; n$ 행렬 $T$가 존재한다.

:$SAT\; =\; \backslash begin\{pmatrix\}$
\alpha_1 & 0 & 0 & \cdots & 0 & \cdots & 0 \\
0 & \alpha_2 & 0 & & & & \\
0 & 0 & \ddots & & \vdots & & \vdots\\
\vdots & & & \alpha_r & & & \\
0 & & \cdots & & 0 & \cdots & 0 \\
\vdots & & & & \vdots & & \vdots \\
0 & & \cdots & & 0 & \cdots & 0
\end{pmatrix}.

여기서 대각선 요소 $\backslash alpha\_i$는 모든 에 대해 $\backslash alpha\_i\; \backslash mid\; \backslash alpha\_\{i+1\}$을 만족한다. 이 대각 행렬은 행렬 $A$의 스미스 표준형이다. $\backslash alpha\_i$는 단위를 곱하는 것을 제외하면 고유하며, 불변 인수라고 불린다. 불변 인수는 다음 공식을 통해 계산할 수 있다.

:$\backslash alpha\_i\; =\; \backslash frac\{d\_i(A)\}\{d\_\{i-1\}(A)\},$

여기서 $d\_i(A)$($i$번째 행렬식 약수라고 함)는 행렬 $A$의 모든 $i\backslash times\; i$ 소행렬식의 행렬식의 최대공약수이고, $d\_0(A):=1$이다.

예시 : $2\backslash times2$ 행렬의 경우, $\{\backslash rm\; SNF\}\{a~~b\backslash choose\; c~~d\}$
= {\rm diag}(d_1, d_2/d_1)이며, $d\_1\; =\; \backslash gcd(a,b,c,d)$이고 $d\_2\; =\; |ad-bc|$이다.

3. 알고리즘

스미스 표준형 알고리즘은 주어진 행렬을 특정 조건을 만족하는 대각 행렬로 변환하는 방법이다. 이 알고리즘은 주로 다음 두 가지 기본 연산을 사용한다.

1. 행 또는 열 교환: 행렬의 두 행 또는 두 열의 위치를 바꾼다.
2. 행 또는 열에 대한 선형 결합: 한 행 또는 열에 다른 행 또는 열의 배수를 더한다.

이러한 연산들을 통해, 주어진 행렬을 스미스 표준형으로 변환할 수 있다. 스미스 표준형은 다음 조건을 만족하는 대각 행렬이다.

* 대각 성분은 0 또는 어떤 수이다.
* 0이 아닌 대각 성분들은 행렬의 왼쪽 위부터 시작하여 대각선 방향으로 나타난다.
* 0이 아닌 각 대각 성분은 다음 대각 성분을 나눈다.

이 알고리즘의 핵심은 주어진 행렬 $A$에 대해, $S\; A\; T$가 대각 행렬이 되는 가역 행렬 $S$와 $T$를 찾는 것이다. 여기서 $S$는 $A$에 적용되는 행 연산을, $T$는 열 연산을 나타낸다. 이러한 행렬 $S$와 $T$는 다음과 같이 찾을 수 있다.

1. 초기화: $S$와 $T$를 항등 행렬로 설정한다.
2. 반복: $A$에 행 연산을 적용할 때마다 $S$를 수정하고, 열 연산을 적용할 때마다 $T$를 수정한다. 이 과정을 통해 $A$를 점진적으로 대각 행렬로 변환한다.
3. 불변성 유지: 이 과정에서 $A\text{'}\; =\; S\text{'}\; \backslash cdot\; A\; \backslash cdot\; T\text{'}$라는 불변 관계식이 유지된다. 여기서 $A\text{'},\; S\text{'},\; T\text{'}$는 현재 값을, $A$는 원래 행렬을 나타낸다.

이 알고리즘은 유일 인수 분해 정역 및 베주 정역의 성질, 즉 행렬의 각 원소가 유일한 인수 분해를 가지며 최대공약수를 통해 선형 결합을 표현할 수 있다는 점을 활용한다.

3.1. 피벗 선택

행렬의 스미스 표준형은 두 행 또는 두 열을 교환하거나, 한 행 또는 열에 다른 행 또는 열의 배수를 더하는 연산을 통해 구할 수 있다. 유일 인수 분해 정역 $R$에서 0이 아닌 모든 원소 $r$은 유일한 인수 분해를 가지며, $l(r)$은 $r$의 소인수 중복집합의 크기를 나타낸다.

$R$ 위의 $2\backslash times\; 2$ 행렬을 예로 들어 설명한다.
:$$
\begin{pmatrix}
a & b \\
c & e
\end{pmatrix}

베주 정역 $R$에서 $a$와 $b$의 최대공약수 $d$에 대해 $d=ua+vb$인 $u,v\backslash in\; R$가 존재한다. $a=da\text{'}$, $b=db\text{'}$라고 하면, $ua\text{'}+vb\text{'}=1$이 성립한다. 따라서 다음 행렬은 가역 행렬이다.
:$$
\begin{pmatrix}
u & -b' \\
v & a'
\end{pmatrix}

이 행렬을 이용하여 원래 행렬을 변형하면 다음과 같다.
:$$
\begin{pmatrix}
a & b \\
c & e
\end{pmatrix}
\begin{pmatrix}
u & -b' \\
v & a'
\end{pmatrix}
=
\begin{pmatrix}
d & 0 \\
uc+vd & -b'c+a'd
\end{pmatrix}

왼쪽에 가역 행렬을 곱하는 방식으로도 첫 행 첫 열 성분을 $a$와 $c$의 최대공약수로, 둘째 행 첫 열 성분을 0으로 만들 수 있다.

일반적인 $m\backslash times\; n$ 행렬 $A$의 경우, $A=0$이면 스미스 표준형이다. $A\backslash ne\; 0$일 때, 행과 열 교환을 통해 $A\_\{11\}\backslash ne\; 0$으로 만들 수 있다. ($l(A\_\{11\})$가 가장 작도록 교환하는 것이 일반적이다.)

만약 모든 $i,j=2,\backslash dots,n$에 대해 $A\_\{11\}\backslash mid\; A\_\{ij\}$라면, 각 행과 열에 첫 행/열의 배수를 더해 첫 행과 첫 열의 $A\_\{11\}$을 제외한 모든 성분을 0으로 만들 수 있다. 그렇지 않다면, $A\_\{11\}\backslash nmid\; A\_\{12\}$이거나 $A\_\{11\}\backslash nmid\; A\_\{21\}$이라고 가정할 수 있다.

$A\_\{11\}\backslash nmid\; A\_\{12\}$라고 가정하면, 다음을 만족하는 가역 행렬 $Q\text{'}$이 존재한다.
:$$
\begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{pmatrix}
Q'=
\begin{pmatrix}
A'_{11} & 0 \\
A'_{21} & A'_{22}
\end{pmatrix}

:$A\text{'}\_\{11\}=\backslash gcd\backslash \{A\_\{11\},A\_\{12\}\backslash \}$

이때, $Q\text{'}$를 확장한 다음 행렬 $Q$는 가역 행렬이다.
:$Q=$
\begin{pmatrix}
Q' & 0 \\
0 & 1_{(n-2)\times(n-2)}
\end{pmatrix}

$AQ$의 첫 행 첫 열 성분은 $A\text{'}\_\{11\}$이며,

최종적으로 $A$는 다음과 같은 형태의 행렬과 동치가 된다.
:$$
\begin{pmatrix}
d_1 & 0 \\
0 & A'
\end{pmatrix}

:$d\_1\backslash mid\; A\text{'}\_\{ij\}\backslash qquad(\backslash forall\; i,j)$

$A\text{'}$에 대해 같은 과정을 반복하면 다음과 같은 행렬을 얻는다.
:$$
\begin{pmatrix}
d_1 & 0 \\
0 & d_2 \\
&& A
\end{pmatrix}

:$d\_1\backslash mid\; d\_2\backslash mid\; A$_{ij}\qquad(\forall i,j)

이 과정을 반복하면 스미스 표준형을 얻을 수 있다.

피벗 선택

스미스 표준형 알고리즘에서 피벗은 행렬의 특정 위치에 있는 원소를 의미하며, 이 원소를 기준으로 행렬을 변형한다. 피벗 선택 과정은 다음과 같다.

1. $t\; >\; 1$인 경우, $j\_\{t-1\}+1$ 열부터 검색하여 0이 아닌 항목이 있는 $A$의 열 인덱스 중 가장 작은 값을 $j\_t$로 선택한다.
2. $a\_\{t,j\_t\}\backslash neq0$이 되도록 한다. 만약 아니라면, $a\_\{k,j\_t\}\; \backslash neq\; 0$인 $k$를 찾아 행 $t$와 $k$를 교환한다.
3. 선택된 피벗은 위치 $(t,\; j\_t)$에 놓인다.

3.2. 피벗 개선

유일 인수 분해 정역인 환 $R$ 위의 행렬의 스미스 표준형은 두 행 또는 두 열을 교환하거나, 한 행 또는 열에 다른 행 또는 열의 배수를 더하는 연산을 통해 계산할 수 있다.

$R$ 위의 $2\backslash times\; 2$ 행렬
:$$
\begin{pmatrix}
a & b \\
c & e
\end{pmatrix}

을 생각하자. $R$은 베주 정역이므로, $a$와 $b$의 최대공약수 $d$에 대해 $d=ua+vb$인 $u,v\backslash in\; R$가 존재한다. $a=da\text{'}$, $b=db\text{'}$라고 하면, $ua\text{'}+vb\text{'}=1$이다. 따라서
:$$
\begin{pmatrix}
u & -b' \\
v & a'
\end{pmatrix}

은 가역 행렬이며, 다음이 성립한다.
:$$
\begin{pmatrix}
a & b \\
c & e
\end{pmatrix}
\begin{pmatrix}
u & -b' \\
v & a'
\end{pmatrix}
=
\begin{pmatrix}
d & 0 \\
uc+vd & -b'c+a'd
\end{pmatrix}

마찬가지로, 왼쪽에 가역 행렬을 곱하여 첫 행 첫 열 성분이 $a$와 $c$의 최대공약수이며 둘째 행 첫 열 성분이 0이 되도록 만들 수 있다.

일반적인 $m\backslash times\; n$ 행렬 $A$에서, $A\backslash ne\; 0$일 때, 행과 열 교환을 통해 $A\_\{11\}\backslash ne\; 0$이라고 가정할 수 있다. 만약 모든 $i,j=2,\backslash dots,n$에 대해 $A\_\{11\}\backslash mid\; A\_\{ij\}$라면, 각 열에 첫 열의 배수를 더하고 각 행에 첫 행의 배수를 더하여, 첫 행과 첫 열의 $A\_\{11\}$을 제외한 모든 성분을 0으로 만들 수 있다.

만약 $A\_\{11\}\backslash nmid\; A\_\{ij\}$인 $i,j=2,\backslash dots,n$이 존재한다면, $A\_\{11\}\backslash nmid\; A\_\{12\}$이거나 $A\_\{11\}\backslash nmid\; A\_\{21\}$라고 가정할 수 있다. 예를 들어 $A\_\{11\}\backslash nmid\; A\_\{12\}$라면,
:$$
\begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{pmatrix}
Q'=
\begin{pmatrix}
A'_{11} & 0 \\
A'_{21} & A'_{22}
\end{pmatrix}

:$A\text{'}\_\{11\}=\backslash gcd\backslash \{A\_\{11\},A\_\{12\}\backslash \}$
인 가역 행렬 $Q\text{'}$이 존재한다. 여기서

이 과정을 반복하면 결국 첫 행 첫 열의 성분이 모든 다른 성분을 나누는 행렬을 얻고, 다음과 같은 형태가 된다.
:$$
\begin{pmatrix}
d_1 & 0 \\
0 & A'
\end{pmatrix}

:$d\_1\backslash mid\; A\text{'}\_\{ij\}\backslash qquad(\backslash forall\; i,j)$

$A\text{'}$에 대해 같은 과정을 반복하면,
:$$
\begin{pmatrix}
d_1 & 0 \\
0 & d_2 \\
&& A
\end{pmatrix}

:$d\_1\backslash mid\; d\_2\backslash mid\; A$_{ij}\qquad(\forall i,j)
를 얻는다. 여기서 $d\_1\backslash mid\; d\_2$인 이유는 $d\_2$가 $A\text{'}$의 성분의 선형 결합이기 때문이다.

위 과정을 반복하면 결국 스미스 표준형을 얻는다.

$S\; A\; T$가 대각선이 되도록 가역 정사각 행렬 $S$와 $T$를 찾는 것이 알고리즘의 핵심이다. $A$를 $R^n$에서 $R^m$으로의 맵으로 생각할 때, 동형 사상 $S:R^m\; \backslash to\; R^m$ 및 $T:R^n\; \backslash to\; R^n$을 찾아 $S\; \backslash cdot\; A\; \backslash cdot\; T$가 대각 행렬의 형태를 갖도록 한다.

행렬 $S$와 $T$는 항등 행렬로 시작하여, $A$에 행 연산이 수행될 때마다 $S$를, 열 연산이 수행될 때마다 $T$를 수정한다. 이는 불변 $A\text{'}=S\text{'}\backslash cdot\; A\backslash cdot\; T\text{'}$를 유지하며, 여기서 $A\text{'},S\text{'},T\text{'}$는 현재 값을, $A$는 원래 행렬을 나타낸다.

$a\; \backslash in\; R\backslash setminus\; \backslash \{0\backslash \}$에 대해, $\backslash delta(a)$는 $a$의 소인수 개수를 나타낸다. 행렬을 스미스 정규형으로 만들기 위해 다음 단계를 반복한다.

$a\_\{t,j\_t\}\; \backslash nmid\; a\_\{k,j\_t\}$인 항목이 존재하면, $\backslash beta\; =\backslash gcd\backslash left(a\_\{t,j\_t\},\; a\_\{k,j\_t\}\backslash right)$로 놓고, 베주 속성에 의해 R에 속하는 σ, τ가 존재하여 다음을 만족한다.

:$$
a_{t,j_t} \cdot \sigma + a_{k,j_t} \cdot \tau=\beta.


가역 행렬 L의 왼쪽 곱셈으로, 행렬 곱의 행 t는 σ 곱하기 원래 행 t와 τ 곱하기 원래 행 k의 합이 된다. $\backslash alpha=a\_\{t,j\_t\}/\backslash beta$ 및 $\backslash gamma=a\_\{k,j\_t\}/\backslash beta$에 대해,

:$L\_0=$
\begin{pmatrix}
\sigma & \tau \\
-\gamma & \alpha \\
\end{pmatrix}


는 가역이며, 역행렬은 다음과 같다.

:$$
\begin{pmatrix}
\alpha & -\tau \\
\gamma & \sigma \\
\end{pmatrix}
.

L은 항등 행렬의 행과 열 t와 k에 $L\_0$을 삽입하여 얻는다. L을 왼쪽에서 곱하면 (t,j_t) 위치에 β, (k,j_t) 위치에 0을 갖는다. 이므로, 이 단계를 반복하면 종료된다.

3.3. 원소 제거

유일 인수 분해 정역 $R$ 위의 행렬의 스미스 표준형은 행 교환, 열 교환, 한 행에 다른 행의 배수를 더하는 연산, 한 열에 다른 열의 배수를 더하는 연산을 통해 구할 수 있다. 이 과정에서 0이 아닌 원소는 유일한 인수 분해를 가지며, 각 원소 $r$에 대해 $l(r)$은 $r$의 소인수 개수를 나타낸다.

$R$ 위의 $2\; \backslash times\; 2$ 행렬
:$$
\begin{pmatrix}
a & b \\
c & e
\end{pmatrix}

을 생각하자. 베주 정역의 성질에 의해, $a$와 $b$의 최대공약수 $d$에 대해 $d\; =\; ua\; +\; vb$를 만족하는 $u,\; v\; \backslash in\; R$이 존재한다. 이를 이용해 가역 행렬을 구성하고, 원래 행렬에 곱하여 첫 행의 두 번째 원소를 0으로 만들 수 있다. 마찬가지로 왼쪽에 가역 행렬을 곱하여 첫 열의 두 번째 원소를 0으로 만들 수 있다.

일반적인 $m\; \backslash times\; n$ 행렬 $A$에 대해서도, 0이 아닌 경우 행과 열 교환을 통해 $A\_\{11\}\; \backslash neq\; 0$이라 가정할 수 있다. 만약 $A\_\{11\}$이 모든 $A\_\{ij\}$를 나누면, 첫 행과 열을 제외한 모든 원소를 0으로 만들 수 있다. 그렇지 않은 경우, $A\_\{11\}$이 $A\_\{12\}$ 또는 $A\_\{21\}$을 나누지 않도록 만들 수 있다.

$A\_\{11\}\; \backslash nmid\; A\_\{12\}$인 경우, 가역 행렬을 곱하여 $A\text{'}\_\{11\}\; =\; \backslash gcd\backslash \{A\_\{11\},\; A\_\{12\}\backslash \}$가 되도록 하고, 을 만족시킨다. 이 과정을 반복하면 첫 행 첫 열의 원소가 모든 다른 원소를 나누는 행렬을 얻게 된다.

최종적으로, $A$는 다음과 같은 형태의 행렬과 동치가 된다.
:$$
\begin{pmatrix}
d_1 & 0 \\
0 & A'
\end{pmatrix}

여기서 $d\_1$은 $A\text{'}$의 모든 원소를 나눈다. $A\text{'}$에 대해 같은 과정을 반복하고, 이를 계속하면 결국 스미스 표준형을 얻는다.

3.4. 재귀적 적용

행렬의 스미스 표준형은 두 행 또는 두 열을 교환하거나, 한 행 또는 열에 다른 행 또는 열의 배수를 더하는 연산을 통해 계산할 수 있다. 유일 인수 분해 정역 $R$에서 0이 아닌 모든 원소는 유일한 인수 분해를 갖는다. $r\backslash in\; R\backslash setminus\backslash \{0\backslash \}$에 대해, $l(r)\backslash in\backslash mathbb\; N$을 $r$의 소인수의 중복집합의 크기로 정의한다.

먼저 $R$ 위의 $2\backslash times\; 2$ 행렬을 생각한다.
:$$
\begin{pmatrix}
a & b \\
c & e
\end{pmatrix}

$R$가 베주 정역이므로, $a$와 $b$의 최대공약수 $d$에 대해 $d=ua+vb$를 만족하는 $u,v\backslash in\; R$가 존재한다. $a=da\text{'}$, $b=db\text{'}$라고 하면, $ua\text{'}+vb\text{'}=1$이 성립한다. 따라서 다음 행렬은 가역 행렬이다.
:$$
\begin{pmatrix}
u & -b' \\
v & a'
\end{pmatrix}

이 행렬을 이용하여 다음을 얻을 수 있다.
:$$
\begin{pmatrix}
a & b \\
c & e
\end{pmatrix}
\begin{pmatrix}
u & -b' \\
v & a'
\end{pmatrix}
=
\begin{pmatrix}
d & 0 \\
uc+vd & -b'c+a'd
\end{pmatrix}

마찬가지로, 왼쪽에 가역 행렬을 곱하여 첫 행 첫 열 성분이 $a$와 $c$의 최대공약수가 되고, 둘째 행 첫 열 성분이 0이 되도록 할 수 있다.

이제 일반적인 $m\backslash times\; n$ 행렬 $A$를 고려한다. $A=0$이면 $A$는 이미 스미스 표준형이다. $A\backslash ne\; 0$인 경우, 행과 열 교환을 통해 $A\_\{11\}\backslash ne\; 0$이라고 가정할 수 있다. (보통 $l(A\_\{11\})$가 가장 작도록 교환한다.)

만약 모든 $i,j=2,\backslash dots,n$에 대해 $A\_\{11\}\backslash mid\; A\_\{ij\}$라면, 각 열에 첫 열의 배수를 더하고 각 행에 첫 행의 배수를 더하여 첫 행과 첫 열에서 $A\_\{11\}$을 제외한 모든 성분을 0으로 만들 수 있다. 그렇지 않다면, $A\_\{11\}\backslash nmid\; A\_\{12\}$이거나 $A\_\{11\}\backslash nmid\; A\_\{21\}$이라고 가정할 수 있다.

$A\_\{11\}\backslash nmid\; A\_\{12\}$라고 가정하면, 다음을 만족하는 가역 행렬 $Q\text{'}$이 존재한다.
:$$
\begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{pmatrix}
Q'=
\begin{pmatrix}
A'_{11} & 0 \\
A'_{21} & A'_{22}
\end{pmatrix}

여기서 $A\text{'}\_\{11\}=\backslash gcd\backslash \{A\_\{11\},A\_\{12\}\backslash \}$이다.

따라서 다음 행렬 $Q$는 가역 행렬이다.
:$Q=$
\begin{pmatrix}
Q' & 0 \\
0 & 1_{(n-2)\times(n-2)}
\end{pmatrix}

행렬 $AQ$의 첫 행 첫 열 성분은 $A\text{'}\_\{11\}$이고,

최종적으로 $A$는 다음과 같은 형태의 행렬과 동치가 된다.
:$$
\begin{pmatrix}
d_1 & 0 \\
0 & A'
\end{pmatrix}

여기서 $d\_1\backslash mid\; A\text{'}\_\{ij\}\backslash qquad(\backslash forall\; i,j)$이다.

$A\text{'}$에 대해 같은 과정을 반복하면 다음과 같은 형태의 행렬을 얻는다.
:$$
\begin{pmatrix}
d_1 & 0 \\
0 & d_2 \\
&& A
\end{pmatrix}

여기서 $d\_1\backslash mid\; d\_2\backslash mid\; A$_{ij}\qquad(\forall i,j)이다. $d\_1\backslash mid\; d\_2$인 이유는 $d\_2$가 $A\text{'}$의 성분의 선형 결합이기 때문이다.

이 과정을 반복하면 스미스 표준형을 얻을 수 있다.

곱 $S\; A\; T$가 대각선이 되도록 가역 정사각 행렬 $S$와 $T$를 찾는 것이 중요하다. $A$를 $R^n$에서 $R^m$으로의 맵으로 생각할 때, 동형 사상 $S:R^m\; \backslash to\; R^m$ 및 $T:R^n\; \backslash to\; R^n$을 찾아 $S\; \backslash cdot\; A\; \backslash cdot\; T$가 대각 행렬 형태를 갖도록 한다.

$S$와 $T$는 항등 행렬로 시작하여, $A$에 행 연산이 수행될 때마다 $S$를 수정하고, 열 연산이 수행될 때마다 $T$를 수정한다. 이는 불변 관계식 $A\text{'}=S\text{'}\backslash cdot\; A\backslash cdot\; T\text{'}$를 유지하며, 여기서 $A\text{'},S\text{'},T\text{'}$는 현재 값을, $A$는 원래 행렬을 나타낸다.

$a\; \backslash in\; R\backslash setminus\; \backslash \{0\backslash \}$에 대해, $\backslash delta(a)$는 $a$의 소인수 개수를 나타낸다. $R$은 베주 정역이므로 최대 공약수 정역이며, 임의의 두 원소의 최대 공약수는 베주의 항등식을 만족한다.

3.5. 최종 단계

행렬의 스미스 표준형은 행 및 열 연산을 통해 얻을 수 있다. 여기서 사용되는 주요 연산은 두 행 또는 열 교환, 한 행 또는 열에 다른 행 또는 열의 배수를 더하는 연산이다. $R$이 유일 인수 분해 정역이므로, 모든 0이 아닌 원소는 유일한 인수 분해를 가지며, 이를 통해 각 원소의 소인수 개수를 정의할 수 있다.

먼저, $R$ 위의 $2\; \backslash times\; 2$ 행렬을 고려한다. 베주 정역의 성질에 따라, 행렬의 원소들의 최대공약수를 이용하여 가역 행렬을 구성하고, 이를 원래 행렬에 곱하여 특정 위치의 성분을 0으로 만들 수 있다. 이 과정을 통해 행렬의 첫 행 첫 열 성분이 다른 성분들의 최대공약수가 되도록 변형할 수 있다.

일반적인 $m\; \backslash times\; n$ 행렬의 경우, 행렬이 영행렬이 아니라면, 행과 열 교환을 통해 첫 행 첫 열 성분이 0이 아니도록 설정한다. 만약 이 성분이 다른 모든 성분을 나눌 수 있다면, 행렬의 나머지 부분을 0으로 만들 수 있다. 그렇지 않은 경우, 추가적인 행 및 열 연산을 통해 첫 행 첫 열 성분의 소인수 개수를 줄여가며, 결국에는 이 성분이 모든 다른 성분을 나누도록 만들 수 있다.

이 과정을 반복하여 행렬을 대각 행렬 형태로 변환하며, 각 대각 성분은 다음 대각 성분을 나누는 조건을 만족시킨다. 이 과정에서 얻어지는 최종 형태가 스미스 표준형이다.

가역 행렬 $S$와 $T$를 찾아 곱 $SAT$가 대각 행렬이 되도록 하는 것은 알고리즘에서 가장 어려운 부분이다. 행 연산을 할 때마다 $S$를, 열 연산을 할 때마다 $T$를 수정하여 불변식을 유지한다. 이 과정을 통해 최종적으로 스미스 표준형을 얻게 된다.

4. 예제

유리수 계수 다항식환 $\backslash mathbb\; Q[x]$ 위의 행렬
:$$
\begin{pmatrix}
x+3 & 1 & 1 \\
2 & x+2 & 1 \\
-6 & -3 & x-2
\end{pmatrix}

의 스미스 표준형은 다음과 같이 구할 수 있다.
:$$
\begin{align}
\begin{pmatrix}
x+3 & 1 & 1 \\
2 & x+2 & 1 \\
-6 & -3 & x-2
\end{pmatrix}
&\sim
\begin{pmatrix}
1 & 1 & x+3 \\
1 & x+2 & 2 \\
x-2 & -3 & -6
\end{pmatrix}
\sim
\begin{pmatrix}
1 & 1 & x+3 \\
0 & x+1 & -x-1 \\
0 & -x-1 & -x^2-x
\end{pmatrix}
\sim
\begin{pmatrix}
1 & 0 & 0 \\
0 & x+1 & -x-1 \\
0 & -x-1 & -x^2-x
\end{pmatrix}
\\&\sim
\begin{pmatrix}
1 & 0 & 0 \\
0 & x+1 & -x-1 \\
0 & 0 & -(x+1)^2
\end{pmatrix}
\sim
\begin{pmatrix}
1 & 0 & 0 \\
0 & x+1 & 0 \\
0 & 0 & -(x+1)^2
\end{pmatrix}
\\&\sim
\begin{pmatrix}
1 & 0 & 0 \\
0 & x+1 & 0 \\
0 & 0 & (x+1)^2
\end{pmatrix}
\end{align}


정수 위에서 다음 행렬의 스미스 표준형을 구하면 다음과 같다.

:$$
\begin{pmatrix}
2 & 4 & 4 \\
-6 & 6 & 12 \\
10 & 4 & 16
\end{pmatrix}


다음은 위의 행렬에 알고리즘을 적용하는 중간 단계이다.

:$$
\to
\begin{pmatrix}
2 & 0 & 0 \\
-6 & 18 & 24 \\
10 & -16 & -4
\end{pmatrix}
\to
\begin{pmatrix}
2 & 0 & 0 \\
0 & 18 & 24 \\
0 & -16 & -4
\end{pmatrix}
\to
\begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & 20 \\
0 & -16 & -4
\end{pmatrix}
\to
\begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & 20 \\
0 & 0 & 156
\end{pmatrix}
\to
\begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 156
\end{pmatrix}


따라서 스미스 표준형은

:$$
\begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 156
\end{pmatrix}


이며, 불변 인자는 2, 2, 156이다.

5. 응용

스미스 표준형은 사슬 복합체의 사슬 모듈이 유한 생성 가군일 때 호몰로지를 계산하는 데 유용하다. 예를 들어, 위상수학에서 유한 단순 복합체 또는 CW 복합체의 정수 계수 호몰로지를 계산할 수 있는데, 이는 이러한 복합체의 경계 사상이 정수 행렬이기 때문이다. 또한 주 이상역에 대한 유한 생성 가군의 구조 정리에 나타나는 불변 인수를 결정하는 데에도 사용할 수 있으며, 여기에는 유한 생성 아벨 그룹의 기본 정리도 포함된다.

스미스 표준형은 제어 이론에서 전달 함수 행렬의 전송 및 차단 영점을 계산하는 데에도 사용된다.

5.1. 주 아이디얼 정역 위의 유한 생성 가군의 구조

스미스 표준형을 통해 주 아이디얼 정역 위의 유한 생성 가군의 불변 인자 분해를 유도할 수 있다.

5.2. 호몰로지 계산

스미스 표준형은 사슬 복합체의 사슬 모듈이 유한 생성 가군일 때 호몰로지를 계산하는 데 유용하다. 예를 들어, 위상수학에서 유한 단순 복합체 또는 CW 복합체의 정수 계수 호몰로지를 계산하는 데 사용할 수 있는데, 이러한 복합체의 경계 사상이 정수 행렬이기 때문이다. 또한 주 이상역에 대한 유한 생성 가군의 구조 정리에 나타나는 불변 인수를 결정하는 데에도 사용할 수 있으며, 여기에는 유한 생성 아벨 그룹의 기본 정리도 포함된다.

5.3. 제어 이론

제어 이론에서 전달 함수 행렬의 전송 및 차단 영점을 계산하는 데 사용된다.

5.4. 닮음 판별

스미스 표준형은 공통 체 $K$ 상의 원소를 갖는 행렬들이 닮음인지 여부를 결정하는 데 사용될 수 있다. 구체적으로 두 행렬 A와 B가 닮음이려면 필요충분 조건으로 특성 행렬 $xI-A$와 $xI-B$가 동일한 스미스 표준형을 가져야 한다. (여기서 PID는 $K[x]$를 의미한다.)

예를 들어, 다음과 같은 행렬들을 생각해 보자.

:$\backslash begin\{align\}$
A & {} =\begin{bmatrix}
1 & 2 \\
0 & 1
\end{bmatrix}, & & \mbox{SNF}(xI-A) =\begin{bmatrix}
1 & 0 \\
0 & (x-1)^2
\end{bmatrix} \\
B & {} =\begin{bmatrix}
3 & -4 \\
1 & -1
\end{bmatrix}, & & \mbox{SNF}(xI-B) =\begin{bmatrix}
1 & 0 \\
0 & (x-1)^2
\end{bmatrix} \\
C & {} =\begin{bmatrix}
1 & 0 \\
1 & 2
\end{bmatrix}, & & \mbox{SNF}(xI-C) =\begin{bmatrix}
1 & 0 \\
0 & (x-1)(x-2)
\end{bmatrix}.
\end{align}

A와 B는 특성 행렬의 스미스 표준형이 일치하기 때문에 서로 닮음이지만, C는 특성 행렬의 스미스 표준형이 이들과 다르므로 A나 B와 닮음이 아니다.

6. 역사

헨리 존 스티븐 스미스의 이름을 땄다.