Decomposition of a matrix in \$ SL_2(\mathbb{Z}) \$ Background

The special linear group \$ SL_2(\mathbb{Z}) \$ is a multiplicative group of \$ 2 \times 2 \$ matrices whose elements are integers and determinant is 1.

It is known that every member of \$ SL_2(\mathbb{Z}) \$ is a product of some sequence of the following two matrices \$ S \$ and \$ T \$ (reference pdf):

$$
S=\begin{pmatrix}0 &amp; -1\\1 &amp; 0\end{pmatrix},T=\begin{pmatrix}1 &amp; 1\\0 &amp; 1\end{pmatrix}
$$

Note that \$ S^{-1} \$ and \$ T^{-1} \$ can also be expressed as a product of \$ S \$ and \$ T \$:

$$
S^{-1} = S^3, T^{-1} = S^3 \cdot T \cdot S \cdot T \cdot S
$$

Task

Given a \$ 2 \times 2 \$ integer matrix whose determinant is 1, express it as the product of a sequence of \$ S \$ and \$ T \$.

Note that there are infinitely many possible answers for any valid input. Your code needs to just output one answer for a valid input.

Example algorithm

Here is a sample algorithm to find a decomposition; you may use different algorithms to solve the task.

First, note that

$$
M = \begin{pmatrix} a &amp; b \\ c &amp; d \end{pmatrix} \implies
S^{-1}M = \begin{pmatrix} c &amp; d \\ -a &amp; -b \end{pmatrix},
T^{-1}M = \begin{pmatrix} a-c &amp; b-d \\ c &amp; d \end{pmatrix}
$$

Using these two operations, we can use Euclidean-like algorithm to reduce the given matrix down to \$ I \$, and then construct the chain backwards:


Assume \$ M = \begin{pmatrix} a &amp; b \\ c &amp; d \end{pmatrix} \$.
Left-multiply \$ S^{-1} \$ until both \$ a \$ and \$ c \$ are positive.
Repeat the following until we reach \$ c = 0 \$:


Left-multiply \$ T^{-q} \$ where \$ -c &lt; a - qc \le 0 \$.
Left-multiply \$ S^{-1} \$ (exactly once). Now, \$a\$ and \$c\$ are positive again, and \$c\$ is smaller than the original.

Then the result is \$ \begin{pmatrix} 1 &amp; b \\ 0 &amp; 1 \end{pmatrix} \$, which is simply \$ T^b \$. (If \$ b &lt; 0 \$, we can use \$ (SSSTSTS)^{-b} \$ instead.) Now invert all the left-multiplications to get the representation for the original matrix.


Here is an example for \$ M = \begin{pmatrix}17 &amp; 29\\7 &amp; 12\end{pmatrix} \$.

$$
T^{-3} M = \begin{pmatrix}-4 &amp; -7\\7 &amp; 12\end{pmatrix}
\\ S^{-1} T^{-3} M = \begin{pmatrix}7 &amp; 12\\4 &amp; 7\end{pmatrix}
\\ T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}-1 &amp; -2\\4 &amp; 7\end{pmatrix}
\\ S^{-1} T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}4 &amp; 7\\1 &amp; 2\end{pmatrix}
\\ T^{-4} S^{-1} T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}0 &amp; -1\\1 &amp; 2\end{pmatrix}
\\ S^{-1} T^{-4} S^{-1} T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}1 &amp; 2\\0 &amp; 1\end{pmatrix} = T^2
\\ M = T^3 S T^2 S T^4 S T^2
$$

Input and output

You can take the input matrix in any suitable way, e.g. a matrix, a 4-element vector, two complex numbers, etc. You can assume that the input is always valid, i.e. the four elements are integers and the determinant is 1.

The output is a sequence of two distinct values (or objects) that represent \$ S \$ and \$ T \$ respectively. All of the following are accepted (using an example output \$ STTS \$):

"STTS"  # string
"0110"  # digit string
[0, 1, 1, 0]  # array of 0s and 1s
['S', 'T', 'T', 'S']  # array of characters
[(0,-1,1,0), (1,1,0,1), (1,1,0,1), (0,-1,1,0)]  # array of tuples


Also, by definition of empty product, an empty sequence (e.g. "" or []) is a valid answer when the input is \$ I \$.

Scoring and winning criterion

Standard code-golf rules apply. Shortest code in bytes wins.

Example I/O

Note that every valid input has infinitely many correct answers, so your code's output may differ from the sample outputs shown here.

[[1 0]
 [0 1]] -&gt; empty or SSSS or SSSTSTST or ...

[[0 -1]
 [1  0]] -&gt; S

[[1 10]
 [0  1]] -&gt; TTTTTTTTTT

[[17 29]
 [ 7 12]] -&gt; TTTSTTSTTTTSTT

[[-1  -7]
 [-2 -15]] -&gt; SSTSTTSTSSTTTTSSTTT
JavaScript (ES6), 68 bytes
This is using xnor's method -- but obviously without complex numbers.
Takes the input matrix \$\begin{pmatrix}a&amp;b\\c&amp;d\end{pmatrix}\$ as 4 distinct parameters a,b,c,d.
Returns a string of digits (\$0\$ for \$S\$, \$1\$ for \$T\$).

f=(a,b,c,d)=&gt;b|c|a-1|d-1?a*c&gt;-b*d?1+f(a-c,b-d,c,d):0+f(c,d,-a,-b):''

Try it online!

JavaScript (ES6),  114 110  108 bytes
Takes the input matrix \$\begin{pmatrix}a&amp;b\\c&amp;d\end{pmatrix}\$ as a 4-element vector [a,b,c,d].
Returns a string of digits (\$0\$ for \$S\$, \$1\$ for \$T\$).
Brute forces a solution, which is guaranteed to be as short as possible, except for the identity matrix.

f=(M,i=0)=&gt;(F=(a,b,c,d,s='')=&gt;s[i]?a+[,b,c,d]==M&amp;&amp;s:F(a,a+b,c,c+d,s+1)||F(b,-a,d,-c,s+0))(1,0,0,1)||f(M,i+1)

Try it online!
Commented
f = (                      // f = wrapper function taking:
  M,                       //   M[] = input vector
  i = 0                    //   i   = maximum number of iterations (-1)
) =&gt; (                     //
  F = (                    // F is a recursive function taking:
    a, b, c, d,            //   the current matrix as 4 distinct parameters
    s = ''                 //   s = output string
  ) =&gt;                     //
    s[i] ?                 // if we've reached the maximum length:
      a + [, b, c, d] == M //   if [a, b, c, d] matches the input matrix:
        &amp;&amp; s               //     return s
    :                      // else:
      F(                   //   try a first recursive call
        a,                 //     where the matrix is multiplied by T
        a + b,             //     [ a b ]   [ 1 1 ]   [ a a+b ]
        c,                 //     [ c d ] x [ 0 1 ] = [ c c+d ]
        c + d,             //
        s + 1              //     append '1' to s
      ) ||                 //
      F(                   //   try a second recursive call
        b,                 //     where the matrix is multiplied by S
        -a,                //     [ a b ]   [ 0 -1 ]   [ b -a ]
        d,                 //     [ c d ] x [ 1  0 ] = [ d -c ]
        -c,                //
        s + 0              //     append '0' to s
      )                    //
)(1, 0, 0, 1)              // initial call to F with the identity matrix
|| f(M, i + 1)             // if it fails, try again with i + 1