Vector Reachability Problem in SL(2, Z) ∗Igor Potapov1 and Pavel Semukhin2
1

Department of Computer Science, University of Liverpool, United Kingdom
potapov@liverpool.ac.uk
Department of Computer Science, University of Liverpool, United Kingdom
semukhin@liverpool.ac.uk

2

Abstract
The decision problems on matrices were intensively studied for many decades as matrix products
play an essential role in the representation of various computational processes. However, many
computational problems for matrix semigroups are inherently difficult to solve even for problems
in low dimensions and most matrix semigroup problems become undecidable in general startingfrom dimension three or four.
This paper solves two open problems about the decidability of the vector reachability problem
over a finitely generated semigroup of matrices from SL(2, Z) and the point to point reachability(over rational numbers) for fractional linear transformations, where associated matrices are fromSL(2, Z). The approach to solving reachability problems is based on the characterization ofreachability paths between points which is followed by the translation of numerical problems on
matrices into computational and combinatorial problems on words and formal languages. We also
give a geometric interpretation of reachability paths and extend the decidability results to matrix
products represented by arbitrary labelled directed graphs. Finally, we will use this technique toprove that a special case of the scalar reachability problem is decidable.
1998 ACM Subject Classification F.2.1 Numerical Algorithms and Problems, F.1.1 Models ofComputation
Keywords and phrases Matrix Semigroup, Vector Reachability Problem, Special Linear Group,
Linear Fractional Transformation, Automata and Formal Languages
Digital Object Identifier 10.4230/LIPIcs.MFCS.2016.84

1

Introduction

Decision problems on matrices were intensively studied from 1947 when A. Markov showed
the connection between classical computations and problems for matrix semigroups [24].
Moreover matrix products play an essential role in the representation of various computational processes, i.e., linear recurrent sequences [18, 27, 28], arithmetic circuits [14], hybrid
and dynamical systems [26, 3], probabilistic and quantum automata [7], stochastic games,
broadcast protocols [13], optical systems, etc. New algorithms for solving reachability problems in matrix semigroups can be incorporated into software verification tools and used foranalysis of mathematical models in physics, chemistry, biology, ecology, and economics.
However, many computational problems for matrix semigroups are inherently difficult
to solve even when the problems are considered in dimension two, and most of these problems become undecidable in general starting from dimension three or four. Examples ofsuch problems are the Membership problem (including the special cases of the Mortality∗

This work was supported by EPSRC grant “Reachability problems for words, matrices and maps”(EP/M00077X/1).

© Igor Potapov and Pavel Semukhin;licensed under Creative Commons License CC-BY
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016).
Editors: Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier; Article No. 84; pp. 84:1–84:14
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

84:2

Vector Reachability Problem in SL(2, Z)

and Identity problems), vector reachability, scalar reachability, freeness problem and theemptiness problem of matrix semigroups intersection [6]. All above problems are tightly
connected, including three central problems:
The membership problem: Let S = hGi be a semigroup generated by a finite set
G of n × n matrices. Determine whether a given matrix M belongs to S, that is, determine whether there exists a sequence of matrices M1 , M2 , . . . , Mk in G such that
M = M 1 · M2 · . . . · Mk
The vector reachability problem: Let x and y be two vectors and S be a given
finitely generated semigroup of n × n matrices. Determine whether there is a matrix
M ∈ S such that M x = y.
The scalar reachability problem: Let x and y be two vectors, λ be a scalar, and S
be a given finitely generated semigroup of n × n matrices. Determine whether there is amatrix M ∈ S such that x> M y = λ.
The vector reachability problem can be seen as a parameterized version of the membership problem, where some elements of a matrix M are either independent variables orvariables linked by some equations. In contrast to the original membership problem, where
all values of M are constants, in vector reachability we may have an infinite set of matricesthat can transform a vector x to y. Thus the decidability results for the membership cannot
be directly applied to the vector reachability problem.
The scalar reachability can be viewed as a vector to hyperplane reachability problem.
Indeed, we can rewrite the equation x> M y = λ as a system of two equations: M y = z andx> z = λ. So, the question becomes if there is a matrix M ∈ S that maps a given vector y toa vector z that lies on a hyperplane x> z = λ. Because there are infinitely many vectors ona hyperplane, decidability of the scalar reachability problem does not follow directly fromthe decidability of the vector reachability problem.
Most of the problems such as membership, vector reachability and freeness are undecidable for 3 × 3 integer matrices. The undecidability proofs in matrix semigroups are mainly
based on various techniques and methods of embedding universal computations into threeand four dimensional matrices and their products. The case of dimension two is the mostintriguing one since there is some evidence that if these problems are undecidable, then thiscannot be proved using a construction similar to the one used for dimensions 3 and 4. In
particular, there is no injective semigroup morphism from pairs of words over any finite
alphabet (with at least two elements) into complex 2 × 2 matrices [8], which means that thecoding of independent pairs of words in 2 × 2 complex matrices is impossible and the exact
encoding of the Post Correspondence Problem or a computation of a Turing Machine cannot
be used directly for proving undecidability in 2 × 2 matrix semigroups over Z, Q or C. The
only undecidability result in dimension two for the vector reachability and the membershipproblems has been shown in the case of 2 × 2 matrices over quaternions [4].
The main hypothesis is that problems for 2 × 2 matrix semigroups over integers, rationals
or complex numbers could be decidable, but not much is known about the status of these
problems. Recently, there was some progress on the Membership problem, which was shown
to be decidable in SL(2, Z), and the Identity problem, which was shown to be decidable
in Z2×2 [11]. Later the decidability of the Freeness problem (that is, to decide whether
each element can be expressed uniquely as a product of generating matrices) was shown forSL(2, Z) [9]. On the other hand, the Mortality, Identity and vector reachability problems
were shown to be at least NP-hard for SL(2, Z) in [5, 6], but for the modular group themembership was shown to be decidable in polynomial time by Gurevich and Schupp [16].

