# Diagonalizing an Integer Matrix

This is, admittedly, not that interesting a question, but it's a small piece of a number theory problem I'm working on, and it's been rather frustrating. As it is technically "homework," feel free to just give suggestions, unless of course it's something really obvious.

I want to prove that for a general integer matrix, $A\in M_n(\mathbb{Z})$, there exist $U,V\in GL_n(\mathbb{Z})$ such that $UAV = \left[ \begin{array}{rrrrrr} d_1 & & & & & 0\\\ & \ddots & & & & \\\ & & d_r & & &\\\ & & & 0& &\\\ & & & & \ddots &\\\ 0 & & & & & 0 \end{array} \right]$, where $r=\mathrm{rank}A$, $d_i\in\mathbb{N}$ and $d_i\vert d_{i+1}$.

I feel like this should be just a linear algebra thing. I tried to just break it down into elements for just a 2 by 2, and it got so messy, so I'm thinking that's not the way to do it, and I'm wondering if maybe it's just a well known theorem (the issue here of course being that everything is integers, so I can't really apply stuff about diagonalizing matrices over a field). Any assistance on this would be dearly appreciated.

Thanks!

-
Note: This is exercise 2.15 from Takashi Ono's "An Introduction to Algebraic Number Theory", on page 72. –  Jon Beardsley Nov 15 '11 at 17:55
Like this? –  Guess who it is. Nov 15 '11 at 18:02
This is a well known theorem. To prove it, you can use Gaussian elimination (remember that each operation on lines or columns amounts to a multiplication by a matrix of $\text{GL}_n(\mathbb{Z})$ to the left or the right) to reduce to a diagonal matrix with $0 \le d1 \le \ldots \le d_r$. Among such matrices, pick one with minimal $d_1 \ldots d_n$. Then it only remains to show that $d_{i+1}$ is not a multiple of $d_i$, then we can produce an equivalent diagonal matrix with a lower product of non-zero diagonal elements (using Euclidian division). –  Joel Cohen Nov 15 '11 at 18:30