17
1
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
Bubbler
Posted 2020-01-14T04:33:07.953
Reputation: 16 616
5I feel like most of the solutions are going to brute force the order rather than follow the given algorithm. Not that that's a bad thing though, and I would be interested to see if the algorithm can be implemented more precisely than that – Jo King – 2020-01-14T06:01:50.153
A harder test case:
[ [-5, 14], [16, -45] ] -> STTTTSTTSTTSTTSTTTSTTSTS– Arnauld – 2020-01-14T16:33:05.750What does your example algorithm do if after getting
c=0, you have thatbis negative, giving a negative power of T? – xnor – 2020-01-14T22:22:03.893@Noodle9 1st question: "Left-multiply $ S^{-1} $" is the procedure, the rest is the description of what that step achieves. 2nd question: There are many possible answers, including yours and mine. – Bubbler – 2020-01-14T22:55:07.690
@xnor One possible solution would be to put
-bcopies ofSSSTSTSsince $ T^{-1} $ is precisely equal to that. – Bubbler – 2020-01-14T22:56:56.190@Noodle9 Look at the worked example and see how the left column reduces from
17, 7to7, 4,4, 1, and then1, 0. Does it help? (The whole algorithm works like the Euclidean algorithm for finding GCD, just that it works on the left column of the matrix, and hitting a negative number before doing the "recursion".) – Bubbler – 2020-01-14T23:05:27.693@Bubbler I'm also confused. If you start with
a=1, c=4, don't you getq=1, giving you(1,4) -> (-3,4) -> (4,3)? I think this requires a particular ordering to count as "smaller", where you first sort byc. – xnor – 2020-01-14T23:15:34.967@xnor Yes it does, but the seeming "increase" only happens once:
1,4 (T)-> -3,4 (S)-> 4,3 (T)-> -2,3 (S)-> 3,2 (T)-> -1,2 (S)-> 2,1 (T)-> 0,1 (S)-> 1,0. In general, it may happen at most once becausea>cis guaranteed after one step. But you're right about the "smaller"; I'll edit the post to reflect the point. – Bubbler – 2020-01-14T23:19:52.197@Noodle9 I tried to clarify the algorithm in the post. Does it look better for you? – Bubbler – 2020-01-14T23:39:57.450
1@Bubbler I feel as if a dark and treacherous sky has cleared and bright happy sunshine is once again lighting up the world! Thanks :-) – Noodle9 – 2020-01-14T23:45:04.063