I. Potapov and P. Semukhin

84:3

The algorithmic properties of SL(2, Z) are important in the context of many fundamental
problems in hyperbolic geometry [34, 10, 12], dynamical systems [29], Lorenz/modular knots[22], braid groups [30], particle physics, high energy physics [33], M/string theories [15], ray
tracing analysis, music theory [25] and can lead to further decidability results in Z2×2 using
matrix presentation in the Smith normal form.
This paper solves two open problems about the decidability of the vector reachability
problem for finitely generated semigroups of matrices from SL(2, Z) and the point to point
reachability (over rational numbers) for fractional linear transformations fM (x) = ax+b
cx+d ,

a bwhere the associated matrix M =belongs to SL(2, Z). The approach to solving thesec dreachability problems for 2 × 2 matrix semigroups is based on the analysis of reachability
paths between vectors or points. This analysis is then used to translate the numericalreachability problems into computational problems on words and regular languages. We alsopresent several extensions of our main results, give a geometric interpretation of reachability
paths, and use this technique to solve a special case of the scalar reachability problem.
The decidability proof of the vector reachability problem in dimension two presented inthis paper is the first nontrivial new result for solving vector reachability problems since 1996
when it was shown that the problem is decidable for any commutative matrix semigroupin any dimension [1] and for a special case of non-commuting matrices [20]. On the other
hand, in the general case of non-commuting matrices the problem is known to be undecidable
already for integer matrices in dimension three [17].

2Preliminaries

The integers and rationals are denoted by Z and Q, respectively, and SL(2, Z) is a group of
2 × 2 integer matrices with determinant 1. The notation a | b means that a divides b, anda - b means that a does not divide b, when a and b are integer numbers.
a b
I Definition 1. With each matrix M =∈ SL(2, Z) we associate a fractional linearc dmap (also called Möbius transformation) fM : Q → Q defined as fM (x) = ax+b
cx+d . Thisdefinition can be extended to f : Q∪{∞} → Q∪{∞} in a natural way by setting fM (∞) = acif c 6= 0, fM (∞) = ∞ if c = 0, and fM (x) = ∞ if cx + d = 0.
Note that we have fM1 ◦ fM2 = fM1 M2 for any matrices M1 and M2 .
Let M1 , . . . , Mn be a finite collection of matrices. Then hM1 , . . . , Mn i denotes the multiplicative semigroup (including the identity matrix) generated by M1 , . . . , Mn .
I Definition 2. The vector reachability problem in SL(2, Z) is defined as follows: Given two
vectors x and y with integer coefficients and a finite collection of matrices M1 , . . . , Mn fromSL(2, Z), decide whether there exists a matrix M ∈ hM1 , . . . , Mn i such that M x = y.
I Definition 3. The reachability problem by fractional linear transformations in SL(2, Z) isdefined as follows: Given two rational numbers x and y and a finite collection of matrices
M1 , . . . , Mn from SL(2, Z), decide whether there exists a matrix M ∈ hM1 , . . . , Mn i suchthat fM (x) = y.
The main result of our paper is that the vector reachability problem and the reachability
problem by fractional linear transformations for SL(2, Z) are decidable (Theorem 14). Bothproofs follow the same pattern. We will use the fact that any matrix M from SL(2, Z) can

M FC S 2 0 1 6

84:4

Vector Reachability Problem in SL(2, Z)




0 −1
0 −1
and R =
. So we can represent
1 0
1 1
any M ∈ SL(2, Z) by a word w in the alphabet Σ = {S, R}.
The main idea of the proof is to show that the solution set of the equation M x = y has
 
t

1 1
the form B
C : t ∈ Z , where B and C are some matrices from SL(2, Z) that can
0 1
be computed in PTIME from x, y (Theorem 8). Similarly, the solution set of the equationfM (x) = y can be presented as a union of two sets of such form (Theorem 10). Aftertranslating matrices into words, these sets become regular languages. On the other hand,
the language that corresponds to the semigroup hM1 , . . . , Mn i is also regular. Indeed, if Mi
corresponds to the word wi , then the semigroup hM1 , . . . , Mn i translates into the language∗(w1 + · · · + wn ) . The last step of the proof is to show that the emptiness problem of theintersection of two such languages is decidable (Proposition 13). 

 
a b
x1
Here is a more detailed description of our proofs. Let M =
, x =
and
c d
x2
 
y
y = 1 . To show that the equation M x = y defines a regular language we must solve they2following system of three equations in four unknown variables:

be expressed as product of matrices S =x1 a + x2 b = y1

x1 c + x2 d = y2

ad − bc = 1

