Decidability of the membership problem for 2 × 2 integer matrices
Igor Potapov, Pavel Semukhin · Symposium on Discrete Algorithms · 2017
The main result of this paper is the decidability of the membership problem for 2 × 2 nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular 2 × 2 integer matrices M1, . . . , Mn and M decides whether M belongs to the semigroup generated by {M1, . . . , Mn}. Our algorithm relies on a translation of numerical problems on matrices into combinatorial problems on words. It also makes use of some algebraic properties of well-known subgroups of GL(2, ℤ) and various new techniques and constructions that help to convert matrix equations into the emptiness problem for intersection of regular languages.