Hermite Form

해당 책을 참고하여 정리한 내용입니다:

Conforti, Michele, et al. Integer programming models. Springer International Publishing, 2014.

 

우선,  Hermite Form은 다음과 같이 정의된다:

Definition : $A\in\mathbb{Q}^{m\times n}$은 Hermite normal form은 $A= [ D \; O]$ 이고 $D$는 lower triangular matrix이고 $d_{ii}>0$ for $i=1,\dots,m$이고 $d_{ij}<d_{ii}$ for 모든 $1\leq j \leq i\leq m$이다.

- Hermite normal form은 full row-rank라는 것을 확인할 수 있다.

 

이제 unimodular operation에 대해 알아보겠다:

1. Interhcanger of two columns

2. Add an integer mulitple of a column to another column

3. Multiply a column by -1

 

 

Theorem 1.12 
모든 full row rank rational matrix는 finite sequence of unimodular operation에 의해 Hermite normal form으로 변환될 수 있다.

Proof: unimoudular 변환에 의해 다음과 같은 형태를 얻었다고 하자: 
\begin{bmatrix} D & O \\ B & C \end{bmatrix}

 

 

A matrxi is said to be unimodular if it has rank $m$, it is integral, and $\text{det}(B)=0-1,1$ for every $m\times m$ sub-matrix $B$ of $A$.

Lemma 1.16 

1) $U$ is unimodular
2) $U$ and $U^{-1}$ are both integral
3) $U^{-1}$ is unimodular
4) $\forall x\in \mathbb{R}^p$, $Ux$ integral if and only if $x$ is integral
5) $U$ is obtained from the identity matrix by a sequence of unimodular operatrions