# 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?

-
Your algorithm (as you mention) will give false negatives. As Chris Godsil mentions, use Frobenius normal form rather than Jordan normal form to at least keep R with rational entries. If they happen to be integer, then you succeed. As Alex Bartel mentions, check the traces, since if they don't match the groups are not conjugate. Another simple necessary condition is that they be conjugate mod p. Sometimes you can reconstruct a conjugating element of GL(n,Z) by using enough primes or prime powers. Algorithms that work in general are available in GAP, I believe in the crystallography packages. –  Jack Schmidt Sep 19 '11 at 15:32

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.

-
"But if $H_i$ are not cyclic, then that's not enough." I am trying all possible combinations of an element in $S_1$ and $S_2$. Then I check whether they conjugate (step 1 in question). Then I check whether they conjugate in $GL(n,\mathbb Z)$ (step 2 in question). Then I check whether the whole subgroup conjugates with the other subgroup by the conjugacy matrix we just found (step 3 in question). –  Wox Sep 19 '11 at 13:44
Is $\otimes$ a tensor product? When you say "rational representation" you mean "integral representation"? –  Wox Sep 19 '11 at 16:26
@Alex B., how do you go from one isomorphism from $\rho_1 \otimes \mathbb{Q}$ to $\rho_2 \otimes \mathbb{Q}$ to a general one? I was thinking about Schur's lemma but then $\mathbb{Q}$ is not algebraically closed.. –  Soarer Sep 19 '11 at 17:19
@Soarer Yes, it is unfortunately a bit more complicated over $\mathbb{Q}$ than it would be over $\mathbb{C}$. In general, the endomorphism ring of an irreducible rational representation is a division algebra over $\mathbb{Q}$, this is the part of Schur's lemma that doesn't rely on the field being algebraically closed. I believe that computing the division algebra is possible algorithmically. What you have to do is compute the Wedderburn component of $\mathbb{Q}[G]$ corresponding to $\rho_1\otimes \mathbb{Q}$. –  Alex B. Sep 20 '11 at 3:37
@Wox I am not sure which place in the answer you are referring to, but I think that when i say "rational representation", I mean "rational representation". And yes, $\otimes$ is a tensor product. It simply turns the integral representation $\rho:G\rightarrow GL(n,\mathbb{Z})$ into a rational one in the obvious way: $\rho\otimes \mathbb{Q}:G\rightarrow GL(n,\mathbb{Z})\hookrightarrow GL(n,\mathbb{Q})$, although now you allow more isomorphisms (namely change of basis on the vector space by any invertible rational matrix). –  Alex B. Sep 20 '11 at 3:54

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.)

-
Where did I give the impression to be talking about Jordan normal forms of subgroups? The S's are subgroups and the Q's are elements (matrices) of these subgroups... –  Wox Sep 19 '11 at 13:43
Basically, in the first two lines. Also knowing that an element in one group is conjugate to an element in another does not imply that the groups are conjugate. But misunderstandings are easy, I was just trying to be clear about what I was doing. –  Chris Godsil Sep 19 '11 at 14:18
"... does not imply that the groups are conjugate" Indeed, hence step 3. –  Wox Sep 19 '11 at 15:10