스미스 보통형

수학에서 스미스 정규 형태(Smith normal form, 때로는 약칭 SNF^[1])는 주 이상 도메인(PID)에 입력된 매트릭스(필수 제곱은 아님)에 대해 정의할 수 있는 정상 형태다. 스미스 정상 형태의 매트릭스는 대각선으로, 변환 불가능한 사각 매트릭스에 의해 왼쪽과 오른쪽에 곱하여 원래의 매트릭스에서 얻을 수 있다. 특히 정수는 PID이기 때문에 항상 스미스 정규 형태의 정수 행렬을 계산할 수 있다. 스미스 정상 형태는 PID를 통해 미세하게 생성된 모듈들과 작업할 때, 특히 자유 모듈의 인용구 구조를 추론할 때 매우 유용하다. 영국의 수학자 헨리 존 스티븐 스미스(Henry John Stephen Smith)의 이름을 따서 지은 것이다.

정의

A를 주 이상적인 영역 R 위에 0이 아닌 m×n 행렬이 되게 하라. 제품 $m\times m$ SA T가 있는 $m\times m$ m $m\times m$ × $m\times m$ {\ $displaystyle m\times m}$ 및 $n\times n$ $n\times n$ {\ $displaystyle$ n\ $times$ n $}$ -matrix $n\times n$ S, T가 있다.

${\displaystyle{\begin{pmatrix}\alpha _{1}&, 0&, 0&,&\cdots &,&0\\0&, \alpha _{2}&, 0&,&\cdots &,&0\\0&, 0&, \ddots &,&&&0\\\vdots &,&&\alpha _{r}&,&&\vdots \\&,&&&0&,&\\&,&&&&\ddots &, \\0&,&&\cdots &,&&0\en.d{pmatrix}}.}$

그리고 대각선 원소 $α$ $\alpha _{i}$ ${\$ 는 $\alpha _{i}\mid \alpha _{i+1}\;\forall \;1\leq i<r$ i $\alpha _{i}\mid \alpha _{i+1}\;\forall \;1\leq i<r$ $\alpha _{i}\mid \alpha _{i+1}\;\forall \;1\leq i<r$ + $\alpha _{i}\mid \alpha _{i+1}\;\forall \;1\leq i<r$ i < $\alpha _{i}\mid \alpha _{i+1}\;\forall \;1\leq i<r$ ${\$ displaystyle $\pair _{i}\mid \i+1}\;\all \1\leq ir}$ 을 $\alpha _{i}$ 만족한다 $\alpha _{i}\mid \alpha _{i+1}\;\forall \;1\leq i<r$ 이것은 매트릭스 A의 스미스 정상 형태다. $\alpha _{i}$ $\alpha _{i}$ ${\$ 원소는 단위별로 최대 곱셈까지 고유하며 $\alpha _{i}$ , 초등분자, 불변인자 또는 불변인자로 불린다. 다음과 같이 계산될 수 있다(단위에 의한 곱셈까지).

\alpha _{i}={\frac {d_{i}(A)}{d_{i-1}(A)}},

여기서 d $d_{i}(A)$ ( $d_{i}(A)$ ) ${\$ $displaystyle$ $d_{i}(A)}($ 일명 i-th 결정요인 divisor)는 매트릭스 A 및 $d_{0}(A):=1$ $)$ 의 모든 $i\times i$ $i\times i$ $i\times i$ ${\$ $displaysty i\$ $time$ $i}$ 미성년자 $i\times i$ 중 가장 큰 $공통점$ 이다 $d_{0}(A):=1$

알고리즘.

