📂위상데이터분석

스미스 노멀 폼의 존재성 증명

알고리즘

$R$ 이 주아이디얼정역일 때, 모든 행렬 $A \in R^{m \times n}$ 에 대해 스미스 노멀 폼이 유일하게 존재한다. 다시 말해, 행렬 $A \in R^{m \times n}$ 에 대해 다음을 만족시키는 $d_{1} , \cdots , d_{r} \in R$ 과 가역행렬 $P \in R^{m \times m}$, $Q \in R^{n \times n}$ 이 존재한다. $$PAQ = \begin{bmatrix} d_{1} & 0 & 0 & 0 & \cdots & 0 \\ 0 & \ddots & 0 & 0 & \cdots & 0 \\ 0 & 0 & d_{r} & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 \end{bmatrix} \in R^{m \times n}$$ 여기서 $d_{1} , \cdots , d_{r}$ 은 $R$ 에서 $0$ 이 아니어야 하며, $d_{1} \mid \cdots \mid d_{r}$ 이어야한다. 다시 말해 $d_{k} \ne 0$ 는 $d_{k+1}$ 의 인자^divisor여야한다. 이 때 유일성은 $d_{k}$ 들의 단원배를 무시한다.

증명 ^{1 2}

전략: 행,열 교환과 가우스 소거법을 사용하는 알고리즘으로써, 구체적인 스미스 노멀 폼을 직접 찾아서 그 존재성을 보인다.

모든 주아이디얼 정역은 유일인수분해정역이다.

행렬 $A$ 는 PID 상의 행렬이므로 UFD 상의 행렬이기도 하다. 따라서 단원^unity이나 $0$ 이 아닌 모든 성분 $A_{ij}$ 는 유일한 인수분해를 가지며, 그 중 가장 적은 갯수의 인수를 가지는 성분의 절대값을 $\alpha > 0$ 이라 나타내고 미니멀 엔트리^{minimal Entry}라 부른다.

참고로 Munkeres 교재에서는 $\mathbb{Z}^{m \times n}$ 이라서 그냥 가장 작은 성분을 고르는데, 정수환 $\mathbb{Z}$ 가 아닌 일반적인 주아이디얼정역은 유클리드 정역이라는 보장조차 없으므로 원소만 보고 ‘가장 작다’를 따지기 곤란하다. 일반적인 PID에서 깔끔하게 미니멀 엔트리를 정하려면 소인수분해를 생각하는 게 타당하다. 다만 이 포스트에서는 편의상 ‘작다’거나 $a < b$ 같은 표현이 나오는데, 이 역시 원소의 크기가 아니라 인수의 수를 비교하는 것이라고 보면 된다.

주어진 행렬은 가우스 소거법에 따라 계속 바뀌므로 $\alpha$ 역시 맥락에 따라 계속해서 바뀌는 것에 주의하라.

참고로 이 알고리즘은 주어진 $A$ 에 대해서 반드시 스미스 노멀 폼을 유도할 수 있음을 수학적으로 보이기 편한 알고리즘일 뿐 딱히 효율적이지도 않고 $P, Q$ 도 알 수 없다.

---

Step 1.

$A$ 가 영행렬이면 그 자체로 이미 스미스 노멀 폼이므로 Step 4로 넘어간다. $A$ 가 영행렬이 아니면 다음을 수행한다.

생각하기 쉽게 우선 행과 열을 교환해서 $\alpha$ 를 좌상단 $(1,1)$ 으로 끌어올리자. 이제 우리는 주어진 행렬 대부분을 신경쓰지 않고 첫 행, 첫 열 근처만 볼 것이다. $$A \sim \begin{bmatrix} \alpha & A_{12} & \cdots & \\ A_{21} & A_{22} & \cdots & \\ \vdots & \vdots & \ddots & \end{bmatrix}$$

---

Step 2. $k= 1, \cdots , r$

(당연히 계산 도중에는 $r$ 을 알 수 없다. 프로그램이 끝나면 자연스럽게 $r$ 이 결정된다.)

• 모든 $i, j$ 에 대해 $\alpha \mid A_{ij}$ 라면 $d_{k} \gets \alpha$ 을 대입한다. $\alpha \mid A_{ij}$ 이므로 $\alpha$ 를 제외한 $A$ 의 첫번째 행과 열의 모든 성분이 $0$ 이 될 때까지 가우스 소거법을 반복할 수 있다. 반복이 끝나면 $1$행과 $1$열을 삭제하고 Step 1로 돌아간다. 이제 행렬 $A$ 의 크기는 $(m - k) \times (n - k)$ 다.
• 어떤 $i, j$ 에 대해 $\alpha \nmid A_{ij}$ 라면 Step 3로 넘어간다.

---

Step 3.

이제부터의 논의는 행이든 열이든 한 방향으로 되면 다른 한 쪽에도 적용할 수 있으니, 앞으로 일반성을 잃지 않고 $\alpha \ne 0$ 와 $A_{12}$ 만 다루도록 하자. 기본적으로 Step 2에서 적어도 하나의 $i, j$ 에 대해서는 $\alpha \nmid A_{ij}$ 을 보장할 수 있고, $(1,2)$ 에 그 $A_{ij}$ 이 오도록해서 아래의 Case 1을 시행하는 것을 목표로 한다.