Choosing b as a free parameter, we can reduce it to the following system of linear congruence equations:x2 b ≡ y1 (mod x1 )y2 b ≡ −x1 (mod y1 )x2 y2 b ≡ y1 y2 − x1 x2 (mod x1 y1 )It can be shown that the above system either has no solutions or it has a solution of theform b = b1 t + b2 , where t ∈ Z, and hence all coefficients of the matrix M are linear
functions of t. In Proposition 7 we will show that such matrices can be written in the formt
1 k
C, where B, C are some matrices from SL(2, Z), k is a fixed integer number
M =B
0 1
and t ∈ Z is a free parameter. After that it is not hard to see that such solution translates
into a regular language.
We will use a similar approach to prove that the equation fM (x) = y also defines aregular language. In fact, we will do it by showing that the solution set of fM (x) = y isequal to the union of the solution sets of the equations M x = y and M x = −y for suitable
vectors x and y.
The final step is to show that there is an algorithm that decides whether the intersectionof two regular subsets of SL(2, Z) is empty or not. Our idea relies on the fact that theintersection of two regular languages is regular, and that the emptiness problem for regular
languages is decidable. The problem here is that we cannot apply these facts directly because∗
for each matrix M ∈ SL(2, Z) there are infinitely many words w ∈ {S, R} that correspondto M , and only some of them may appear in the given language. However there is only one
reduced word that corresponds to M , that is, the word that does not have a substring of
the form SS or RRR. So, our solution is to take any automaton A and turn it into a newautomaton Ae that accepts the same language as A plus all reduced words w that correspondto non-reduced words w0 accepted by A.
The construction of the automaton Ae was inspired by a similar construction from [11].
Note that in SL(2, Z) we have an equality S 2 = R3 = −I. Thus to construct Ae we add to A
a new ε-transition from a state q1 to a state q2 if there is a run of A from q1 to q2 labelled

I. Potapov and P. Semukhin

84:5

by SS or RRR. We will apply this procedure iteratively until no new ε-transitions can be
added. However we need to keep track of sign changes when we add new ε-transitions. To
achieve this we will use signed automata, which are slight modifications of the usual finite
automata but they take into account such sign changes.
Now to solve the emptiness problem for the intersection of two regular languages L1and L2 , we take the signed automata A1 and A2 that accept L1 and L2 , respectively, andconstruct new automata Ae1 and Ae2 as described above. After that we can check whether
L(Ae1 ) ∩ L(Ae2 ) 6= ∅.
In the Section 4 we will show how to extend these decidability results to arbitrary regularsubsets of SL(2, Z), i.e., subsets that are defined by finite automata. Using this technique
we will show how to algorithmically solve the equation M1x1 · · · Mkxk x = N1y1 · · · Nlyl y, wherex, y are given vectors from Z×Z, the matrices M1 , . . . , Mk and N1 , . . . , Nl are from SL(2, Z),
and x1 , . . . , xk and y1 , . . . , yl are unknown non-negative integers. Furthermore, we will show
how to apply this method to prove that a special case of the scalar reachability problem isdecidable.
All missing proofs can be found in the extended version of this paper, which is available
online on arXiv.org [31].

3

Main results

The characterization of the solution set of the equation M x = y given in Theorem 8 will
follow from Propositions 5 and 7. First, we prove one simple lemma which we will use several
times in our arguments.
 
 
x1
y
I Lemma 4. Let x =and y = 1 be vectors from Z × Z and M be a matrix fromx2y2
SL(2, Z) such that M x = y. Then gcd(x1 , x2 ) = gcd(y1 , y2 ).
a bProof. Take any k ∈ Z such that k | x1 , x2 and let M =. Then from M x = y wec dhave y1 = ax1 + bx2 and y2 = cx1 + dx2 . Thus k | y1 , y2 . Now since M ∈ SL(2, Z), M −1 isalso in SL(2, Z), and M x = y is equivalent to M −1 y = x. So, if k ∈ Z is any number suchthat k | y1 , y2 , then k | x1 , x2 . Therefore, gcd(x1 , x2 ) = gcd(y1 , y2 ).
J
 
 
x
y
I Proposition 5. Let x = 1 and y = 1 be two vectors from Z × Z, such that x is
x2
y2
not equal to the zero vector 0, and consider the matrix equation M x = y, where M is an
unknown matrix from SL(2, Z). Then either this equation does not have a solution or all
its solutions are given by M = tA1 + A2 , where t is any integer number, A1 , A2 are somematrices from Z2×2 such that A1 is a nonzero matrix. Moreover, there is a polynomial timealgorithm that determines whether such an equation has a solution and if so, finds it.
Proof. See Section A of the Appendix in [31].

J

For the next proposition we will need the following theorem about the Smith normal
form of a matrix.
2×2
I Theorem 6 (Smith normal form [19]).For any nonzero matrix A ∈ Z , there are matricest0
B, C from SL(2, Z) such that A = B 1
C for some t1 , t2 ∈ Z such that t1 6= 0 and
0 t2
t1 | t2 . Moreover, B, C, t1 , t2 can be computed in polynomial time.

M FC S 2 0 1 6

84:6

Vector Reachability Problem in SL(2, Z)

I Proposition 7. Let A1 and A2 be matrices from Z2×2 such that A1 is a nonzero matrix
and, for every t ∈ Z, we have tA1 + A2 ∈ SL(2, Z). Then there are matrices B and C fromSL(2, Z) and k ∈ Z such thatkt
tA1 + AC for every t ∈ Z,
 2 = BT
1 1where T =∈ SL(2, Z). Moreover, B, C, and k can be computed in polynomial time.
0 1




a1 b1
a2 b2
Proof. Let A1 =and A2 =. By the assumption, for every t ∈ Z,
c1 d1
c2 d2
a1 t + a2 b1 t + b2
= 1. That is (a1 t + a2 )(d1 t + d2 ) − (b1 t + b2 )(c1 t + c2 ) = 1 or
c1 t + c2 d 1 t + d 2(a1 d1 − b1 c1 )t2 + (a1 d2 + a2 d1 − b1 c2 − b2 c1 )t + a2 d2 − b2 c2 = 1 for all t ∈ Z.
Therefore, a1 d1 − b1 c1 = 0, a1 d2 + a2 d1 − b1 c2 − b2 c1 = 0, and a2 d2 − b2 c2 = 1. In particular,det(A1 ) = 0 and det(A2 ) = 1.

