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 & -1\\1 & 0\end{pmatrix},T=\begin{pmatrix}1 & 1\\0 & 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 & b \\ c & d \end{pmatrix} \implies S^{-1}M = \begin{pmatrix} c & d \\ -a & -b \end{pmatrix}, T^{-1}M = \begin{pmatrix} a-c & b-d \\ c & 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 & b \\ c & 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 < 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 & b \\ 0 & 1 \end{pmatrix} \$, which is simply \$ T^b \$. (If \$ b < 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 & 29\\7 & 12\end{pmatrix} \$.
$$ T^{-3} M = \begin{pmatrix}-4 & -7\\7 & 12\end{pmatrix} \\ S^{-1} T^{-3} M = \begin{pmatrix}7 & 12\\4 & 7\end{pmatrix} \\ T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}-1 & -2\\4 & 7\end{pmatrix} \\ S^{-1} T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}4 & 7\\1 & 2\end{pmatrix} \\ T^{-4} S^{-1} T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}0 & -1\\1 & 2\end{pmatrix} \\ S^{-1} T^{-4} S^{-1} T^{-2} S^{-1} T^{-3} M = \begin{pmatrix}1 & 2\\0 & 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]] -> empty or SSSS or SSSTSTST or ...
[[0 -1]
[1 0]] -> S
[[1 10]
[0 1]] -> TTTTTTTTTT
[[17 29]
[ 7 12]] -> TTTSTTSTTTTSTT
[[-1 -7]
[-2 -15]] -> SSTSTTSTSSTTTTSSTTT
[ [-5, 14], [16, -45] ] -> STTTTSTTSTTSTTSTTTSTTSTS\$\endgroup\$c=0, you have thatbis negative, giving a negative power of T? \$\endgroup\$