첫 번째 목표는 제품 $SA$ $T$ $SAT$ 이(가) 대각선으로 되도록 $T$ $SAT$ 회전 불가능한 사각 행렬 S $SAT$ 을 $S$ (를) 찾는 것이다. 이것은 알고리즘에서 가장 어려운 부분이다. 일단 대각성이 달성되면 매트릭스를 스미스의 정상적인 형태로 넣는 것이 비교적 쉬워진다. Phrased more abstractly, the goal is to show that, thinking of $A$ as a map from $R^{n}$ (the free $R$ -module of rank $n$ ) to $R^{m}$ (the free $R$ -module of rank $m$ ), 이형성 $S:R^{m}\to R^{m}$ : $S:R^{m}\to R^{m}$ $S:R^{m}\to R^{m}$ → $S:R^{m}\to R^{m}$ $S:R^{m}\to R^{m}$ ${\$ $R^{m}\to R^{m}}$ 및 $S:R^{m}\to R^{m}$ $T:R^{n}\to R^{n}$ : R $T:R^{n}\to R^{n}$ → $T:R^{n}\to R^{n}$ n $T:R^{n}\to R^{n}$ {\ $displaystyle T:$ $S\cdot A\cdot T$ { A \ T {\ $displaystyle S\cdot$ A $\cdot T}$ 이 $T:R^{n}\to R^{n}$ (가) 대각 행렬의 단순한 형태를 갖도록 $S\cdot A\cdot T$ $R^{n$ }\ $to R^{n}}}}}.$ 행렬 $S$ $S$ $T$ T $T$ 은(예: 행 $i$ ${\\)$ 해당 열 연산에 의해 알고리즘의 $A$ $A$ $A$ 에서 행 연산을 수행할 때마다 $S$ $S$ $S$ 을(를) 수정하여 찾을 수 있다 $T$ . $displaystyle i}$ 을 $j$ $($ 를) A {\ $displaystyle$ A $}$ 의 j {\displaystyle $j}$ 열에 추가한 다음 $i$ $A$ $제품$ 불변성을 유지하려면 s $S$ ${\displaystyle$ s}의 $i$ $i$ ${\displaystystyle i}$ 열에서 빼야 하며, 수행된 각 열 작업에 대해 $T$ 로 $T$ T ${\\\displaystystylease t}$ 을 수정해야 한다 $j$ . Since row operations are left-multiplications and column operations are right-multiplications, this preserves the invariant $A'=S'\cdot A\cdot T'$ where $A',S',T'$ denote current values and $A$ denotes the original matrix; eventually 이 불변성의 행렬은 대각선이 된다. $S$ $S$ 및 $S$ $T$ $T$ 이(가) 변위 불가능한 행렬로 $T$ 유지되도록 하는 변환 불가능한 행과 열 연산만 수행된다.

