整数行列の単因子
この記事の内容:単因子論の整数バージョンの、単因子標準形に変形できるところまでの証明。一意性は示していない。
整数を成分とするm×n次正方行列全体をM(m,n;ℤ)と書く。
基本行列 とは、次のようなN次正方行列のこと。
m×n行列にm次基本行列を左からかける操作を左基本変形, n次基本行列を右からかける操作を右基本変形と呼ぶ。両方を合わせて単に基本変形と呼ぶ。
二つの行列A, B∊M(m,n;ℤ) が、何回かの基本変形によって移りあうとき、AとBは対等であると言う。
次の定理が成り立つ。
定理 任意の行列 A∊M(m,n;ℤ) は次の単因子形に対等である。
ただし、各eᵢは正の整数で、e₁|e₂| … |eᵣ (a|b はaがbを割り切ることを表す)。
さらに、この単因子形はAによって一意に決まる。正方行列のように見えるが違うことに注意。対角線は右下端に達するとは限らない。
今回は定理の前半を示す。
m,nに関する数学的帰納法で示す。
m=1, n=1 ならば明らか。
Aが零行列ならそれが単因子形だから、零行列ではないとする。
このとき、Aと対等な行列で、(1,1)成分が0でないものが少なくとも1つ存在する。
このような行列全体を考え、そのうちで(1,1)成分の絶対値が最小であるようなものの1つをとる。(1,1)成分が負の場合にを左右どちらかから掛ければ、Aと対等で(1,1)成分が正の行列
が得られる。
このとき、Bの第一行および第一列の成分はすべてe₁で割り切れる。
なぜか説明しよう。b₁ⱼ (j≠1) がe₁ で割り切れないとする。このとき b₁ⱼ = e₁q + r となるような整数 q, r (0 < r < e₁)が存在する。B に右から Rₙ(j,1,-q) をかけ(これはj列に1列の-q倍を足す操作)、さらに右からPₙ(1,j)をかければ(1列とj列の交換)、得られる行列はAと対等で、(1,1)成分は r である。0 < r < e₁ よりこれはBのとりかたに矛盾する。
bᵢ₁ (i≠1)についても同様。
よってBの第一行および第一列の成分はすべてe₁で割り切れるから、掃き出し法により
(CはBと対等, したがってAと対等) が得られる。
m=1またはn=1のとき、これが単因子形。そうでないとき、Cの第一行と第一列を取り去った残りの行列
に数学的帰納法を適用すれば、これは単因子形
に移る。同じ変形でCも
に移る(DもAと対等)このとき、e₂はe₁で割り切れる。
なぜか説明しよう。e₂ がe₁ で割り切れないとする。このとき e₂ = e₁q + r となるような整数 q, r (0 < r < e₁)が存在する。B に右から Rₙ(2,1,-q) をかけ(これは2列に1列の-q倍を足す操作)、さらに左からRₘ(2,1,1)をかければ(2行に1行を足す)、得られる行列はAと対等で、(結局(2,2)に(1,1)の-q倍が足されるから) (2,2)成分は r である。行と列の入れ替えで(1,1)成分をrにできる。0 < r < e₁ よりこれはBのとりかた((1,1)成分の絶対値はすべてのAと対等な行列の中で最小)に矛盾する(DもAと対等かつ(1,1)成分rがe₁より小さいから)。
よってDは単因子形だから、以上より定理の前半が示された。