Conjugacy in $GL(n,\mathbb Z)$

How can I determine whether $A_1,A_2\in GL(n,\mathbb Z)$ conjugate in $GL(n,\mathbb Z)$ and if they are, how can I find a $P\in GL(n,\mathbb Z)$ for which $A_2 = P^{-1}.A_1.P$ ?

In $GL(n,\mathbb Q)$ one could achieve this by checking if the Frobenius normal forms (FNF) are equal and if they are

$\quad\quad FNF_2 = FNF_1$

$\Leftrightarrow P_2^{-1}.A_2.P_2=P_1^{-1}.A_1.P_1$

$\Leftrightarrow A_2=M^{-1}.A_1.M\quad\quad\quad M=P_1.P_2^{-1}$

I found an algorithm which gives the FNF of a matrix with P a matrix of integers. Is there an way of performing subsequent elementary similarity transformations on $P_i$ (and hence also on $P_i^{-1}$) until $P_i\in GL(n,\mathbb Z)$ while also checking whether it is even possible to arrive at such a $P_i$?

-
Doesn't the Smith normal form do it? en.wikipedia.org/wiki/Smith_normal_form – José Figueroa-O'Farrill Oct 4 '11 at 14:23
See Alex Eskin's answer here: mathoverflow.net/questions/69578/… – Mark Sapir Oct 4 '11 at 14:29
@Jose: I don't think the SNF does it, it allows multiplication by different (and unrelated) invertible matrices from the left and the right, and in any case is mostly trivial for $GL(N, \mathbb{Z}),$ since recall that the determinant is $\pm 1$ in $(GL(N, \mathbb{Z}),$ and so the elementary divisors are also $\pm 1.$ – Igor Rivin Oct 4 '11 at 14:33
@Mark:Yes, Eskin's answer is the short form of Chris Godsil's question I allude to in my answer... – Igor Rivin Oct 4 '11 at 14:34
@Jose: I believe the SNF, just as the FNF, can be used for checking similarity in $GL(n,\mathbb Q)$ but not in $GL(n,\mathbb Z)$. – Wox Oct 5 '11 at 8:08

This is the conjugacy problem for ${\mathop{\rm GL}}(n,\mathbb Z)$. It was solved by Fritz Grunewald in the paper "Solution of the conjugacy problem in certain arithmetic groups" and also by R.A. Sarkisjan in "The conjugacy problem for collections of integral matrices". See MathSciNet for reviews of these papers.

-
A good reference, but Grunewald's solution is not effective (as he himself points out in arxiv.org/pdf/0801.3011 ) – Igor Rivin Oct 4 '11 at 15:26
@Sam: Your answer is misleading. Sarkisjan (and independently Grunewald-Segal) solved the much harder problem of multiple conjugacy. – Mark Sapir Oct 4 '11 at 16:51
@Mark: in the end, this is exactly what I need. But isn't that just an extension of the similarity-of-two-matrices-problem? Try all pairs of matrices, one from each set (or group in my case). If you find a pair that conjugates in $GL(n,\mathbb Z)$, you can check if the groups conjugate by the same similarity transform P. If you can't find such P or if you can't find conjugate pairs at all, then the two groups don't conjugate. Or am I missing something? – Wox Oct 5 '11 at 8:29
@Wox - Sarkisjan solves the following problem: Given two lists of matrices $\{A_i\}_{i=1}^n$ and $\{B_i\}_{i=1}^n$ is there a single matrix $P$ so that for all $i$, $P A_i P^{-1} = B_i$? This answers your question, because you can take $n = 1$. Note, however, that the $n=1$ case does not solve the $n > 1$ case. This is because the conjugating matrix $P$ need not be unique. – Sam Nead Oct 5 '11 at 12:45
Wox - also, if you are interested in infinite subgroups generated by more than one element, then checking conjugacy between a finite set of matrices is not going to be enough. – HJRW Oct 5 '11 at 14:37

See the below question (there are no answers, but the question is useful): Ideal classes and integral similarity

and also the following for a related question:

symmetric integer matrices

-