$a\in R\setminus \{0\}$ $a\in R\setminus \{0\}$ $a\in R\setminus \{0\}}$ 의 경우 ${\displaystyle$ $\delta (a)$ 의 주요 요인 $수$ 에 대해 $\delta (a)$ $({\displaystystyle$ $\$ delta (a)를 쓰십시오 $a\in R\setminus \{0\}$ $a$ 이러한 PID도 고유한 요인화 도메인이기 때문에 고유). 특히 $R$ $R$ 도 베즈아웃 도메인이기 $R$ 때문에 gcd 도메인이며 어떤 두 원소의 gcd도 베즈아웃의 정체성을 만족시킨다.

매트릭스를 Smith 일반 양식에 넣으려면 $t$ $t$ 루프를 $t$ 1에서 ' $m$ $m$ 까지 반복적으로 적용할 수 있다 $m$

1단계: 피벗 선택

$j_{t-1}+1$ t {\ $displaystyle j_$ $j_{t-1}+1$ $t}$ 를 선택하여 $j_{t}$ 0이 $j_{t-1}+1$ $A$ 을 $A$ 가진 A $A$ 의 가장 작은 열 인덱스로, $t>1$ > $t>1$ ${\displaystyle j_$ ${t-1$ $}+1$ $}$ 에서 $j_{t-1}+1$ 검색을 시작하십시오 $t>1$

We wish to have $a_{t,j_{t}}\neq 0$ ; if this is the case this step is complete, otherwise there is by assumption some $k$ with $a_{k,j_{t}}\neq 0$ , and we can exchange rows $t$ and $k$ , ther $a_{t,j_{t}}\neq 0$ , t $a_{t,j_{t}}\neq 0$ $a_{t,j_{t}}\neq 0$ $a_{t,j_{t}}\neq 0$ $a_{t,j_{t}}\neq 0$ 0 ${\displaystyle a_{t,j_{t}}\neq$ 0 $}$ 을(를) 얻음 $a_{t,j_{t}}\neq 0$

선택한 피벗이 현재 위치 $(t,j_{t})$ , $(t,j_{t})$ $(t,j_{t})$ ) ${\displaystyle (t,j_{t}})$ 에 있음 $(t,j_{t})$

2단계: 피벗 개선

만약 위치에서(k,jt) 엔트리를 t, jt∤ k, j({\displaystyle a_{t,j_{t}}\nmid a_{k,j_{t}}}, 그때 있게 함 β)gcd(는 t, jt, k, jt){\displaystyle \beta =\gcd \left(a_{t,j_{t}},a_{k,j_{t}}\right)}, 우리가 알고 있는 베주 속성이 존재하 σ, τ에 R과 같은 등번호.t

a_{t,j_{t}\cdot \cdma +a_{k,j_{t}\cdot \tau =\cdot .

적절한 반전성 매트릭스 L을 가진 왼쪽 곱셈에 의해, 매트릭스 제품의 행 t는 원래 행 t와 τ 곱하기 k의 times 곱하기의 합이고, 제품의 행 k는 원래 행의 또 다른 선형 조합이며, 다른 행은 모두 변경되지 않는다는 것을 달성할 수 있다. Explicitly, if σ and τ satisfy the above equation, then for $\alpha =a_{t,j_{t}}/\beta$ and $\gamma =a_{k,j_{t}}/\beta$ (which divisions are possible by the definition of β) one has

\displaystyle \cdma \cdot \cdot +\tau \cdot \cdot =1,}

매트릭스가

L_{0}={\begin{pmatrix}\sigma &\\tau \\\alpha \\end{pmatrix}}}

역방향으로 변환할 수 없음

{\pmatrix}\reason &-\tau \\\nd{pmatrix}.

이제 L은 ID $L_{0}$ 의 $L_{0}$ 행과 열 t와 $k$ 에 L 0 {\displaystyle $L_{$ 0 $}$ 을 $L_{0}$ 장착하여 얻을 수 있다. 구성을 통해 L에 의해 왼쪽 다중화 후 얻은 매트릭스는 위치(t,j_t)에 β 엔트리를 가지고 있다(그리고 우리가 α와 γ를 선택했기 때문에 위치(k_t,j)에도 엔트리가 0인데, 알고리즘에는 필수적이지는 않지만 유용하다. 이 새로운 항목 β는 이전에 있었던 $a_{t,j_{t}}$ $a_{t,j_{t}}$ $a_{t,j_{t}}$ , $a_{t,j_{t}}$ $a_{t,j_{t}}$ {\ $displaystyle a_{t,j_{t}}$ 을 t, 특히 $\delta (\beta )<\delta (a_{t,j_{t}})$ ( $\delta (\beta )<\delta (a_{t,j_{t}})$ , $\delta (\beta )<\delta (a_{t,j_{t}})$ j t $\delta (\beta )<\delta (a_{t,j_{t}})$ ) $\delta (\beta )<\delta (a_{t,j_{t}})$ (t , $\delta (\beta )<\delta (a_{t,j_{t}})$ $\delta (\beta )<\delta (a_{t,j_{t}})$ ) ${\display$ style $\delta$ (\ $beta )<\delta (a_{t,j_{t})}}}}}}}}}}}$ 을 분할하므로 이러한 단계를 반복하면 결국 종료해야 한다 $\delta (\beta )<\delta (a_{t,j_{t}})$ 하나의 행렬은 j열의_t 모든 항목을 나누는 위치(t,j_t)에 입력을 갖는 행렬로 끝난다.

3단계: 항목 제거

마지막으로, t행의 적절한 배수를 추가하면, 위치(t,j_t)의 항목을 제외한 j열의_t 모든 항목이 0이라는 것을 알 수 있다. 이것은 적절한 행렬을 가진 왼쪽 곱셈을 통해 달성될 수 있다. 그러나 행렬을 완전히 대각선으로 만들기 위해서는 위치의 행(t,j_t)에 0이 아닌 항목도 제거해야 한다. 이는 행 대신 열에 대해 2단계의 단계를 반복하고, 획득한 행렬 L의 전치점에 의해 오른쪽에 있는 곱셈을 사용하여 달성할 수 있다. 일반적으로 이것은 3단계의 이전 적용에서 0 항목이 다시 0이 되는 결과를 초래할 것이다.

하지만 저 단계 2세의 행이나 칼럼의 각 응용 프로그램 δ(는 tjt){\displaystyle \delta(a_{t,j_{t}})}의 가치를 떨어뜨릴 수 있도록 과정 결국 반복 주기 몇가지의 후를 중단해야 합니다, 둘 다에 위치(t,jt)에서 엔트리를 있는 유일한 가 0이 아닌 항목이 행렬에 계속해야 합니다. row와 column

