3
$\begingroup$

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

$\endgroup$
8
  • 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$ Nov 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 Levy
    Nov 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$
    – YCor
    Nov 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$
    – YCor
    Nov 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 Holt
    Nov 13, 2021 at 8:57

1 Answer 1

1
$\begingroup$

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:

enter image description here

enter image description here

enter image description here

$\endgroup$
2
  • 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$
    – Derek Holt
    Nov 13, 2021 at 8:52
  • $\begingroup$ @DerekHolt , indeed, Magma spoils the work. $\endgroup$
    – loup blanc
    Nov 14, 2021 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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