k 0
By Theorem 6, there are matrices F, G ∈ SL(2, Z) such that A1 = F
G for some
0 l
k, l ∈ Z such that k | l. Since det(A1 ) = 0 we have that kl = 0. However if k = 0 and l = 0,then A1 is equal to the zero matrix, contrary to the assumption. Hence we must have thatk 6= 0 and l = 0.

kt + a b−1−1
Now F (tA1 + A2 )G =, for some a, b, c, d ∈ Z. Note that since det(F ) =cdkt + a b= dkt + ad − bc = 1 for every t ∈ Z.
det(G) = det(tA1 + A2 ) = 1, we havecdHence dk = 0 and so d = 0. Substituting d = 0 in the above equation, we obtain bc = −1.
Since b and c are integers, there are only two possibilities: b = 1, c = −1, or b= −1, c = 1.
kt + a ∓1
So the above matrix actually looks like F −1 (tA1 + A2 )G−1 =. Therefore,
±1
0


0 ∓1
T −c(kt+a) F −1 (tA1 + A2 )G−1 = D, where c = ±1 and D =∈ SL(2, Z). Hence±1 0
tA1 + A2 = F T (ck)t T ca DG. Note that F and T ca DG are in SL(2, Z). This completes theproof. The bound on complexity follows from the fact that F and G can be computed in
PTIME by Theorem 6.
J
As a corollary of Propositions 5 and 7 we obtain the following theorem.
 
 
x
y
I Theorem 8. Let x = 1 and y = 1 be vectors from Z × Z such that x 6= 0, andx2y2
consider the matrix equation M x = y, where M is an unknown matrix from SL(2, Z). Theneither this equation does not have a solution or all its solutions are given by the following
t
1 kformula M = B
C, where t ∈ Z.
0 1
In the above expression B and C are some matrices from SL(2, Z), and k is an integer
number. Moreover, there is a polynomial time algorithm that determines whether such an
equation has a solution and if so, finds the suitable matrices B, C and the integer k.
In Section 4 we will give a geometric interpretation of reachability paths (Figure 1 and
Proposition 16), using which we can prove the following corollary.1 The proof itself can be
1

Even though we use Corollary 9 in the proofs of Theorem 10 and Proposition 18, it is not essential
there for proving decidability. Namely, all references to Corollary 9 in these proofs can be replaced byreferences to Theorem 8, at the same time replacing T with T k where appropriate.

I. Potapov and P. Semukhin

84:7

found in Section D of the Appendix in [31].
I Corollary 9. The value of the parameter k in Theorem 8 is equal to 1.
Theorem 8 provides us with a characterization of the matrices M ∈ SL(2, Z) that map
vector x to vector y. This characterization will be used later to prove the decidabilityof the vector reachability problem. We now give a similar characterization of the matrices
M ∈ SL(2, Z) for which the fractional linear transformation fM maps a number x to number
y. In fact, we will do this by reducing the problem to finding the solutions of the equation
M x = y which we discussed above.
I Theorem 10. Let x and y be rational numbers and let F(x, y) be the following set of
matrices from SL(2, Z):
F(x, y) = {M ∈ SL(2, Z) : fM (x) = y}.
Then F(x, y) = F1 (x, y) ∪ F2 (x, y), where each Fi (x, y) is either empty or has the form
Fi (x, y) = {Bi T t Ci : t ∈ Z},
where Bi and Ci are some matrices from SL(2, Z). Moreover, there is a polynomial timealgorithm that determines whether each Fi (x, y) is empty or not and in the latter case finds
corresponding matrices Bi and Ci .
Proof. Let us write the numbers x and y as x = xx21 and y = yy12 , where we assume thata b
gcd(x1 , x2 ) = gcd(y1 , y2 ) = 1. Consider the equation fM (x) = y, where M =
is an
c d
unknown matrix from SL(2, Z). We can rewrite it asa xx21 + b
c xx21 + d

=

y1
y2

or

ax1 + bx2
y1=.
cx1 + dx2
y2

(1)

 
 
 
x1
y1
z1
, y =
, and z =, where z is the vector withx2
y2
z2
coordinates z1 = ax1 + bx2 and z2 = cx1 + dx2 . So we have that z = M x. In this notation
Equation (1) is equivalent to the fact that vector z = M x belongs to the set {ky : k ∈ Z}.
Recall that gcd(x1 , x2 ) = 1 and hence, by Lemma 4, we also have that gcd(z1 , z2 ) = 1.
Thus if z = ky for some k ∈ Z, then we must have that k = ±1. In other words, we showedthat Equation (1) is equivalent to two matrix equations: M x = y and M x = −y. So wehave that F(x, y) = F1 (x, y) ∪ F2 (x, y), whereF1 (x, y) = {M ∈ SL(2, Z) : M x = y} and F2 (x, y) = {M ∈ SL(2, Z) : M x = −y}.
Note that x 6= 0 because x2 6= 0. Hence by Theorem 8 and Corollary 9, each Fi (x, y) iseither empty or has the form Fi (x, y) = {Bi T t Ci : t ∈ Z} for some Bi and Ci from SL(2, Z)
which can be computed in polynomial time.
J
Consider the vectors x =Now we will use signed automata to prove that the emptiness problem for the intersectionof two regular subsets of SL(2, Z) is decidable.
Consider an alphabet Σ = {S, R} consisting of two symbols S andR anddefine the
0 −1
0 −1
mapping ϕ : Σ → SL(2, Z) as follows: ϕ(S) =and ϕ(R) =. We can
1 0
1 1
extend this mapping to the morphism ϕ : Σ∗ → SL(2, Z) in a natural way. The matrices
ϕ(S) and ϕ(R) are in fact generators of SL(2, Z), so ϕ is surjective. We call a word w ∈ Σ∗
reduced if it does not have substrings of the form SS or RRR. In our proof we will makeuse of the following well-known fact.

