12
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Doesn't the Smith normal form do it? en.wikipedia.org/wiki/Smith_normal_form $\endgroup$
    – José Figueroa-O'Farrill
    Commented Oct 4, 2011 at 14:23
  • 1
    $\begingroup$ See Alex Eskin's answer here: mathoverflow.net/questions/69578/… $\endgroup$
    – user6976
    Commented Oct 4, 2011 at 14:29
  • 5
    $\begingroup$ @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.$ $\endgroup$
    – Igor Rivin
    Commented Oct 4, 2011 at 14:33
  • $\begingroup$ @Mark:Yes, Eskin's answer is the short form of Chris Godsil's question I allude to in my answer... $\endgroup$
    – Igor Rivin
    Commented Oct 4, 2011 at 14:34
  • $\begingroup$ @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)$. $\endgroup$
    – Wox
    Commented Oct 5, 2011 at 8:08

3 Answers 3

Reset to default
11
$\begingroup$

The Conjugacy Problem in $\operatorname{GL}(n, \mathbb{Z})$ by Eick, Hofmann and O'Brien gives an algorithm for solving this problem, which has been implemented in Magma.

Improve this answer
$\endgroup$
4
  • $\begingroup$ more practical than what? $\endgroup$
    – YCor
    Commented May 23, 2021 at 12:05
  • $\begingroup$ @YCor More practical than Grunewald's algorithm - but that makes no claims to be practical, so perhaps one should miss out the "more", $\endgroup$
    – Derek Holt
    Commented May 23, 2021 at 13:15
  • $\begingroup$ That sounds exactly like what I needed. Thanks @David Roe. $\endgroup$
    – Wox
    Commented May 24, 2021 at 12:22
  • $\begingroup$ FYI an application of that problem is determining what space group is described by a given set of symmetry operations (we're talking about the Euclidean group and crystal symmetries in the domain of crystallography). The authors are active in this domain so no coincidence. $\endgroup$
    – Wox
    Commented May 24, 2021 at 12:28
11
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ A good reference, but Grunewald's solution is not effective (as he himself points out in arxiv.org/pdf/0801.3011 ) $\endgroup$
    – Igor Rivin
    Commented Oct 4, 2011 at 15:26
  • 2
    $\begingroup$ @Sam: Your answer is misleading. Sarkisjan (and independently Grunewald-Segal) solved the much harder problem of multiple conjugacy. $\endgroup$
    – user6976
    Commented Oct 4, 2011 at 16:51
  • $\begingroup$ @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? $\endgroup$
    – Wox
    Commented Oct 5, 2011 at 8:29
  • 1
    $\begingroup$ @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. $\endgroup$
    – Sam Nead
    Commented Oct 5, 2011 at 12:45
  • $\begingroup$ 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. $\endgroup$
    – HJRW
    Commented Oct 5, 2011 at 14:37
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .