Hermite標準形

列を左から順に処理し、次の状態を保つ：第 $j-1$ 列まで処理し終えたとき、ある $t$ について、第 $1$ 行から第 $t$ 行までの部分は第 $j-1$ 列までについて定義の条件 2・3 を満たし（ピボット列はすべて $j-1$ 以下）、第 $t+1$ 行から第 $m$ 行までは第 $1$ 列から第 $j-1$ 列まですべて $0$ である。最初は $j=1$、$t=0$ でこの状態にある。
第 $j$ 列を処理する。第 $t+1$ 行から第 $m$ 行までの第 $j$ 成分がすべて $0$ なら、何もしないで次の列に進む。そうでないとき、この成分を並べた列ベクトルに 基本変形 の記事の補題「列の Euclid の互除法」を当てると（成分が 1 つだけなら何もしない）、(iii) 型の基本行列の積 $E$ で第 $j$ 成分が $(d,0,\dots,0)^{\top}$（$d\ne0$）になるものがある。$E$ を第 $t+1$ 行から第 $m$ 行までに施す（$\operatorname{diag}(I_t,E)$ を左から掛ける）。これらの行は第 $j-1$ 列まで $0$ だったので、その整数係数の結合もそこまで $0$ である。$d<0$ なら第 $t+1$ 行を $-1$ 倍する。こうして第 $t+1$ 行は第 $j$ 列に正の成分 $p:=|d|$ をもち、その左は $0$、その下の第 $j$ 成分は $0$ になる。
次に $k\le t$ について、第 $k$ 行の第 $j$ 成分 $a$ を $a=\lfloor a/p\rfloor p+b$（$0\le b< p$）と割り、第 $k$ 行から第 $t+1$ 行の $\lfloor a/p\rfloor$ 倍を引く。第 $t+1$ 行は第 $j-1$ 列まで $0$ なので、第 $k$ 行の第 $j-1$ 列までの成分は変わらず、すでに満たしていた条件 3 は壊れない。第 $j$ 成分は $b$ になる。$j_{t+1}:=j$ とし、$t$ を $t+1$ に進めると、第 $j$ 列まで状態が保たれる。
すべての列を処理すると、第 $t+1$ 行以下は $0$ で、第 $1$ 行から第 $t$ 行は条件 2・3 を満たすので、Hermite 標準形を得る（$r=t$）。使った変形はすべて基本行列を左から掛けることなので、その積を $U$ とすればよい。$\square$

1：$i< i_0$ では $c_i=0$ であり、$i\ge i_0$ の $h_i$ は第 $j_i\ge j_{i_0}$ 列より左で $0$ なので、$x$ も第 $j_{i_0}$ 列より左で $0$ である。第 $j_{i_0}$ 列では、$i>i_0$ の $h_i$ の成分はピボットの下なので $0$ であり、$x_{j_{i_0}}=c_{i_0}p_{i_0}\ne0$ である。よって $\sum c_ih_i=0$ ならすべての $c_i=0$ で、$h_1,\dots,h_r$ は線形独立である。$\Lambda$ を生成するので基底である。
2：$x=\sum c_ih_i\in\Lambda_{\ge j}$ で $x\ne0$ なら、1 の $i_0$ について $x_{j_{i_0}}\ne0$ なので $j_{i_0}\ge j$ であり、$c_i\ne0$ となる $i$ はすべて $j_i\ge j_{i_0}\ge j$ を満たす。逆に $j_i\ge j$ なら $h_i\in\Lambda_{\ge j}$ である。
3：2 により $x\in\Lambda_{\ge j}$ は $j_i\ge j$ の $h_i$ の結合である。$j_i>j$ の $h_i$ は第 $j$ 成分が $0$ なので、$j$ がピボット列でなければ $x_j=0$ であり、$j=j_i$ なら $x_j=c_ip_i$ である。$h_i$ 自身が $p_i$ を与えるので、集合は $p_i\mathbb{Z}$ である。$\square$

