Is this true for integers matrices $A=XA’Y$

Question

Let be $A$ a matrix with integer entries. Prove that there are some matrices $X, Y$ with integer entries and having $\det (X), \det(Y)$ equal to $1$ or $-1$ such that $$A=XA’Y$$ where

$$ A’=\begin{pmatrix} a_1 & 0 & \ldots & 0\\ 0& a_2& \ldots & 0\\ \vdots & \vdots & \ddots & 0 &\\ 0& 0 &0 &a_n \end{pmatrix} $$ and $a_1$, $a_2$, ... $a_n$ are integers.

I came across this while solving some mathematics problems but only for the case when $n=2$ . Is this true for the general case? I would be extremely grateful if somebody can provide a complete proof for this problem.

Answer 1

This is the Smith normal form of a matrix over a principal ideal domain. The ring of the integers $(\mathbb Z, + , \cdot)$ is a principal ideal domain.

Wikipedia entry provides an algorithm to compute the Smith normal form of a matrix and therefore the proof you're looking for. See also this paper to get some elements on algorithms performance.