M FC S 2 0 1 6

84:8

Vector Reachability Problem in SL(2, Z)

I Theorem 11 ([21, 23, 32]). For every M ∈ SL(2, Z), there exists a unique reduced wordw ∈ Σ∗ such that either M = ϕ(w) or M = −ϕ(w).
I Definition 12. A signed automaton A = (Σ, Q, I, ∆, F + , F − ) is a (non-deterministic)
finite automaton whose final states are divided into two (not necessarily disjoint) subsets
F + and F − .
A signed language accepted by a signed automaton A is a pair L(A) = (L(A)+ , L(A)− ),where L(A)+ and L(A)− consists of the words w ∈ Σ∗ for which there is a run of A that
ends in the set F + or F − , respectively. Note that we do not assume that L(A)+ and L(A)−are disjoint.
Let L = (L+ , L− ) be a signed language, then we define a regular subset of SL(2, Z)
corresponding to this language as ϕ(L) = {ϕ(w) : w ∈ L+ } ∪ {−ϕ(w) : w ∈ L− }.
The following proposition is an important ingredient of our main results.
I Proposition 13. There is an algorithm that for any given regular signed languages L1and L2 over the alphabet Σ, decides whether ϕ(L1 ) ∩ ϕ(L2 ) is empty or not.
Proof. See Section B of the Appendix in [31].

J

We are now ready to prove our main results.
I Theorem 14. The vector reachability problem and the reachability problem by fractional
linear transformations in SL(2, Z) are decidable.
Proof. Suppose M1 , . . . , Mn is a given finite collection of matrices from SL(2, Z). Let
w1 , . . . , wn ∈ Σ∗ be some words, not necessarily reduced, such that Mi = ϕ(wi ), fori = 1, . . . , n. Define the language Lsemigr that corresponds to the semigroup hM1 , . . . , Mn i∗
as Lsemigr = (w1 + w2 + · · · + wn ) .
Recall that in the vector reachability problem we are given two vectors x and y fromZ × Z, and we ask if there is a matrix M ∈ hM1 , . . . , Mn i such that M x = y. We want toconstruct a regular language Lvrp
x,y that corresponds to these matrices.
If x = 0 and y 6= 0, then we set Lvrp
x,y = ∅ because in this case the equation M x = y does∗
not have a solution. On the other hand, if x = 0 and y = 0, then we set Lvrp
x,y = {S, R}
because any matrix M ∈ SL(2, Z) satisfies the equation M 0 = 0.
Now assume that x 6= 0. Then by Theorem 8, the matrix equation M x = y either has
1 1
no solution, or its solution has the form {BT t C : t ∈ Z}, where T =, and B and
0 1
C are some matrices from SL(2, Z). Moreover, B and C can be computed from x and y in
PTIME. In the case when M x = y has no solution, we set Lvrp
x,y = ∅. If the solution set in
non-empty, then we can rewrite it as{BT t C : t ∈ Z} = {BT t C : t ≥ 0} ∪ {BT −t C : t ≥ 0}.
Let u and v be words from Σ∗ such that B = ϕ(u) and C = ϕ(v). It is easy to check that∗∗3
5
T = ϕ(S 3 R) and T −1 = ϕ(R5 S). Hence Lvrp
x,y = u(S R) v + u(R S) v is a regular languagethat describes the solutions of the equation M x = y in SL(2, Z).
In a similar way we can construct a regular language Lflt
x,y that corresponds to thereachability problem by fractional linear transformations from x to y. By Theorem 10,
the set F(x, y) of matrices from SL(2, Z) that satisfy the equation fM (x) = y is equalto F(x, y) = F1 (x, y) ∪ F2 (x, y), where each Fi (x, y) is either empty or has the form
Fi (x, y) = {Bi T t Ci : t ∈ Z}, where T is as above, and Bi and Ci are some matrices
from SL(2, Z). All these matrices can be computed in PTIME from x and y.

I. Potapov and P. Semukhin

84:9

flt
We define Lflt
x,y as the union Lx,y = L1 ∪ L2 of two regular languages L1 and L2 . If
Fi (x, y) is empty, then we set Li = ∅. Otherwise, let ui and vi be words from Σ∗ such∗∗that Bi = ϕ(ui ) and Ci = ϕ(vi ). Then we can define Li as Li = ui (S 3 R) vi + ui (R5 S) vi .
flt
Thus we defined a regular language Lx,y that corresponds the solution set of the equationfM (x) = y in SL(2, Z).
We remind that in Proposition 13 we work with signed languages. Therefore, in what
follows we convert every regular language L that we have constructed so far into a corresponding signed language (L, ∅).
Finally, the vector reachability problem for x and y has a solution if and only if
ϕ (Lvrpx,y , ∅) ∩ ϕ (Lsemigr , ∅) 6= ∅.
Similarly, the reachability problem by fractional linear transformations for x and y has asolution if and only
if


flt
ϕ (Lx,y , ∅) ∩ ϕ (Lsemigr , ∅) 6= ∅.
By Proposition 13 these questions are algorithmically decidable.
J

