Let $A \in \mathbb{Q}^{m \times n}$ with full row rank. Then the matrix $B$ in $A$’s Hermite Normal Form $[B \quad 0]$ is invertible.

101 Views Asked by At

My lecture introduces several new definitions and theorems as below. The part about the matrix $B$ is a passing remark that I’d like to have some more elaboration.

Definition 1. Let $A$ be a $m \times n$ rational matrix. The matrix $A$ is in Hermite Normal Form $(\mathrm{HNF})$ if $A=[B \quad 0]$ where $B$ is lower-triangular, has non-negative integers, with the diagonal entry being the unique maximum entry in each row.

Theorem 1. Any rational matrix $M$ of full row rank can be converted to $\mathrm{HNF}$ by a sequence of elementary column operations which involve:
(i) exchanging columns,
(ii) multiplying a column by $-1,$ and
(iii) adding an integral multiple of one column to another.

By this theorem, HNF $(M)=M C$ for some non-negative integral matrix $C .$ Hence, the HNF of an integral matrix will always be integral.

Corollary 1. If $M$ is integral, then $\mathrm{HNF}(\mathrm{M})$ is also integral.

Moreover, if $A$ has full row-rank, then we can assume $C$ to be a unimodular matrix.

Definition 2. A matrix $U$ is unimodular if it is integral and $\operatorname{det}(U) \in\{\pm 1\}$.

Note: $U$ is unimodular iff $U^{-1}$ is unimodular.

Theorem 2. If $M$ has full row rank, then:
(i) $\operatorname{HNF}(M)$ is unique and
(ii) there exists a unimodular matrix $U$ such that $H N F(M)=M U$

By theorem 1, $\mathrm{HNF}(A) = AU$ for some unimodular matrix $U$. The note goes on to say that $AU = [B \quad 0]$ where $B$ is invertible. Why is it so?