17
\$\begingroup\$

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:

  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
\$\endgroup\$
  • 5
    \$\begingroup\$ 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 \$\endgroup\$ – Jo King Jan 14 at 6:01
  • \$\begingroup\$ A harder test case: [ [-5, 14], [16, -45] ] -> STTTTSTTSTTSTTSTTTSTTSTS \$\endgroup\$ – Arnauld Jan 14 at 16:33
  • \$\begingroup\$ What does your example algorithm do if after getting c=0, you have that b is negative, giving a negative power of T? \$\endgroup\$ – xnor Jan 14 at 22:22
  • \$\begingroup\$ @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. \$\endgroup\$ – Bubbler Jan 14 at 22:55
  • 1
    \$\begingroup\$ @Bubbler I feel as if a dark and treacherous sky has cleared and bright happy sunshine is once again lighting up the world! Thanks :-) \$\endgroup\$ – Noodle9 Jan 14 at 23:45

10 Answers 10

7
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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.

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

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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\$.

Try it online or verify a few test cases at once.

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)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

MATL, 42 38 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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 64 bytes

W∨§η⁰⊖§θ⁰¿‹⁰קθ⁰§η⁰«TUMθ⁻κ§ηλ»«S≔±θι≔ηθ≔ιη»×TΠθ¿›⁰Πθ«SSS×TST±ΠθS

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

W∨§η⁰⊖§θ⁰

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

¿‹⁰קθ⁰§η⁰

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

«TUMθ⁻κ§ηλ»

... 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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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]}[0]}

Try it online!

Use the (brute) force.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Python 3, 193 192 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!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.