A characterization of the matrices M from SL(2, Z) that satisfy the equation M x = y,which is given in Theorem 8, can be computed in polynomial time. However the overall
complexity of the algorithm is EXPTIME if the entries of the matrices are given in binarypresentation. This is due to the fact that a reduced word w that corresponds to a given
matrix M , i.e., such that M = ±ϕ(w), has length exponential in the binary presentationof M . So computing symbolic presentations of given matrices and constructing automata forflt
the languages Lsemigr , Lvrp
x,y and Lx,y takes exponential time. The next steps of the algorithm
take only polynomial time in the size of these automata. However the PTIME algorithm
for computing all mappings from x to y could be combined with the result of Gurevich andSchupp [16] to produce a polynomial time algorithm for the vector reachability problem overthe modular group.

4

Geometric interpretation and extensions

Consider a semigroup generated by matrices M1 , . . . , Mn from SL(2, Z). As we showed
above, this semigroup can be described by a regular language which we called Lsemigr . It’s
not hard to see that the proof of Theorem 14 remains valid if we replace Lsemigr by any otherregular language, that is, a language defined by a finite automaton or a labelled transition
system.
I Proposition 15. Suppose that we are given a finite collection of matrices M1 , . . . , Mn∗from SL(2, Z) and a regular language L ⊆ {1, . . . , n} . Consider the following generalized
reachability problems:
Generalized vector reachability problem. Given two vectors x and y with integer
coefficients, decide whether there exists a word i1 . . . ik from the language L such that
Mi1 · · · Mik x = y.
Generalized reachability problem by fractional linear transformations. Given
two rational numbers x and y, decide whether there exists a word i1 . . . ik from L suchthat fMi1 ···Mik (x) = y.
Then the above generalized reachability problems are decidable.
Proof. The proof of this proposition is similar to the proof of Theorem 14. Namely, itfollows from the fact that a regular language L defines a regular subset in SL(2, Z) and
Proposition 13, where we proved that the emptiness problem for the intersection of two
regular subsets in SL(2, Z) is decidable.
J

M FC S 2 0 1 6

84:10

Vector Reachability Problem in SL(2, Z)

As an application of Proposition 15 let us consider the follow matrix equation
M1x1 · · · Mkxk x = N1y1 · · · Nlyl y,(2)where x1 , . . . , xk and y1 , . . . , yl are non-negative integers. In [1] it was proved that if
M1 , . . . , Mk and N1 , . . . , Nl are commuting n × n matrices over algebraic numbers and x, y
are vectors with algebraic coefficients, then it is decidable in polynomial time whether theEquation (2) has a solution. On the other hand, in [2] it was shown that there is no algorithm for solving the equation M1x1 · · · Mkxk = Z, where M1 , . . . , Mk are integer n × nmatrices and Z is the zero matrix. Using the construction of Kronecker (or tensor) productof matrices, it is possible to show that the above-mentioned result implies that Equation (2)is algorithmically undecidable in general for non-commuting integer matrices M1 , . . . , Mk
and N1 , . . . , Nl .
However with the help of Proposition 15 we can algorithmically solve Equation (2)in the case when M1 , . . . , Mk and N1 , . . . , Nl are matrices from SL(2, Z) and the vectors
x, y have integer coefficients. Indeed, since the matrices from SL(2, Z) are invertible,yly1
we can rewrite (2) as (Nl−1 ) · · · (N1−1 ) M1x1 · · · Mkxk x = y. It is not hard to see that
xk
x1
−1 yl
−1 y1
{(Nl ) · · · (N1 ) M1 · · · Mk : x1 , . . . , xk , y1 , . . . , yl ∈ N ∪ {0} } is a regular subset ofSL(2, Z), and hence the problem is decidable. Using the same idea we can algorithmicallysolve Equation (2) also in the case when x1 , . . . , xk and y1 , . . . , yl are arbitrary integers andthe matrices are from SL(2, Z).
In the rest of this section we will give a geometric interpretation of both reachability
problems (Figure 1), which we will use later to solve a special case of the scalar reachability
problem (Proposition 18).
I Proposition 16. According
to Theorem 8,the set of matrices M from SL(2, Z) that trans
x1yform a vector x =to a vector y = 1 has the form F = {BT kt C : t ∈ Z}.
x2
y2
Consider the equation BT kt Cx = y and let us make the following change of variables:

d
C
T kt
B
−1
u = Cx and v = B y:x −−→ u −−−→ v −−→ y. Then u = v =, where0|d| = gcd(x1 , x2 ) = gcd(y1 , y2 ).
kt
Proof. In the new notations, the equation BT kt Cx = y can be written  as T u = v, andu1v1this equality holds for any t ∈ Z. Now let u =and v =. Hence we haveu2v2   
1 kt u1v= 1 , which is equivalent to u2 = v2 and u1 + ktu2 = v1 , for any t ∈ Z. So,
0 1 u2v2
we must have u2 = v2 = 0 and hence u1 = v1 .
 dTherefore, the vectors u and v have the form u = v =for some d ∈ Z. Moreover,0since u = Cx, we obtain from Lemma 4 that |d| = gcd(x1 , x2 ) = gcd(y1 , y2 ).
J

We can give the following geometric interpretationof the transformation BT t Cx = y: d, then we loop at u for t many times using T ,first, we apply C to x and arrive at u =0
and finally apply B to move from u to y (see Figure 1 on the left).
Similarly, we have the following geometric interpretation of the fractional linear transformation y = fBT t C (x) = fB ◦ fT t ◦ fC (x): first it maps x to ∞ using fC , then loops at ∞for t many times using fT , and finally maps ∞ to y using fB (see Figure 1 on the right).
We now show how to apply the geometric interpretation of the vector reachability problem to solve a special case of the scalar reachability problem.

