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