$\Lambda:=\Lambda(H)=\Lambda(H')$ とする。lem-hnf-rows の 3 により、ピボット列の集合は「$\{x_j\mid x\in\Lambda_{\ge j}\}\ne\{0\}$ となる $j$ の全体」であり、ピボットはその部分群の正の生成元である。これは $\Lambda$ だけで決まるので、$H$ と $H'$ は $r$、ピボット列 $j_1< \cdots< j_r$、ピボット $p_1,\dots,p_r$ が一致する。$m-r$ 個の $0$ の行も一致する。
$i\le r$ を固定し、$H$、$H'$ の第 $i$ 行を $h_i$、$h'_i$ として $x:=h_i-h'_i\in\Lambda$ とおく。$h_i$ と $h'_i$ はどちらも第 $j_i$ 列より左で $0$、第 $j_i$ 成分が $p_i$ なので、$x$ は第 $j_i$ 列まで $0$ である。$j_i=n$ ならこれで $x=0$ であり、$j_i< n$ なら $x\in\Lambda_{\ge j_i+1}$ である。lem-hnf-rows の 2 により $x=\sum_{k>i}c_kh_k$ と書ける。$x\ne0$ と仮定し、$c_k\ne0$ となる最小の $k$ を $k_0$ とする。lem-hnf-rows の 1 により $x_{j_{k_0}}=c_{k_0}p_{k_0}$ は $p_{k_0}$ の $0$ でない倍数である。一方 $k_0>i$ なので、定義の条件 3 により $0\le H_{i,j_{k_0}}< p_{k_0}$、$0\le H'_{i,j_{k_0}}< p_{k_0}$ で、差の絶対値 $|x_{j_{k_0}}|$ は $p_{k_0}$ 未満である。これは矛盾なので $x=0$、$h_i=h'_i$ である。よって $H=H'$ である。
同値性：1 ⇒ 2 は定義のあとで示した。2 ⇒ 3：$A$、$B$ の Hermite 標準形 $H_A$、$H_B$ は $\Lambda(H_A)=\Lambda(A)=\Lambda(B)=\Lambda(H_B)$ を満たすので、前半により等しい。3 ⇒ 1：$H=U_1A=U_2B$ なら $B=U_2^{-1}U_1A$ である。$\square$

$r=n$ でピボット列は $n$ 列のうちの $n$ 個なので $j_i=i$ であり、$H$ は上三角で対角成分が $p_i$ である。集合 $R:=\{y\in\mathbb{Z}^n\mid 0\le y_j< p_j\ (1\le j\le n)\}$ が $\mathbb{Z}^n/\Lambda$ の完全代表系であることを示す。
代表の存在：$x\in\mathbb{Z}^n$ に対し、$j=1,2,\dots,n$ の順に、第 $j$ 成分を $p_j$ で割った商の分だけ $h_j$（$H$ の第 $j$ 行）を引く。$h_j$ は第 $j$ 列より左で $0$ なので、すでにそろえた第 $1$ 成分から第 $j-1$ 成分は変わらない。最後に $R$ の元 $y$ で $x-y\in\Lambda$ となるものを得る。
一意性：$y,y'\in R$、$y\ne y'$、$y-y'\in\Lambda$ とすると、lem-hnf-rows の 1 により、$y-y'=\sum c_kh_k$ の $0$ でない係数のうち最小の番号 $k_0$ について、第 $k_0$ 成分 $y_{k_0}-y'_{k_0}$ は $p_{k_0}$ の $0$ でない倍数である。しかし $|y_{k_0}-y'_{k_0}|< p_{k_0}$ なので矛盾する。
よって $[\mathbb{Z}^n:\Lambda]=|R|=p_1\cdots p_n=\det H$ である。$\det A\ne0$ なら $\Lambda(A)$ の Hermite 標準形 $H=UA$ は階数 $n$ で、$\det U=\pm1$ から $|\det A|=\det H$ である。$\square$

$\Lambda$ の指数が $N$ なら、Lagrangeの定理 の記事の系「元の位数」により $\mathbb{Z}^n/\Lambda$ の元の位数は $N$ を割るので $N\mathbb{Z}^n\subset\Lambda$ であり、$\Lambda$ は階数 $n$ である。thm-hnf-unique と cor-hnf-index により、指数 $N$ の部分群は、対角成分の積が $N$ の $n$ 次 Hermite 標準形と一対一に対応する。対角成分 $p_1,\dots,p_n$ を決めると、第 $j$ 列の対角より上の $j-1$ 個の成分はそれぞれ $0,1,\dots,p_j-1$ の $p_j$ 通りに選べ、ほかの成分は $0$ である。よって個数は $\prod_jp_j^{j-1}$ で、これを和にとればよい。$n=2$ では $p_2$ が $N$ の約数全体を動くので和は $\sigma(N)$ である。$\square$