I. Potapov and P. Semukhin

84:11

y
x
(d, 0)

fT t

fC

B
C
x

∞

y

Tt

fB

Figure 1 Geometric interpretation of the linear transformation y = BT t Cx (left) and of thefractional linear transformation y = fBT t C (x) (right).

I Definition
17. The scalar reachability problem in SL(2, Z) is stated as follows: Let [z1 , z2 ]
 
x1
and
be vectors from Z × Z and let λ be an integer number. We are also given a finitex2
collection of matrices M1 , . . . , Mn from SL(2, Z). The question is to decide whether therexexists a matrix M ∈ hM1 , . . . , Mn i which satisfies the equation [z1 , z2 ] M 1 = λ.
x2
We will consider a special case of this problem when z2 = 1 and λ = 1. Our proof relieson the characterization from Theorem 8 and Corollary 9 and on Proposition 13 in which we
showed that the emptiness problem for the intersection of two regular subsets in SL(2, Z) is
decidable.
I Proposition 18. Suppose that the above equation has the form 
x[a, 1] M 1 = 1,x2

(3)

where a, x1 and x2 are some integer numbers. Then this special case of the scalar reachability
problem is decidable.
Proof. The general idea of the proof is the same as in Theorem 14, that is, we will show thatthe set of matrices M ∈ SL(2, Z) that satisfy Equation (3) can be described by a regular
language. First, let us consider a geometric interpretation    of this problem. We can rewritexyEquation (3) as a system of two equations: M 1 = 1 and ay1 + y2 = 1. So, M satisfies
x2
y2
 
 
x1
y
Equation (3) if and only if it maps a fixed vector x =to some vector y = 1 thatx2y2lies on the line L described by the equation ay1 + y2 = 1. In other words, we have a vector
to line reachability problem for the line L that is defined by the equation ay1 + y2 = 1.
Note that if a vector y lies of the line ay1 + y2 = 1, then gcd(y1 , y2 ) = 1. Hence byLemma 4, Equation (3) has a solution only if gcd(x1 , x2 ) = 1. So, from now on we assume
that gcd(x1 , x2 ) = 1.
By Corollary 9, any M ∈ SL(2, Z) that maps x to a vector y on the line L has the form
M = BT t C, where B and C are some matrices from SL(2, Z) and t ∈ Z. Geometrically, thetransformation y = BT t Cx goes via the point (1, 0) as shown in Figure 2.
Note that the matrices B and C above depend on the vector y as a parameter. Here we
prove a useful lemma which will imply that we can choose only one matrix C that maps x
1
to
independently of the vector y.
0

M FC S 2 0 1 6

84:12Vector Reachability Problem in SL(2, Z)
 
 
x1
y
and y = 1 be any vectors from Z×Z such that gcd(x1 , x2 ) =x2
y2
gcd(y1 , y2 ) = d. Let d1 and d2 be any integer numbers with |d1 |= |d2 | = d and let A1 , B1
didand A2 , B2 by any matrices from SL(2, Z) such that Bi x =and Ai i = y, for00i = 1, 2. Then {A1 T t B1 : t ∈ Z} = {A2 T t B2 : t ∈ Z}. In other words, the following
diagrams define the same set of matrices that map x to y.
I Lemma 19. Let x =x

B1 d  A1
1

0

y

x

B2 d  A2
2

0

Tt

y

Tt

Proof. See Section C of the Appendix in [31].

J

By Lemma
  19, we can choose any matrix C from SL(2, Z) that maps a vector x to
1
1
the vector, and for each y on the line L we can choose any matrix By that maps00
to the vector y. Then the solution of Equation (3) will be described by the following set
F = {By T t C : y ∈ L and t ∈ Z}. Figure 2 gives geometric interpretation of this solution.

y
Tt
By

L

x
C

(1, 0)

Figure 2 Geometric interpretation of the scalar reachability problem.

 yWe need to choose By in such a way that F becomes a regular set. Let y = 1 ∈ L,
y2


y1
−1
then we have ay1 + y2 = 1. As one can check, if we let By =then−ay1 + 1 a 
1By ∈ SL(2, Z) and By= y.
0
Since every entry of By is a linear function of y1 , we obtain by Proposition 7 that
By = AT ky1 D, where A and D are some matrices from SL(2, Z) and k is some integer
number (in fact, one can show that k = 1). Finally, we can write all solutions of Equation (3)as F = {AT ky1 DT t C : y1 ∈ Z and t ∈ Z}. This is clearly a regular set and, therefore, thescalar reachability problem is decidable.
J
References1

László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, and Eugene M. Luks. Multiplicativeequations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM
Symposium on Discrete Algorithms, SODA ’96, pages 498–507, Philadelphia, PA, USA,1996. Society for Industrial and Applied Mathematics.

I. Potapov and P. Semukhin

2
3
4
5

6
7

8

9
10
11
12
13
14

15

16
17

18

19
20

