행렬의 스미스 노멀 폼 📂위상데이터분석

행렬의 스미스 노멀 폼

Smith Normal Form of Matrix

정의 1 2

PID, 즉 주아이디얼정역 $R$ 이 주어져 있다고 하자. 행렬 $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 \in R^{m \times n}$ 을 $A$ 의 스미스 노멀 폼Smith Normal Form이라 한다. $$ 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여야한다.

예시

역행렬이 나와서 복잡해보이지만 실상은 가우스 소거법을 통해서 구할 수 있다. 공식적으로 쓰는 표현은 절대 아니지만, 예시를 읽기 쉽도록 행렬 우측에 어떤 연산을 취했는지 표기하도록 하겠다. $r-$ 는 행row, $c-$ 는 열column이고 $-x$ 는 교환exchange, $-e$ 는 소거elimination, $-+$ 는 해당 계수를 곱해서 더하는 연산이다.

물론 가우스 소거법을 통해 계산하는 것은 계산 측면에서 별로 현명하지 않을지도 모른다. 그냥 손계산 할 때는 이렇게도 구할 수 있구나 하는 정도로만 참고하자.

정수환 $\mathbb{Z}$

$$ \begin{align*} \begin{bmatrix} 2 & 3 & 1 \\ 4 &-1 &-1 \end{bmatrix} \sim & & \begin{bmatrix} 1 & 3 & 2 \\ -1 &-1 & 4 \end{bmatrix} & \qquad cx(1,3) \\ \sim & & \begin{bmatrix} 1 & 0 & 0 \\ -1 & 2 & 6 \end{bmatrix} & \qquad ce(1 \to 2,3) \\ \sim & & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 6 \end{bmatrix} & \qquad re(1 \to 2) \\ \sim & & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \end{bmatrix} & \qquad ce(2 \to 3) \end{align*} $$

여기서 $1 \mid 2$ 임에 주의하라.

다항식환 $\mathbb{Q} [x]$

$$ \begin{align*} \begin{bmatrix} x & 2 & 0 \\ 0 & 1 & 2x \\ -1 & 0 & x+1 \end{bmatrix} \sim & \begin{bmatrix} x & 2 & x \\ 0 & 1 & 2x \\ -1 & 0 & x \end{bmatrix} & \qquad c+(1 \to 3, 1) \\ \sim & \begin{bmatrix} x+1 & 2 & 0 \\ 2 & 1 & 0 \\ -1 & 0 & x \end{bmatrix} & \qquad re(3 \to 1, 2) \\ \sim & \begin{bmatrix} 2 & 1 & 0 \\ x+1 & 2 & 0 \\ -1 & 0 & x \end{bmatrix} & \qquad rx(1,2) \\ \sim & \begin{bmatrix} 1 & 2 & 0 \\ 2 & x+1 & 0 \\ 0 & -1 & x \end{bmatrix} & \qquad cx(1,2) \\ \sim & \begin{bmatrix} 1 & 2 & 0 \\ 0 & x-3 & 0 \\ 0 & -1 & x \end{bmatrix} & \qquad re(1 \to 2) \\ \sim & \begin{bmatrix} 1 & 0 & 0 \\ 0 & x-3 & 0 \\ 0 & -1 & x \end{bmatrix} & \qquad ce(1 \to 2) \\ \sim & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & -x \\ 0 & x-3 & 0 \end{bmatrix} & \qquad rx(2,3) \\ \sim & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & x-3 & x(x-3) \end{bmatrix} & \qquad c+(2 \to 3, x) \\ \sim & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & x(x-3) \end{bmatrix} & \qquad r+(2 \to 3, -(x-3)) \end{align*} $$

설명

주의해야할 것은 주어진 주아이디얼정역 $R$ 은 라는 보장이 없기 때문에 일반적으로 나눗셈이 허용되지 않고, PID베주 정역임을 이용해서 소거를 해야한다는 것이다.

정리

존재성과 유일성

$R$ 이 주아이디얼정역일 때, 모든 행렬 $A \in R^{m \times n}$ 에 대해 스미스 노멀 폼이 유일하게 존재한다. 이 때 유일성은 $d_{k}$ 들의 단원배를 무시한다.

증명

구체적으로 스미스 노멀 폼을 구하는 알고리즘을 통해 보인다.

댓글