行列の正規形
数学 において 、スミス正規形 （スミスしょうこ、英: Smith normal form、SNF [1] と略されることもある ） は 、 主 イデアル領域 (PID)に要素を持つ任意の行列 (必ずしも正方行列ではない) に対して 定義 できる 正規 形である 。行列 のスミス正規形は 対角行列 であり、元の行列の左右に 可逆な 正方行列を乗じることで得られる。特に、 整数 は PID であるため、 整数行列のスミス正規形を常に計算できる。スミス正規形は、PID 上の 有限生成 加群 を扱う場合、特に 自由加群 の 商 の構造を演繹する場合に非常に便利である。これはアイルランドの数学者 ヘンリー・ジョン・スティーブン・スミス にちなんで名付けられた 。
意味 を主イデアル領域 上の 非零行列と する。 の
要素を持つ可逆な -行列 と -行列 が存在し 、その積は
あ
{\displaystyle A}
メートル × ん
{\displaystyle m\times n}
R
{\displaystyle R}
メートル × メートル
{\displaystyle m\times m}
ん × ん
{\displaystyle n\times n}
ス 、 T
{\displaystyle S,T}
R
{\displaystyle R}
ス あ T
{\displaystyle SAT}
（
α
1
0
0
⋯
0
⋯
0
0
α
2
0
0
0
⋱
⋮
⋮
⋮
α
r
0
⋯
0
⋯
0
⋮
⋮
⋮
0
⋯
0
⋯
0
）
。
{\displaystyle {\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}}.}
対角要素は すべての に対して を 満たす 。これは行列 のスミス標準形である 。要素は 単位 倍数を 除いて 一意であり、 基本因子 、 不変量 、または 不変因子 と呼ばれる 。これらは（単位倍数を除いて）次のように計算できる。
α
私
{\displaystyle \alpha_{i}}
α
私
∣
α
私 + 1
{\displaystyle \alpha _{i}\mid \alpha _{i+1}}
1 ≤ 私 < r
{\displaystyle 1\leq i<r}
あ
{\displaystyle A}
α
私
{\displaystyle \alpha_{i}}
α
私
=
d
私
（ あ ）
d
私 − 1
（ あ ）
、
{\displaystyle \alpha _{i}={\frac {d_{i}(A)}{d_{i-1}(A)}},}
ここで、 （ i 番目の 行列式約数 と呼ばれる）は 、 行列のすべての 小行列式 の行列式の最大公約数 と 等しくなります。
d
私
（ あ ）
{\displaystyle d_{i}(A)}
私 × 私
{\displaystyle i\times i}
あ
{\displaystyle A}
d
0
（ あ ） := 1
{\displaystyle d_{0}(A):=1}
例: および の 行列 の場合 。
2 × 2
{\displaystyle 2\times 2}
ス いいえ ふ
（
1つの
b
c
d
）
=
d 私 1つの グ
（
d
1
、
d
2
/
d
1
）
{\displaystyle {\rm {SNF}}{a~~b \choose c~~d}={\rm {diag}}(d_{1},d_{2}/d_{1})}
d
1
= いいえ （ 1つの 、 b 、 c 、 d ）
{\displaystyle d_{1}=\gcd(a,b,c,d)}
d
2
=
|
1つの d − b c
|
{\displaystyle d_{2}=|ad-bc|}
アルゴリズム 最初の目標は、積が対角になるような可逆な正方行列 および を見つけることです 。これがアルゴリズムの最も難しい部分です。対角性が達成されると、行列をスミス正規形にすることは比較的簡単になります。より抽象的に言えば、目標は、 を( ランク の 自由- モジュール )から ( ランク の 自由- モジュール) へ の写像として考えたとき 、対角行列の単純な形式を持つ 同型 およびが存在する ことを示すことです 。行列 および は、適切なサイズの単位行列から始めて、アルゴリズムで に対して行演算 が実行されるたびに を対応する列 演算で変更し (たとえば、 の 行に行を追加する場合、積の不変量を維持するために の列から 列を 減算する必要があります )、同様に 実行される列演算ごとに を変更することで見つけることができます。行演算は左乗算で列演算は右乗算であるため、これにより不変量が保持されます。 ここで は 現在の値を表し、 は 元の行列を表します。 最終的に、この不変量の行列は対角行列になります。可逆な行と列の演算のみが実行されるため、 と は 可逆な行列のままであることが保証されます。
ス
{\displaystyle S}
T
{\displaystyle T}
ス あ T
{\displaystyle SAT}
あ
{\displaystyle A}
R
ん
{\displaystyle R^{n}}
R
{\displaystyle R}
ん
{\displaystyle n}
R
メートル
{\displaystyle R^{m}}
R
{\displaystyle R}
メートル
{\displaystyle m}
ス :
R
メートル
→
R
メートル
{\displaystyle S:R^{m}\to R^{m}}
T :
R
ん
→
R
ん
{\displaystyle T:R^{n}\to R^{n}}
ス ⋅ あ ⋅ T
{\displaystyle S\cdot A\cdot T}
ス
{\displaystyle S}
T
{\displaystyle T}
ス
{\displaystyle S}
あ
{\displaystyle A}
私
{\displaystyle i}
じ
{\displaystyle j}
あ
{\displaystyle A}
じ
{\displaystyle j}
私
{\displaystyle i}
ス
{\displaystyle S}
T
{\displaystyle T}
あ ′
=
ス ′
⋅ あ ⋅
T ′
{\displaystyle A'=S'\cdot A\cdot T'}
あ ′
、
ス ′
、
T ′
{\displaystyle A',S',T'}
あ
{\displaystyle A}
ス
{\displaystyle S}
T
{\displaystyle T}
について 、 の素因数の個数を と書きます (これらは存在し、一意です。なぜなら、任意の PID は 一意の因数分解領域 でもあるからです)。特に、は ベズー領域 でもあるため、これは gcd 領域 であり 、任意の 2 つの要素の gcd は ベズーの恒等式 を満たします。
1つの ∈ R ∖ { 0 }
{\displaystyle a\in R\setminus \{0\}}
δ （ 1つの ）
{\displaystyle \delta (a)}
1つの
{\displaystyle a}
R
{\displaystyle R}
行列をスミス正規形にするには、次の式を繰り返し適用します。ここで、 は 1 から までループします 。
t
{\displaystyle t}
メートル
{\displaystyle m}
ステップ1: ピボットの選択 非ゼロのエントリを持つ の最小の列インデックス を 選択し、 の場合の列インデックスから検索を開始します 。
じ
t
{\displaystyle j_{t}}
あ
{\displaystyle A}
じ
t − 1
+ 1
{\displaystyle j_{t-1}+1}
t > 1
{\displaystyle t>1}
が実現されることを望みます 。この場合、このステップは完了です。そうでない場合は、仮定により が存在するため 、 行 と を交換して を取得できます 。
1つの
t 、
じ
t
≠ 0
{\displaystyle a_{t,j_{t}}\neq 0}
け
{\displaystyle k}
1つの
け 、
じ
t
≠ 0
{\displaystyle a_{k,j_{t}}\neq 0}
t
{\displaystyle t}
け
{\displaystyle k}
1つの
t 、
じ
t
≠ 0
{\displaystyle a_{t,j_{t}}\neq 0}
選択したピボットは現在位置にあります 。
（ t 、
じ
t
）
{\displaystyle (t,j_{t})}
ステップII: ピボットの改善 位置 ( k , j t ) に となる要素がある場合 、 とすると 、ベズー特性により R に σ, τ が存在し、
1つの
t 、
じ
t
∤
1つの
け 、
じ
t
{\displaystyle a_{t,j_{t}}\nmid a_{k,j_{t}}}
β = いいえ
（
1つの
t 、
じ
t
、
1つの
け 、
じ
t
）
{\displaystyle \beta =\gcd \left(a_{t,j_{t}},a_{k,j_{t}}\right)}
1つの
t 、
じ
t
⋅ σ +
1つの
け 、
じ
t
⋅ τ = β 。
{\displaystyle a_{t,j_{t}}\cdot \sigma +a_{k,j_{t}}\cdot \tau =\beta .}
適切な可逆行列 L との左乗算により、 行列積の行 t は元の行 t の σ 倍と元の行 k の τ 倍の合計となり、積の行 k は元の行の別の線形結合となり、他のすべての行は変更されないことが達成される。明示的には、 σ と τ が上記の式を満たす場合、 および （β の定義により分割が可能）に対して、 次 が成り立つ。
α =
1つの
t 、
じ
t
/
β
{\displaystyle \alpha =a_{t,j_{t}}/\beta}
γ =
1つの
け 、
じ
t
/
β
{\displaystyle \gamma =a_{k,j_{t}}/\beta}
σ ⋅ α + τ ⋅ γ = 1 、
{\displaystyle \sigma \cdot \alpha +\tau \cdot \gamma =1,}
マトリックス
ら
0
=
（
σ
τ
− γ
α
）
{\displaystyle L_{0}={\begin{pmatrix}\sigma &\tau \\-\gamma &\alpha \\\end{pmatrix}}}
は逆であり、逆は
（
α
− τ
γ
σ
）
。
{\displaystyle {\begin{pmatrix}\alpha &-\tau \\\gamma &\sigma \\\end{pmatrix}}.}
ここで、 L は 単位行列の t 行 と k 列に 適合させることで得られます。構築により、 Lを左から乗算した後に得られる行列には、位置 ( t 、 j t )にエントリ β が含まれます (また、 α と γ の選択により、位置 ( k 、 j t ) にエントリ 0 も含まれますが、これはアルゴリズムには必須ではありませんが便利です)。この新しいエントリ β は、 以前存在していたエントリを割り切ります。したがって、特に です。したがって、これらの手順を繰り返すと、最終的には終了する必要があります。最終的には、列 j t のすべてのエントリを割り切る位置 ( t 、 j t ) のエントリを持つ行列になります 。
ら
0
{\displaystyle L_{0}}
1つの
t 、
じ
t
{\displaystyle a_{t,j_{t}}}
δ （ β ） < δ （
1つの
t 、
じ
t
）
{\displaystyle \delta (\beta )<\delta (a_{t,j_{t}})}
ステップIII: エントリの削除 最後に、行 tの適切な倍数を追加することで、位置 ( t 、 j t ) を除く列 j t のすべてのエントリがゼロになることが実現できます。これは、適切な行列の左乗算によって実現できます。ただし、行列を完全に対角にするには、位置 ( t 、 j t ) の 行 の 非ゼロのエントリも削除する必要があります 。 これ は 、 ステップ II の手順を行ではなく列に対して繰り返し、得られた行列 L の転置を右側で乗算することで実現できます。一般に、これにより、ステップ III の前の適用からのゼロのエントリが再び非ゼロになります。
ただし、行または列のいずれかにステップ II を適用するたびに の値が減り続けるため、このプロセスは最終的にいくつかの反復後に停止し、位置 ( t 、 j t )のエントリが行と 列の両方で唯一のゼロ以外のエントリとなる行列になることに注意してください。
δ （
1つの
t 、
じ
t
）
{\displaystyle \delta (a_{t,j_{t}})}
この時点では、( t , j t )の右下にある A のブロックのみ を対角化する必要があり、概念的には、このブロックを別の行列として扱い、アルゴリズムを再帰的に適用できます。つまり、 t を 1 増やして、ステップ I に戻ること
ができます。
最終ステップ 結果の行列の残りの非ゼロ列（存在する場合）に上記の手順を適用すると、 列インデックスが である - 行列が得られます 。行列のエントリは 非ゼロで、他のすべてのエントリはゼロです。
メートル × ん
{\displaystyle m\times n}
じ
1
< … <
じ
r
{\displaystyle j_{1}
r ≤ 分 （ メートル 、 ん ）
{\displaystyle r\leq \min(m,n)}
（ l 、
じ
l
）
{\displaystyle (l,j_{l})}
ここで、この行列の null 列を右に移動して、非ゼロのエントリが の位置になるようにすることができます 。 つまり、 位置 の要素を に設定します 。
（ 私 、 私 ）
{\displaystyle (i,i)}
1 ≤ 私 ≤ r
{\displaystyle 1\leq i\leq r}
α
私
{\displaystyle \alpha_{i}}
（ 私 、 私 ）
{\displaystyle (i,i)}
対角要素の割り切れる条件は満たされない可能性があります。 となる任意のインデックスについて、行と列に対する操作と のみ によってこの欠点を修正できます 。まず、 位置 の 要素に影響を与えずに列 i の 要素を得るために列 を 列に追加し、次にステップ II の ように 行操作を適用して位置 の要素を に等しくします 。最後にステップ III のように続行して、行列を再び対角にします。位置 の新しい要素は 元の の線形結合であるため 、β で割り切れます。
私 < r
{\displaystyle i<r}
α
私
∤
α
私 + 1
{\displaystyle \alpha _{i}\nmid \alpha _{i+1}}
私
{\displaystyle i}
私 + 1
{\displaystyle i+1}
私 + 1
{\displaystyle i+1}
私
{\displaystyle i}
α
私 + 1
{\displaystyle \alpha_{i+1}}
α
私
{\displaystyle \alpha_{i}}
（ 私 、 私 ）
{\displaystyle (i,i)}
（ 私 、 私 ）
{\displaystyle (i,i)}
β = いいえ （
α
私
、
α
私 + 1
）
{\displaystyle \beta =\gcd(\alpha _{i},\alpha _{i+1})}
（ 私 + 1 、 私 + 1 ）
{\displaystyle (i+1,i+1)}
α
私
、
α
私 + 1
{\displaystyle \alpha_{i},\alpha_{i+1}}
上の操作によって値は 変化しない（それは上側部分 行列の行列式のδである）ので、その操作は（素因数を右に移動することによって）値を減少させる。
δ （
α
1
） + ⋯ + δ （
α
r
）
{\displaystyle \delta (\alpha _{1})+\cdots +\delta (\alpha _{r})}
r × r
{\displaystyle r\times r}
∑
じ = 1
r
（ r − じ ） δ （
α
じ
） 。
{\displaystyle \sum _{j=1}^{r}(rj)\delta (\alpha _{j}).}
したがって、この操作を有限回適用した後は、それ以上の適用は不可能になり、 目的の結果が得られたことになります。
α
1
∣
α
2
∣ ⋯ ∣
α
r
{\displaystyle \alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}}
このプロセスに含まれるすべての行と列の操作は可逆であるため、可逆行列 S、T が存在し、積 SAT がスミス正規形の定義を満たすことが示されます 。 特に 、 定義 で は証明なしに想定されていたスミス正規形が存在することが示されます。
メートル × メートル
{\displaystyle m\times m}
ん × ん
{\displaystyle n\times n}
アプリケーション スミス標準形は、 連鎖複体 の連鎖加群が 有限生成 である場合に、連鎖複体の ホモロジー を計算するのに役立ちます。たとえば、 位相幾何学 では、そのような複体の境界写像は単なる整数行列であるため、スミス標準形を使用して、整数上の有限 単体複体 または CW 複体のホモロジーを計算することができます。また、 有限生成アーベル群の基本定理 を含む 主イデアル領域上の有限生成加群の構造定理 で発生する 不変因子を 決定するためにも使用できます 。
スミス正規形は 制御理論において 伝達関数行列 の伝達零点と阻止零点を計算するためにも使われる 。 [2]
例 例として、整数上の次の行列のスミス正規形を見つけます。
（
2
4
4
− 6
6
12
10
4
16
）
{\displaystyle {\begin{pmatrix}2&4&4\\-6&6&12\\10&4&16\end{pmatrix}}}
次の行列は、上記の行列にアルゴリズムを適用したときの中間ステップです。
→
(
2
0
0
−
6
18
24
10
−
16
−
4
)
→
(
2
0
0
0
18
24
0
−
16
−
4
)
{\displaystyle \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}}}
→
(
2
0
0
0
2
20
0
−
16
−
4
)
→
(
2
0
0
0
2
20
0
0
156
)
{\displaystyle \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}}}
→
(
2
0
0
0
2
0
0
0
156
)
{\displaystyle \to {\begin{pmatrix}2&0&0\\0&2&0\\0&0&156\end{pmatrix}}}
スミス正規形は
(
2
0
0
0
2
0
0
0
156
)
{\displaystyle {\begin{pmatrix}2&0&0\\0&2&0\\0&0&156\end{pmatrix}}}
不変因子は 2、2、156 です。
実行時の複雑さ N 行 N 列の行列 A のスミス正規形は、 時間で計算できます 。 [3] 行列が 疎な 場合、計算は通常はるかに高速になります。
O
(
‖
A
‖
log
‖
A
‖
N
4
log
N
)
{\displaystyle O(\|A\|\log \|A\|N^{4}\log N)}
類似性 スミス正規形は、共通体上の要素を持つ行列が 類似して いる かどうかを判断するために使用できます 。具体的には、2 つの行列 A と B が 類似しているのは、 特性 行列 とが 同じスミス正規形 (PID で動作) を持つ 場合のみです 。
K
{\displaystyle K}
x
I
−
A
{\displaystyle xI-A}
x
I
−
B
{\displaystyle xI-B}
K
[
x
]
{\displaystyle K[x]}
例えば、
A
=
[
1
2
0
1
]
,
SNF
(
x
I
−
A
)
=
[
1
0
0
(
x
−
1
)
2
]
B
=
[
3
−
4
1
−
1
]
,
SNF
(
x
I
−
B
)
=
[
1
0
0
(
x
−
1
)
2
]
C
=
[
1
0
1
2
]
,
SNF
(
x
I
−
C
)
=
[
1
0
0
(
x
−
1
)
(
x
−
2
)
]
.
{\displaystyle {\begin{aligned}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{aligned}}}
A と B は、 特性行列のスミス正規形が一致するため類似していますが、特性行列のスミス正規形が一致しないため、
C とは類似していません。
参照
注記
^ Stanley, Richard P. (2016). 「組合せ論におけるスミス正規形」. 組合せ理論ジャーナル . シリーズ A. 144 : 476–495 . arXiv : 1602.00166 . doi : 10.1016/j.jcta.2016.06.013 . S2CID 14400632. ^ Maciejowski, Jan M. (1989). 多変量フィードバック設計 . ウォキンガム、イギリス: Addison-Wesley. ISBN 0201182432 . OCLC 19456124. ^ 「Maple でのスミス正規形の計算時間」。MathOverflow。2024 年 4 月 5 日 閲覧 。
参考文献
外部リンク 
![{\displaystyle K[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a9e6c2ac2830d6a9abe078b47450777c41d69a9)