84:13

Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumäki, and Igor Potapov. Matrix equationsand Hilbert’s tenth problem. Internat. J. Algebra Comput., 18(8):1231–1241, 2008.
Paul Bell and Igor Potapov. On undecidability bounds for matrix decision problems. Theoretical Computer Science, 391(1-2):3–13, 2008.
Paul Bell and Igor Potapov. Reachability problems in quaternion matrix and rotation
semigroups. Information and Computation, 206(11):1353–1361, 2008.
Paul C. Bell, Mika Hirvensalo, and Igor Potapov. Mortality for 2x2 matrices is NP-hard. In
Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer Science 2012, volume 7464 of Lecture Notes in Computer Science, pages
148–159. Springer Berlin Heidelberg, 2012.
Paul C. Bell and Igor Potapov. On the computational complexity of matrix semigroupproblems. Fundam. Inf., 116(1-4):1–13, January 2012.
Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. Decidable
and undecidable problems about quantum automata. SIAM J. Comput., 34(6):1464–1473,
June 2005.
Julien Cassaigne, Tero Harju, and Juhani Karhumaki. On the undecidability of freeness ofmatrix semigroups. International Journal of Algebra and Computation, 09(03n04):295–305,
1999. URL: http://www.worldscientific.com/doi/pdf/10.1142/S0218196799000199.
Julien Cassaigne and François Nicolas. On the decidability of semigroup freeness. RAIRO- Theor. Inf. and Applic., 46(3):355–399, 2012.
Fernando Chamizo. Non-euclidean visibility problems. Proceedings of the Indian Academyof Sciences - Mathematical Sciences, 116(2):147–160, 2006.
Christian Choffrut and Juhani Karhumaki. Some decision problems on integer matrices.
RAIRO-Theor. Inf. Appl., 39(1):125–131, 2005.
J. Elstrodt, F. Grunewald, and J. Mennicke. Arithmetic applications of the hyperbolic
lattice point theorem. Proc. London Math. Soc., s3-57:pp.239–283, 1988.
J. Esparza, A. Finkel, and R. Mayr. On the verification of broadcast protocols. In Logicin Computer Science, 1999. Proceedings. 14th Symposium on, pages 352–359, 1999.
Esther Galby, Joël Ouaknine, and James Worrell. On Matrix Powering in Low Dimensions.
In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of Leibniz International
Proceedings in Informatics (LIPIcs), pages 329–340, Dagstuhl, Germany, 2015. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik.
M. P. García del Moral, I. Martín, J. M. Peña, and A. Restuccia. Sl(2,z) symmetries,
supermembranes and symplectic torus bundles. Journal of High Energy Physics, 2011(9):1–
12, 2011.
Yuri Gurevich and Paul Schupp. Membership problem for the modular group. SIAM J.
Comput., 37(2):425–459, May 2007.
Vesa Halava, Tero Harju, and Mika Hirvensalo. Undecidability bounds for integer
matrices using Claus instances. International Journal of Foundations of Computer Science, 18(05):931–948, 2007. URL: http://www.worldscientific.com/doi/pdf/10.1142/
S0129054107005066.
Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumaki. Skolem’s problem - on
the border between decidability and undecidability. Technical Report 683, Turku Centre
for Computer Science, 2005.
Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the Smithand Hermite normal forms of an integer matrix. SIAM J. Comput., 8(4):499–507, 1979.
Alexei Lisitsa and Igor Potapov. Membership and reachability problems for row-monomialtransformations. In Mathematical Foundations of Computer Science 2004, 29th Interna-

M FC S 2 0 1 6

84:14Vector Reachability Problem in SL(2, Z)

21
22
23

24
25

26

27

28

29
30

31
32
33

34

tional Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings,
pages 623–634, 2004.
Roger C. Lyndon and Paul E. Schupp. Combinatorial group theory. Springer-Verlag,
Berlin-New York, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89.
Dana Mackenzie. A new twist in knot theory. What’s Happening in the Mathematical
Sciences, Volume 7, 2009.
Wilhelm Magnus, Abraham Karrass, and Donald Solitar. Combinatorial group theory.
Dover Publications, Inc., New York, revised edition, 1976. Presentations of groups in termsof generators and relations.
A. Markov. On certain insoluble problems concerning matrices. Doklady Akad. Nauk SSSR,
57(6):539–542, June 1947.
Thomas Noll. Musical intervals and special linear transformations. Journal of Mathematics and Music: Mathematical and Computational Approaches to Music Theory, Analysis,
Composition and Performance, vol.1, 2007.
Joël Ouaknine, João Sousa Pinto, and James Worrell. On termination of integer linear
loops. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA ’15, pages 957–969. SIAM, 2015.
Joël Ouaknine and James Worrell. On the positivity problem for simple linear recurrence
sequences,. In Automata, Languages, and Programming - 41st International Colloquium,
ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 318–329,
2014.
Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages
330–341, 2014.
Leonid Polterovich and Zeev Rudnick. Stable mixing for cat maps and quasi-morphisms ofthe modular group. Ergodic Theory and Dynamical Systems, 24:609–619, 4 2004.
Igor Potapov. Composition problems for braids. In 33nd International Conference onFoundations of Software Technology and Theoretical Computer Science, volume 24 of
LIPIcs. Leibniz Int. Proc. Inform., pages 175–187. Schloss Dagstuhl. Leibniz-Zent. Inform.,
Wadern, 2013.
Igor Potapov and Pavel Semukhin. Vector reachability problem in SL(2, Z). CoRR,
abs/1510.03227, 2015. URL: http://arxiv.org/abs/1510.03227.
Robert A. Rankin. Modular forms and functions. Cambridge University Press, CambridgeNew York-Melbourne, 1977.
Edward Witten. SL(2, Z) action on three-dimensional conformal field theories with abelian
symmetry. In From fields to strings: circumnavigating theoretical physics. Vol. 2, pages
1173–1200. World Sci. Publ., Singapore, 2005.
Don Zagier. Elliptic modular forms and their applications. In Kristian Ranestad, editor,
The 1-2-3 of Modular Forms, Universitext, pages 1–103. Springer Berlin Heidelberg, 2008.