Check whether two subgroup of $GL(n,\mathbb Z)$ are conjugate Suppose I have two finite subgroups of $GL(n,\mathbb Z)$. Is there an algorithm
to find out whether these two belong to the same conjugacy class in
$GL(n,\mathbb Z)$? I tried by using the Jordan normal form: S1 and S2 belong to
the same conjugacy class in $GL(n,\mathbb Z)$ when we find a $Q_1 \in S_1$ and $Q_2 \in S_2$ for which
$\quad 1.$ their Jordan normal forms are the same (i.e. they conjugate)
$\quad \quad J_2 = J_1$
$\quad \quad \Leftrightarrow V_2^{-1}.Q_2.V_2 = V_1^{-1}.Q_1.V_1$
$\quad \quad \Leftrightarrow Q_2 = V_2.V_1^{-1}.Q_1.V_1.V_2^{-1} $
$\quad \quad \Leftrightarrow Q_2 = R^{-1}.Q_1.R\quad\quad  with\quad   R = V_1.V_2^{-1}$
$\quad 2.$ $R\in GL(n,\mathbb Z)$
$\quad 3.$ $S_2 = R^{-1}.S_1.R$
The problem is that the algorithm to calculate the Jordan normal form
is not very stable. Secondly, R given by the algorithm is not always
in $GL(n,\mathbb Z)$. For example:
$S_1=\lbrace id,Q_1\rbrace$
$Q1= \left[\begin{array}{rrr} 0 & -1 & 0\\
        -1  & 0 & 0\\
         0 &  0 & -1\end{array}\right]$
$S_2=\lbrace id,Q_2\rbrace$
$Q_2= \left[\begin{array}{rrr} -1 & 0 & 0\\
        0  & 0 & 1\\
         0 &  1 & 0\end{array}\right]$
Through the jordan normal form, the conjugacy matrix is found
$R= \left[\begin{array}{rrr} 1 & 0.5 & 0.5\\
        1  & -0.5 & -0.5\\
         0 &  0.5 & -0.5\end{array}\right]$
so that $S_2 = R^{-1}.S_1.R\quad$   However, R is not in $GL(n,\mathbb Z)$ but we can find an R' in $GL(n,\mathbb Z)$ for which $S_2 = R'^{-1}.S_1.R'$
$R'= \left[\begin{array}{rrr} 0 & 1 & 0\\
        0  & 0 & -1\\
         1 &  0 & 0\end{array}\right]$
Any idea on how to solve this problem, preferably without using the
Jordan normal form?
 A: The right way to do this is via representation theory. You will need to read a bit about representation theory to understand this answer
Let $H_1$, $H_2$ be the two subgroups. First, let me remark that the approach via Jordan normal forms doesn't solve the problem at all. It can tell you whether two matrices are conjugate. But if $H_i$ are not cyclic, then that's not enough. It might be that all their generators are conjugate (over $\mathbb{Q}$), but via different elements of $GL(n,\mathbb{Q})$, and the groups are not in fact conjugate.
Now, for an approach that does work over $\mathbb{Q}$. For $H_1$, $H_2$ to be conjugate, they should certainly be isomorphic. So let $\phi:H_1\rightarrow H_2$ be an isomorphism.
Theorem: $H_1$ and $H_2$ are conjugate in $GL(n,\mathbb{Q})$ if and only if there exists an automorphism $\psi$ of $H_2$ such that $\operatorname{Tr}h = \operatorname{Tr}\psi(\phi(h))$ for all $h\in H_1$, where $\operatorname{Tr}$ is the trace of the elements in $GL(n,\mathbb{Z})$.
This amazing theorem is the great achievement of representation theory of finite groups. For a proof, you can consult any of the standard references on representations theory (e.g. Isaacs, Serre, Curtis & Reiner) or my notes.
However, the question of conjugacy over $\mathbb{Z}$ is much much more subtle. Once you learn some representation theory, your question can be rephrased as classifying (or at least telling apart) isomorphism classes of $\mathbb{Z}$-free rank $n$ faithful $\mathbb{Z}[G]$-modules, where $G$ is a given finite group (abstractly isomorphic to $H_i$ in the above notation). And this, I am afraid, is completely out of reach. On the other hand, that may be a good thing, since it makes my job interesting.
Finally, on a positive note: there is a thereom due to Jordan and Zassenhaus, which says that for given $n$ and given $G$, there are only finitely many distinct isomorphism classes of $\mathbb{Z}[G]$-module of $\mathbb{Z}$-rank $n$. In other words, there are only finitely many conjugacy classes of finite subgroups of $GL(n,\mathbb{Z})$ isomorphic to $G$. I have never really seriously tried, but I believe that the proof of Jordan-Zassenhaus can be made effective in the sense that it would explicitly produce a set of representatives. But that would still not quite settle your question.
Edit: I think I was a bit too pessimistic above. You don't really need to classify the integral representations to solve this problem. For what follows, you will need to learn some representation theory. A conjugation of the type you are looking for by a matrix in $GL(n,\mathbb{Z})$ (respectively in $GL(n,\mathbb{Q})$) is the same as an isomorphism between the associated modules/representations over $\mathbb{Z}$ (respectively over $\mathbb{Q}$). Let $\rho_i:G\rightarrow GL(n,\mathbb{Z})$, $i=1,2$, be the two integral representations of $G$ with images $H_1$, $H_2$, assume that $\rho_i\otimes\mathbb{Q}$ are isomorphic. First, you need to compute the endomorphism ring of the given rational representation of $G$. Next, find one isomorphism from $\rho_1\otimes\mathbb{Q}$ to $\rho_2\otimes\mathbb{Q}$. Both of this can be done using standard techniques of representation theory. That allows you to write down a general isomorphism from $\rho_1\otimes\mathbb{Q}$ to $\rho_2\otimes\mathbb{Q}$ as a linear map in terms of bases on $\rho_1$ and $\rho_2$ and to check whether any such isomorphism is represented by a matrix with integer coefficients and with determinant 1. All this should be doable algorithmically.
A: First, subgroups do not have a Jordan normal form, only individual matrices. So I assume you are concerned with conjugate elements. 
Second, if two matrices over $\mathbb{Z}$ have the same Jordan normal form, they
are similar (conjugate) over the rationals. But this does not imply that they
are similar using an element of $GL(n,\mathbb{Z})$. As an example the matrix
$$
  A=\begin{pmatrix}1&-5\\ 3&-1\end{pmatrix}
$$
is similar to its transpose, but not by an element of $GL(2,\mathbb{Z})$. (This
is just an example, of course $A$ itself is not in $GL(2,\mathbb{Z})$.) In general it is not easy to decide if two integer matrices are similar via an element of $GL(2,\mathbb{Z})$.
You might find that the rational normal form (aka Frobenius normal form) is better
than Jordan normal form. For one thing it does not require that you have the eigenvalues. (But you will still have the same problem with rational versus integral similarity.)
