Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
@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

2 Answers 2

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.

share|improve this answer
    
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
1  
@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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.