주아이디얼 정역은 베주 정역이다: PID는 베주 정역이므로 확장된 유클리드 정리가 성립한다. 다시 말해, 모든 $a, b \in D$ 에 대해 다음을 만족시키는 $m,n \in D$ 가 존재한다. $$m a + n b = \gcd \left( a, b \right)$$

• Case 1. $\alpha \nmid A_{12}$ 인 경우
  $\alpha$ 는 미니멀 엔트리고 $\alpha \nmid A_{12}$ 이므로 $\gcd \left( \alpha, A_{12} \right) < \alpha$ 이다. 확장된 유클리드 정리에 따라 $$m \alpha + n A_{12}$$ 를 $\alpha$ 보다 작게 만드는 $m,n \in D$ 가 존재한다. 가우스 소거법에 따라 $1$열에 $m$ 을 곱한 열과 $2$ 열에 $n$ 을 곱한 열을 더해 $2$열에 대입한다. 이 새로운 열의 첫번째 성분인 $A_{12}' = \gcd \left( \alpha , A_{12} \right)$ 는 원래의 $\alpha$ 보다 작을 뿐만 아니라, 계산 자체에서 $\alpha$ 의 약수이므로 기존보다 더 작고 새로운 미니멀 엔트리의 후보다. 이에 따라 $1$열과 $2$열을 교환하고 Step 1로 돌아간다.(계산 중 우연한 기회로 더 작은 미니멀 엔트리가 존재할 수도 있다.)
• Case 2. $\alpha \mid A_{12}$ 인 경우
  $k \alpha + A_{12} = 0$ 를 만족 시키는 어떤 $k \in \mathbb{Z}$ 가 존재하므로, $1$ 열에 $k$ 를 곱해서 $2$열에서 뺀다. 그러면 이 새로운 열의 첫번째 성분인 $A_{12} '$ 는 $0$ 이다. Step 3를 반복한다.
• Case 3. $A_{12} = 0$ 인 경우
  $A_{12} \ne 0$ 일 때까지 열교환을 반복한다. 만약 $j \ne 1$ 에 대해 모든 $A_{1j}$ 가 $0$ 일 경우 $A_{21}$ 에 대해서 Step 3를 시행한다.
  • $\alpha \nmid A_{21}$ 인 경우 $A_{21}' < \alpha$ 다. 미니멀 엔트리를 갱신한다.
  • $\alpha \mid A_{21}$ 이면 $A_{21} '$ 을 $0$ 으로 만든다.
  • $A_{21} = 0$ 이면 지금 행렬이 다음과 같이 생겼다는 의미다. $$A \sim \begin{bmatrix} \alpha & 0 & \cdots & \\ 0 & A_{22} & \cdots & \\ \vdots & \vdots & \ddots & \end{bmatrix}$$ $A_{21} = 0$ 이므로, $2$행을 $1$행에 더하면 $\alpha$ 는 그대로 있고 $$A \sim \begin{bmatrix} \alpha & A_{22} & \cdots & \\ 0 & A_{22} & \cdots & \\ \vdots & \vdots & \ddots & \end{bmatrix}$$ 과 같은 꼴이 된다. $A_{i1} \ne 0$ 을 만족하는 $i$번째 행과 $2$행을 교환하고 다시 Step 3를 반복한다. 만약 $\alpha$ 를 제외한 $1$행과 $1$열의 모든 성분이 $0$ 이라도 $\alpha \nmid A_{ij}$ 를 만족하는 $i,j \ge 2$ 가 여전히 적어도 한 쌍 존재해야하므로 Case 3를 반복하면 언젠간 $\alpha \nmid A_{12}$ 이어야한다.

Case 1에 따라 $A_{11}$ 의 값을 계속해서 줄여나갈 수 있고, Case 2에 따라 첫행과 첫열에서 $\alpha$ 외의 성분을 $0$ 으로 만들 수 있고, Case 3에 따라 반드시 $\alpha \nmid A_{ij}$ 인 $A_{ij}$ 가 $(1,2)$ 에 위치하게 된다.

---

Step 4. $d_{1} \mid \cdots \mid d_{r}$

Step 4로 넘어오는 방법은 Step 1에서 남은 $A$ 가 영행렬인 경우 뿐이다.

우리는 Step 2에서 $d_{k} \gets \alpha$ 와 같이 $d_{k}$ 들을 기록해왔다. 미니멀 엔트리였던 $\alpha$ 가 모든 $A_{ij}$ 를 나눌 수 있었다는 것은 이후 남겨진 행렬에서 확장된 유클리드 정리로 만들어지는 어떤 원소든 이 $\alpha$ 로 나누어진다는 것이 보장된다는 것이다. 따라서 $d_{1} \mid \cdots \mid d_{r}$ 이고, 다음의 스미스 노멀 폼을 얻는다. $$\begin{bmatrix} d_{1} & 0 & 0 & 0 & \cdots & 0 \\ 0 & \ddots & 0 & 0 & \cdots & 0 \\ 0 & 0 & d_{r} & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 \end{bmatrix} \in R^{m \times n}$$

■