# 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 & -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$$

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:

1. Assume $$\ M = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \$$.
2. Left-multiply $$\ S^{-1} \$$ until both $$\ a \$$ and $$\ c \$$ are positive.
3. Repeat the following until we reach $$\ c = 0 \$$:
1. Left-multiply $$\ T^{-q} \$$ where $$\ -c < a - qc \le 0 \$$.
2. Left-multiply $$\ S^{-1} \$$ (exactly once). Now, $$\a\$$ and $$\c\$$ are positive again, and $$\c\$$ is smaller than the original.
4. 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 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

• I 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 Jan 14 at 6:01
• A harder test case: [ [-5, 14], [16, -45] ] -> STTTTSTTSTTSTTSTTTSTTSTS – Arnauld Jan 14 at 16:33
• What does your example algorithm do if after getting c=0, you have that b is negative, giving a negative power of T? – xnor Jan 14 at 22:22
• @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 Jan 14 at 22:55
• @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 Jan 14 at 23:45

# JavaScript (ES6), 68 bytes

This is using xnor's method -- but obviously without complex numbers.

Takes the input matrix $$\\begin{pmatrix}a&b\\c&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)=>b|c|a-1|d-1?a*c>-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&b\\c&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)=>(F=(a,b,c,d,s='')=>s[i]?a+[,b,c,d]==M&&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)
) => (                     //
F = (                    // F is a recursive function taking:
a, b, c, d,            //   the current matrix as 4 distinct parameters
s = ''                 //   s = output string
) =>                     //
s[i] ?                 // if we've reached the maximum length:
a + [, b, c, d] == M //   if [a, b, c, d] matches the input matrix:
&& 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


# Python, 67 bytes

g=lambda z,w:(z/w).real>0and'T'+g(z-w,w)or z+w*w and'S'+g(w,-z)or''


Try it online!

Thanks to Bubbler for cutting a byte

Takes input as two complex numbers for the rows. The idea is simple and easy-to-see on a less-golfed version:

def f(a,b,c,d):
if (a,b,c,d)==(1,0,0,1): return ''
elif a*c+b*d>0: return 'T'+f(a-c,b-d,c,d)
else: return 'S'+f(c,d,-a,-b)


From $$\ \begin{pmatrix} a & b \\ c & d \end{pmatrix}\$$, we choose whether to apply $$\S^{-1}\$$ or $$\T^{-1}\$$ based on a simple condition: whether $$\ac+bd>0\$$. Repeating this enough times takes any matrix to the identity.

• Now that is how to use complex numbers for golfing. – Bubbler Jan 15 at 3:24
• 67 bytes. – Bubbler Jan 15 at 8:09
• @Bubbler Nice one, thanks – xnor Jan 18 at 15:57

# APL (Dyalog Extended), 47 bytesSBCS

Anonymous tacit prefix function. Gives Boolean list with 0 and 1 meaning $$\S\$$ and $$\T\$$ respectively.

{⍺≡⊃+.×/(r←⊤⍵)⊇2 2∘⍴¨(0 ¯1 1)(1 1 0):r⋄⍺∇1+⍵}∘1


Try it online! (Faster edition emulating Extended in Unicode.)

{}∘1 apply the following function with 1 and the given matrix as right and left arguments:

(0 ¯1 1)(1 1 0) the list [[0,-1,1],[1,1,0]]

2 2∘⍴¨reshape each into a 2-by-2 matrix; [[[0,-1],[1,0]],[[1,1],[0,1]]]

()⊇ select the following elements from that:

⊤ convert the right argument To base Two

r← store that in r (potential result)

+.×/ reduce using matrix multiplication (this also reduces the number of dimensions from 1 to 0)

⊃ disclose (the enclosure necessitated to reduce the number of dimensions)

⍺≡: if the left argument (the target matrix) matches that, then:

r return the result

⋄ else:

1+⍵ increment the right argument

⍺∇ call self with same left argument and new right argument

# 05AB1E, 48 44 43 40 bytes

Crossed out &nbsp;44&nbsp; is no longer 44 :)

9bS[)DðýIk©d#¼vyDÁ0T·Sǝ+y2Å€(}2ôí˜]T¾ã®è


9bS and DÁ0T·Sǝ+ could alternatively be 9Yв/т1ª/тĆS/TºS and D2ôO13Sǝ/DÁ2Å€0}+ for the same byte-count.

Brute-force approach with pretty bad performance (it times out for the last three test cases - the previous 48;44;43 bytes versions only timed out for the last test case).

Input $$\\begin{pmatrix}a&b\\c&d\end{pmatrix}\$$ as a space-delimited string of four integers "a b c d".
Output as a string of 0s and 1s, where 0 is $$\S\$$ and 1 is $$\T\$$.

Explanation:

