📂位相データ分析

スミス標準形の存在証明

アルゴリズム

$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上の行列でもある。従って、単元や$0$でない全ての要素$A_{ij}$は、ユニークな因数分解を持ち、その中で最も少ない因数の数を持つ要素の絶対値を$\alpha > 0$と表示し、ミニマルエントリー^{minimal Entry}と呼ぶ。

ちなみにMunkeresの教科書では$\mathbb{Z}^{m \times n}$で、単に最も小さい要素を選ぶのだが、整数環$\mathbb{Z}$ではなく、一般的な主イデアル領域はユークリッド領域である保証すらないため、要素だけ見て「最小」と判断するのは難しい。一般的なPIDできれいにミニマルエントリーを定める場合、因数分解を考えるのが妥当だ。ただし、このポストでは便宜上、「小さい」や$a < b$のような表現が出てくるが、これは要素の大きさではなく、因数の数を比較していると理解すればいい。

与えられた行列はガウス消去法により続けて変化するため、$\alpha$も文脈によって続けて変化することに注意せよ。

ちなみに、このアルゴリズムは与えられた$A$に対して必ずスミス標準形を導けることを数学的に見せるためのアルゴリズムであり、特に効率的というわけではなく$P, Q$も分からない。

---

ステップ1.

$A$がゼロ行列なら、そのままでスミス標準形なのでステップ4に進む。$A$がゼロ行列でないなら、以下を実行する。

理解しやすくするために、まず行と列を交換して、$\alpha$を左上の$(1,1)$に引き上げよう。これから与えられた行列のほとんどを気にせずに、最初の行、最初の列だけを見ることになる。 $$A \sim \begin{bmatrix} \alpha & A_{12} & \cdots & \\ A_{21} & A_{22} & \cdots & \\ \vdots & \vdots & \ddots & \end{bmatrix}$$

---

ステップ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$列を削除してステップ1に戻る。この時、行列$A$のサイズは$(m - k) \times (n - k)$になる。
• 何らかの$i, j$に対して$\alpha \nmid A_{ij}$ならば、ステップ3に進む。

---

ステップ3.

ここからの議論は、行でも列でも、一方が成り立てば他方にも適用できるので、一般性を失わずに$\alpha \ne 0$と$A_{12}$だけを扱おう。基本的にはステップ2で少なくとも一つの$i, j$に対して$\alpha \nmid A_{ij}$が保証され、$(1,2)$の下にその$A_{ij}$が来るように以下のCase1を実施することを目指す。

主イデアル領域はベズー領域である: PIDはベズー領域なので、拡張ユークリッドの定理が成立する。つまり、全ての$a, b \in D$に対して、次を満たす$m,n \in D$が存在する。 $$m a + n b = \gcd \left( a, b \right)$$

• ケース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$列を交換して、ステップ1に戻る（計算中に偶然、より小さいミニマルエントリーが存在する可能性もある）。
• ケース2. $\alpha \mid A_{12}$の場合
  $k \alpha + A_{12} = 0$を満たす何らかの$k \in \mathbb{Z}$が存在するので、$1$列に$k$を掛けて、$2$列から引く。すると、この新しい列の最初の要素である$A_{12} '$は$0$となる。ステップ3を繰り返す。
• ケース3. $A_{12} = 0$の場合
  $A_{12} \ne 0$になるまで列交換を繰り返す。全ての$j \ne 1$に対して、全て