整数行列のスミス標準形・エルミート標準形を計算する

整数行列のスミス標準形とエルミート標準形とそれぞれの変換行列が欲しい状況に遭遇したのだが、標準的なpythonのライブラリには実装されていなかったので自分で書いた。

github.com

スミス標準形の実装には以下のブログを大いに参考にした(というかほぼそのまま):
www.dlfer.xyz


スミス標準形は大まかには、行列の左上から右下にかけて値を確定させていき、対角線上にまだ値が確定していない範囲の整数の最大公約数が来るように行と列を入れ替えていくことで得られる。

ユニモジュラ行列による基本変形によって最大公約数が求められるのはユークリッドの互除法が動くのと同じ理屈になっている。


また、エルミート標準形を求めるときはスミス標準形を求める手続きのなかで行(列)を動かす操作を取り除いて同様にユークリッドの互除法をすればよい。


ところでwikipedia を読んで初めて知ったのだが、整数行列AをH=UAと分解するのをrow-style Hermite normal form、H=ARと分解するのをcolumn-style Hermite normal form と呼ぶらしい。

en.wikipedia.org