The conjugacy classes of $\mathrm{SL}_2(\mathbb{Z})$ are well characterized (see, e.g., this question). Assuming two matrices $A, B \in \mathrm{SL}_2(\mathbb{Z})$ are conjugate, is there a way to compute their conjugacy, i.e. construct a matrix $C \in \mathrm{SL}_2(\mathbb{Z})$ such that $A C = C B$?
-
5$\begingroup$ Sure, just enumerate and try all matrices $C \in \operatorname{SL}_2(\mathbf{Z})$, and you’ll eventually find one. Perhaps you mean to ask whether there is a more efficient way than this? $\endgroup$– Carl-Fredrik Nyberg BroddaNov 11, 2021 at 1:20
-
$\begingroup$ Isn't there a more efficient way by first finding all rational solutions to $AC=CB$ (4 linear equations in 4 unknowns, solution space of dimension 2)? $\endgroup$– Paul LevyNov 11, 2021 at 8:17
-
1$\begingroup$ For efficiency, it might depend a bit on the input: is it a pair of group words in terms of generators, of a pair of matrices? In the second case the best algorithm might anyway require writing the element as such a group word. $\endgroup$– YCorNov 11, 2021 at 13:27
-
3$\begingroup$ In any case the approach writing as a word and solving the conjugacy problem in $(P)SL_2(Z)$ yields a reasonably efficient algorithm. (I'm writing $PSL_2$ since it's simpler, being a free product $C_2*C_3$, and two matrices of nonzero same trace are conjugate in $SL_2$ iff their images in $PSL_2$ are conjugate.) $\endgroup$– YCorNov 11, 2021 at 13:52
-
2$\begingroup$ As I said in my comment to the answer below, if you are looking for software to do this, then Magma has a built in function for testing two elements of ${\rm GL}(n,{\mathbb Z})$ for conjugacy (there is a paper on the method by Eick, Hoffman and O'Brien), $\endgroup$– Derek HoltNov 13, 2021 at 8:57
1 Answer
If you have access to a soft as Maple , Mathematica or Sage, you can proceed as follows. Let $A,B\in \mathrm{SL}_2$ be conjugate.
Step 1. Using a Grobner basis library, you solve the equation in $X=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ $XB-AX=0,\det(X)=1$ ($5$ equations in the $4$ unknowns $(a_{i,j}))$. Since the dimension of the algebraic set of the solutions is $1$, you group the unknowns into 2 blocks, for example $(a,b)$ and $(c,d)$. In this way , you obtain $3$ equations, the first $2$ of degree $1$ and the last one, denoted by (*), is a quadratic function of $(c,d)$ ($uc^2+vd^2+wcd+t=0$). The calculation must be instantaneous with $70$ digits; otherwise change the couples of unknowns.
Step 2. You solve (*); you can do that on line here
https://www.alpertron.com.ar/QUAD.HTM
This type of equations admits an infinity of solutions except for example if we consider the equation $x^2+y^2+1=0$ which, I think so, does not have many solutions. We obtain one or several primitive solutions and also one or several recursive solutions starting with primitive solutions. With $70$ digits, the time of calculation is $20"$.
Step 3. The problem is that the first $2$ equations have the form: $pa+qb=r(c,d),p_1a+q_1b=r_1(c,d)$; then the solution obtained in the last equation must kill the denominator $pq_1-p_1q$.
Fortunately, in all the tests I carried out, a primitive solution was suitable. I don't know if this is general or at least generic; however, if not, then we have to use the recurrence formulas.
That follows is an example:
-
1$\begingroup$ The matrices in your example appear to be images, and I could not cut and paste them. If we are discussing available software, then Magma has a fast built in function for testing elements of ${\rm GL}(n,{\mathbb Z})$ for conjugacy, and I expect GAP has something similar. $\endgroup$ Nov 13, 2021 at 8:52
-
$\begingroup$ @DerekHolt , indeed, Magma spoils the work. $\endgroup$ Nov 14, 2021 at 21:44