# Algorithm to generate an arbitrary matrix of special linear group $SL(2,\mathbb{Z})$

I have a given $2\times 2$ special linear matrix, for example $$m=\begin{pmatrix} 55 & 8469 \\ 1 & 154 \end{pmatrix}$$

and I would like to get the generating form of it from the s and t matrices which are these:

$$t=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\qquad\qquad\qquad s=\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$$

I don't know if exist an algoritmh for this problem or any proceedings which could help me.

• Row reduce and use the Euclidean algorithm. – Qiaochu Yuan May 1 '15 at 10:10
• I know the Euclidean algorithm, but can you give me more support to start? Thank you! – Alíz May 1 '15 at 10:14
• So that you can also use column reduction, it is useful to note that $u = \left(\begin{array}{cc}1&0\\1&1\end{array}\right) = st^{-1}s^{-1}$. – Derek Holt May 1 '15 at 10:48

Disclaimer: The ideas for the following answer come from a pdf I found by Keith Conrad at the University of Connecticut.

The idea of the following is to deal with a simple case (one of the entries is $0$) and then reduce to this simple case using the Euclidean algorithm.

Let our arbitrary matrix $m$ be written as $$m=\left(\begin{matrix}a&b\\c&d\end{matrix}\right)$$

Simple Case: First suppose that $c=0$.

As $\det(m)=1$ this means we must have $a=d=\pm1$. If $a=d=1$ we can directly write $m=t^b$, while if $a=d=-1$ we can write $m=s^2t^{-b}$ (note that $s^2=-I$).

General Case: Now suppose $|c|>0$.

We describe an iterative process to reduce this matrix to the simple case. First suppose that $|a|<|c|$. Then let $m'=sm$ (so now $m'$ has $|a'|\ge|c'|$ since we have just switched them up to a sign). Second suppose that $|a|\ge |c|$, and use the Euclidean algorithm to write $a=cq+r$ with $0\le r<c$. Now take $m'=t^{-q}m$. This matrix has $a-cq=r<c$ as the top left entry and $c$ as the bottom left entry.

Applying this process eventually leads to $c=0$ (using the switching operation after the reducing operation always leads to a $c'$ of strictly lesser magnitude than $c$), and from there we fall into our simple case.

• Thank you for your answer! :) – Alíz May 1 '15 at 10:58
• I tried this algorithm on an arbitrary matrix, and it works for me. – Alíz May 1 '15 at 12:21

The key is that the second matrix rotates by 90 degrees. $$\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right)^a.\left( \begin{array}{cc} 0 & -1 \\ 1 & 0 \\ \end{array} \right).\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right)^b$$

Gives the result $$\left( \begin{array}{cc} a & a d-1 \\ 1 & d \\ \end{array} \right)$$

• In the product you have a exponent $b$, but in the result you use $d$, you should decide for one. – Viktor Glombik May 20 '18 at 13:47

This rather small example can also be done by hand without any algorithms.

Note that $$\begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} a & a+b \\ c & c+d \end{pmatrix}$$ While $S$ switches the columns and puts a minus sign in.

Then by guesstimating powers, we reduce the size of scalars quite efficiently.

For example: $$\begin{pmatrix} 55 & 8469 \\ 1 & 154 \end{pmatrix} \begin{pmatrix} 1 & -153 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 55 & 54 \\ 1 & 1 \end{pmatrix}.$$ Multiply by $S^3=S^{-1}$:

$$\begin{pmatrix} 55 & 54 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}= \begin{pmatrix} -54 & 55 \\ -1 & 1 \end{pmatrix}$$ This look quite close to a power of $T$. So mulitply it by $T$: $$\begin{pmatrix} -54 & 55 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}= \begin{pmatrix} -54 & 1 \\ -1 & 0 \end{pmatrix}$$ This we recognize as $T^{54}S$. Working backwards, this all means that $$MT^{-153}ST=T^{54}S.$$ Hence $M=T^{54}ST^{-1}S^{-1}T^{153}$. (this might be simplified though)