이때 (t,j_t)의 오른쪽 하단에 있는 A의 블록만 대각선으로 하면 되며, 개념적으로 알고리즘을 재귀적으로 적용할 수 있어 이 블록을 별도의 매트릭스로 취급한다. 즉 t를 하나씩 증가시켜 1단계로 돌아갈 수 있다.

최종 단계

어디 r≤분(m, n){\displaystyle r\leq \min(m,n)}. 매트릭스 항목(l. 위의 단계를 결과 매트릭스( 있는 경우)의 남아 있는 0이 아닌 기둥에 설명한 적용 1<>j, …<>j r{\displaystyle j_{1}<, \ldots <, j_{r}}칼럼 지수와 m×n{\displaystyle m\times의 스녀}-matrix다 , jl= ${\displaystyle(l,j_{l})$ 은 $(l,j_{l})$ 0이 아니며 다른 모든 항목은 0이다.

Now we can move the null columns of this matrix to the right, so that the nonzero entries are on positions $(i,i)$ for $1\leq i\leq r$ . For short, set $\alpha _{i}$ for the element at position $(i,i)$ .

대각선 입력의 구분 조건이 충족되지 않을 수 있다. 나는 < 어떤 지수 대응하며{\displaystyle i<, r}경우에 나는 α 나는}1{\displaystyle \alpha_{나는}\nmid \alpha _{i+1}+, 운영에 의해 나는{\displaystyle 나는}행과 열에 이러한 단점 고칠 수 있고 나는 + 1{\displaystyle를 i+1}, 첫번째 추가 칼럼 나는 + 1{\displaystyle를 i+1}{나는 column에 ∤ α.\disp $laystyle i}$ to get an entry $\alpha _{i+1}$ in column i without disturbing the entry $\alpha _{i}$ at position $(i,i)$ , and then apply a row operation to make the entry at position $(i,i)$ equal to $\beta =\gcd(\alpha _{i},\alpha _{i+1})$ $\beta =\gcd(\alpha _{i},\alpha _{i+1})$ $\beta =\gcd(\alpha _{i},\alpha _{i+1})$ + 1 ) ${\displaystyle \beta =\gcd(\alpha _{i},\alpha$ _{ $i+1}},$ 마지막으로 $\beta =\gcd(\alpha _{i},\alpha _{i+1})$ 3단계와 같이 진행하여 매트릭스를 다시 대각선으로 만든다. 위치에서의 신규 진입 $(i+1,i+1)$ + $(i+1,i+1)$ , $(i+1,i+1)$ + $(i+1,i+1)$ ) ${\displaystyle (i+1,i+1)$ 은 원래의 $\alpha _{i},\alpha _{i+1}$ i , $\alpha _{i},\alpha _{i+1}$ $\alpha _{i},\alpha _{i+1}$ + $\alpha _{i},\alpha _{i+1}$ 의 선형 결합이므로 $(i+1,i+1)$ $\$ }} $\alpha _{i},\alpha _{i+1}$ β로 구분할 수 있다 $\alpha _{i},\alpha _{i+1}$

The value $\delta (\alpha _{1})+\cdots +\delta (\alpha _{r})$ does not change by the above operation (it is δ of the determinant of the upper $r\times r$ submatrix), whence that operation does diminish (by moving prime factors to the right) the value of

\sum _{j=1}^{r}(r-j)\properties(\property _{j}).

