Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
My guess is that for x sufficiently large the Hermite normal form itself consists of integral polynomials. One should be able to prove this by computing the analogue of the Hermite normal form over Z[x] and then showing that it satisfies the conditions of the the usual Hermite normal form for large x. –  Qiaochu Yuan Nov 21 '09 at 3:46
    
Unfortunately, I don't think it is that simple. For example, a family of 2x2 upper triangular matrices with 2s on the diagonal and x in the upper right has "periodic" Hermite normal form over Z (the upper right entry alternates between 0 and 1). This is why I speculated about Ehrhart theory (eg. maybe the entries are eventually quasipolynomials) but this is just a guess too. I do think your guess is probably true for some "generic" families, in a sense that needs a bit more clarification . . . –  Danny Calegari Nov 21 '09 at 7:22

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
OK, I will take away your "tick" and then put it back again. Thanks. –  Danny Calegari Dec 1 '09 at 16:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.