Hermite normal form in families

2009-11-21T03:06:55Z

How does Hermite normal form (over $Z$) vary in families? I.e. if I have an $n\times m$ matrix $M$ whose entries are integral polynomials in some integral variable $x$, how does the Hermite normal form of the integral matrix $M(p)$ (obtained by setting $x$ equal to $p$) vary as a function of $p$? What about the special case that the entries are (at most) linear in $x$?

The question is a bit open ended so answers could be of several kinds, eg: (i) how certain integer programming problems associated to $M(p)$ depend on $p$; (ii) by explaining how the answer can be expressed in a way that generalizes Ehrhart theory; (iii) by specializing to an important case that is well-understood; (iv) in some other interesting way.

I would also really appreciate a pointer to any relevant literature.

Answer by Greg Kuperberg for Hermite normal form in families

2009-11-27T06:44:55Z

Hi "DC". I think that I have worked out that the Hermite normal form is a "trichotomous quasipolynomial" in the variable $p$. If $f:\mathbb{Z} \to \mathbb{Z}$ is a function, then my definition is that $f$ is a trichotomous quasipolynomial if it is a quasipolynomial for $x \gg 0$, possibly a different quasipolynomial for $x \ll 0$, and in between finitely many unrestricted values.

I think that if $R$ is a canonically Euclidean ring — Euclidean with canonically chosen quotients and remainders — then there is a Hermite normal form for matrices over $R$. In particular, I think that $R$ does not have to be a Euclidean domain.

As a first try, let $A$ be the ring of all functions $f:\mathbb{Z} \to \mathbb{Z}$, using pointwise quotients and remainders. Hermite normal form over this ring is a model of computing Hermite normal form for any $\mathbb{Z}$ family of integer matrices. $A$ is sort-of a Euclidean ring, except it isn't Noetherian.

Let $B$ be the subring of $A$ consisting of trichotomous quasipolynomials. ~~Then I believe that $B$ is Noetherian and it is a Euclidean ring. If that is correct, then you obtain a Hermite normal form that is also a trichotomous quasipolynomial.~~

It's not correct, at least not in any obvious way. It is easy to check that $B$ is not only a subring, but is also closed under quotients with pointwise remainders. In order to compute how $b(x)$ divides into $a(x)$, you can reduce to the case in which $a(x)$ and $b(x)$ are both polynomials. Then for starters there is a quotient and a remainder in $\mathbb{Q}[x]$: $$a(x) = q(x)b(x) + r(x).$$ Since $r(x)$ has lower degree than $b(x)$, its values are smaller than those of $b(x)$ when $x \gg 0$, so that part is okay; but it may be negative and $q(x)$ may not be integral. We can fix all that by rounding $q(x)$, which creates quasipolynomial behavior; and by changing it by 1 to make $r(x)$ positive. Also since $r(x)$ might have odd degree, there may be a different quasipolynomial solution when $x \ll 0$.

The part that is either not true or far from obvious is why $B$ is Euclidean. My argument for that fell apart. However, I can still show that the Euclidean algorithm for finitely many elements $a_1,\ldots,a_n$ of $B$ terminates in a finite number of steps, and consequently that the Hermite normal form stabilizes in a finite number of steps with trichotomous quasipolynomial entries. The proof is a two-stage induction. The outer stage is the sum of the degrees of $a_1,\ldots,a_n$. If $\deg a_j < \deg a_k$ for some $j$ and $k$, then dividing $a_j$ into $a_k$ reduces the degree of $a_k$. On the other hand, suppose that the degrees are all equal. Then we can pass to a congruence class for the input $x$ in $\mathbb{Z}$ and apply a linear change of variables so that the leading coefficients are all integers. Then (in the inner induction) the Euclidean algorithm on these polynomials, for $x \gg 0$, amounts to the Euclidean algorithm on their coefficients. It is important, in this inner inductive part, to only change the variable $x$ once; don't worry if the lower-order coefficients are not integers. Eventually a $0$ is produced and the degrees once again decrease.

Alas, this is a very informal writeup, but this time I think that it works.

Hermite normal form in families - MathOverflow

Hermite normal form in families

Answer by Greg Kuperberg for Hermite normal form in families