따라서 이 연산을 정밀하게 많은 응용을 한 후에는 더 이상 적용할 수 없으며, 이는 우리가 원하는 대로 $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ α α $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ α $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ ${\$ \ $midalpha _{r}$ 을 얻었다는 것을 의미한다.

공정에 관련된 모든 행과 컬럼 조작은 수정이 불가능하므로, 이는 제품 SA T가 Smith 정상 형태의 정의를 만족하도록 변환 $m\times m$ 한 m $m\times m$ × $m\times m$ $m\times m$ 과 $m\times m$ $n\times n$ $n\times n$ n ${\displaystystyle n\times n}$ -matrix $n\times n$ S, T가 존재함을 보여준다. 특히 이는 정의에 근거 없이 가정된 스미스 정상 형태가 존재함을 보여준다.

적용들

스미스 정상 형태는 체인 단지의 체인 모듈이 미세하게 생성될 때 체인 단지의 호몰로리지를 계산하는데 유용하다. 예를 들어, 위상에서는 그러한 복합체 내의 경계 지도가 정수 행렬에 불과하기 때문에 정수에 걸쳐 단순 복합체나 CW 복합체의 동질성을 계산하는 데 사용할 수 있다. 또한 주 이상영역에 걸쳐 정밀하게 생성된 모듈에 대해 구조 정리에서 발생하는 불변 인자를 결정하는 데도 사용할 수 있으며, 정밀하게 생성된 아벨리아 집단의 근본적인 정리를 포함한다.

스미스 정상 형태는 전송과 전송 함수 매트릭스의 차단 0을 계산하기 위해 제어 이론에도 사용된다.^[2]

예

예를 들어, 우리는 다음 행렬의 일반적인 형태를 정수를 통해 찾을 것이다.

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

알고리즘이 상기 매트릭스에 적용되는 중간 단계는 다음과 같다.

\to {\pmatrix}2&0&0\\-6&18&24\\\\10&-16&-4\end{pmatrix}\to {\\pmatrix}2&0&0&0&0&0&24\0&-16-4\end{pmatrix}}}}}}}

\to {\pmatrix}2&0&0\0&0\2&20\\0&#4\end{pmatrix}\to {\\pmatrix}2&0&0&#0&#0&#0&#0&#end{pmatrix}}}}}}}}}}

\to {\pmatrix}2&0&0\\0&0&0\\0&#0&#0&#8226\end{pmatrix}}}

그래서 스미스 정상적인 형태는

{\pmatrix}2&0&0\0&0&0\\0&0&0\\0&#0&#8226\end{pmatrix}}}

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

유사성

Smith 정규 양식을 사용하여 공통 필드에 입력된 행렬이 유사한지 여부를 결정할 수 있다. 특히 두 행렬 $xI-A$ 와 B는 특성 행렬 x $xI-A$ - A {\ $displaystyle xI-A}$ 과 $xI-B$ x I - B {\ $displaystyle$ xI-B $}$ 이 $xI-A$ (가) 동일한 Smith 정규 형식을 갖는 $xI-B$ 경우에만 유사하다.

예를 들어, 와 함께.

{\reasoned}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}}}}}}}}}}}\nd{bmatrix\nd{bmatrix}\C&{}={\begin{bmatrix}1&0\1&2\end{bmatrix},&{\mbox{SNF}}(xI-C)={\begin{bmatrix}1&0\(x-1)\end{bmatrix}}}.\end{정렬}}

A와 B는 스미스 정상 형태의 특성 행렬이 일치하기 때문에 유사하지만, 특성 행렬의 스미스 정상 형태가 일치하지 않기 때문에 C와 비슷하지 않다.

참고 항목

메모들

^ Stanley, Richard P. (2016). "Smith normal form in combinatorics". Journal of Combinatorial Theory, Series A. 144: 476–495.
^ Maciejowski, Jan M. (1989). Multivariable feedback design. Wokingham, England: Addison-Wesley. ISBN 0201182432. OCLC 19456124.

참조

Smith, Henry J. Stephen (1861). "On systems of linear indeterminate equations and congruences". Phil. Trans. R. Soc. Lond. 151 (1): 293–326. doi:10.1098/rstl.1861.0016. JSTOR 108738. 헨리 존 스티븐 스미스의 수학적 논문집(pp. 367–409)에 재인쇄되었다. 나는 J. W. L. Glaisher가 편집했다. 옥스퍼드: Clarendon Press (1894), xcv+603 pp.
플래닛매트릭스의 스미스 정상형.
PlanetMath에서 Smith 정규 형식의 예.
K. R. Matthews, Smith 정상형. MP274: Linear 대수학, 강의 노트, 퀸즐랜드 대학교, 1991.

외부 링크

Smith 정규 형식 계산의 애니메이션 예.

[1] Stanley, Richard P. (2016). "Smith normal form in combinatorics". Journal of Combinatorial Theory, Series A. 144: 476–495.

[2] Maciejowski, Jan M. (1989). Multivariable feedback design. Wokingham, England: Addison-Wesley. ISBN 0201182432. OCLC 19456124.

[1]

[2]

Search