9bS                # Push 9, convert it to binary, and then to a digit-list: [1,0,0,1]
[               # Start an infinite loop:
)              #  Wrap all lists on the stack into a list
D             #  Duplicate the current list of lists
ðý           #  Join each inner list to a string with space delimiter
Ik         #  Get the index of the input-string in this list
#  (the join is a work-around for lack of non-vectorizing index builtin)
©        #  Store it in variable ® (without popping)
d       #  Check if this index is non-negative (>= 0)
#      #  And it it is: stop the infinite loop
¼              #  Increase the counter variable by 1
v            #  Loop over each inner [a,b,c,d]-list y:
yD          #   Push the list twice
Á         #   Rotate the second one once towards the right: [a,b,c,d] → [d,a,b,c]
T·S     #   Push 10 doubled as digit list: [2,0]
0   ǝ    #   Insert a 0 at those (0-based) indices: [0,a,0,c]
+   #   Add it to the earlier list: [a+0,b+a,c+0,d+c] → [a,b+a,c,d+c]
y           #   Get the initial list [a,b,c,d] again
2Å€ }      #   Apply to every 0-based 2nd item (so at indices [0,2]):
(       #    Negate
2ô    #   Split the list into parts of size 2: [-a,b,-c,d] → [[-a,b],[-c,d]]
í˜  #   Reverse each, and flatten: → [[b,-a],[d,-c]] → [b,-a,d,-c]
]               # Close both the map and infinite loop
T¾ã            # Take the cartesian product of 10 with the counter variable
#  i.e. 3 → ["111","110","101","100","011","010","001","000"]
®è          # And index variable ® into this list
# (after which the result is output implicitly)


# MATL, 4238 32 bytes

@B"@?FT!tqh}IlhB]]Nq:"Y*]G-z}@B


The code enumerates all finite sequences that begin with S, and stops when a solution is found. It is sufficient to test sequences beginning with S because S*S*S*S equals the identity matrix (inspiration from @Adam's APL solution).

Outputs a binary sequence, where 1 corresponds to matrix S and 0 to matrix T. The produced solution is the first in lexicographical order.

Try it online!

# Jelly,  24  22 bytes

⁽¬Pb3’s2$⁺⁸ṃæ×/⁼ 0ç1#B  A monadic Link accepting the target matrix which outputs a list containing a single list of 1s ($$\S\$$) and 0s ($$\T\$$). As a full program a Jelly representation of this list is printed. Always yields a resulting equation with a leading $$\S\$$ (except for an input of $$\T\$$ itself). Note that since $$\S^4=I\$$ this is always possible. Try it online! (very slow in general). ### How? Starts with i=0 and increments i while the binary representation of i with digits $$\S\$$ (1) and $$\T\$$ (0) does not have a matrix-product equal to the input, then returns the normal binary representation (using 1s and 0s). ⁽¬Pb3’s2$⁺⁸ṃæ×/⁼ - Link 1: integer, i; target matrix, M
⁽¬P              - literal 2831
b3            - to base three    [1,0,2,1,2,2,1,2]
’           - decrement        [0,-1,1,0,1,1,0,1]
s2\$        - split into twos  [[0,-1],[1,0],[1,1],[0,1]]
⁺       - repeat that      [[[0,-1],[1,0]],[[1,1],[0,1]]]
⁸ṃ     - base-decompression of i
-     -> i in binary using digits 1=[[0,-1],[1,0]] and 0=[[1,1],[0,1]]
æ×/  - reduce by matrix-multiplication
⁼ - is equal to M?

0ç1#B            - Main Link: 2-by-2 target matrix with determinant 1, M
0                - initialise the left argument, say i, to 0
1#             - count up finding the first match under:
ç               -   last Link (1) as a dyad - i.e. f(i, M)
B            - convert to binary


# Python 3, 301 $$\\cdots\$$ 139 129 bytes

def f(a,b,c,d,l=''):
while c:
while 0>a or b<0:a,b,c,d=c,d,-a,-b;l+='S'
if c:q=-a//c;a+=q*c;b+=q*d;l+='T'*-q
return l+'T'*b


Try it online!

Saved 18 bytes thanks to Arnauld!!!

Takes the 4 matrix elements as separate numbers as input and outputs a string of 'S's and 'T's.

# Charcoal, 64 bytes

Ｗ∨§η⁰⊖§θ⁰¿‹⁰×§θ⁰§η⁰«TＵＭθ⁻κ§ηλ»«S≔±θι≔ηθ≔ιη»×TΠθ¿›⁰Πθ«SSS×TST±ΠθS


Try it online! Link is to verbose version of code. Based on the provided algorithm. Explanation:

Ｗ∨§η⁰⊖§θ⁰


Repeat while the first column is not [1, 0].

¿‹⁰×§θ⁰§η⁰


If the product of the first column is positive...

«TＵＭθ⁻κ§ηλ»


... then print a T and subtract the second row from the first row...

«S≔±θι≔ηθ≔ιη»


... otherwise print an S, and swap the rows, while negating the second row.

×TΠθ


If the product of the first row is positive then print that many Ts.

¿›⁰Πθ«


But if it is negative, then...

SSS×TST±ΠθS


... print SSS, the appropriate number of TSTs, and a final S.

# Ruby, 96 bytes

->m{z=[['',1,0,0,1]];z.find{|a,q,w,e,r|z<<[a+?S,w,-q,r,-e]<<[a+?T,q,q+w,e,e+r];m==[q,w,e,r]}}


Try it online!

Use the (brute) force.

# Python 3, 193192 191 bytes

Takes in a 2D numpy array and returns a string of S and T. Uses the algorithm in the question.

import numpy
def g(m,x=0):
if m[1,0]==0:y=m[0,1];return['T','SSSTSTS'][y<0]*abs(y)
while(m[:,0]<[1,0]).any():x+=1;m=[[0,1],[-1,0]]@m
q=-m[0,0]//m[1,0];return'S'*x+'T'*-q+g([[1,q],[0,1]]@m)
`

Try it online!