Membership Problem for 2x2 integer matrices

The Membership Problem for matrix semigroups is stated as follows: given a finite collection of n by n matrices M_1,..., M_k andM, decide if M can be presented as a product of matrices from{M_1,...,M_k}, in other words, decide if M belongs to the semigroup generated by {M_1,...,M_k}. It is known that the Membership Problem is undecidable in dimension 3 even for integer matrices. On the other hand, it is a big open question whether this problem is decidable for 2x2 matrices.

In our recent work we showed that the Membership Problem is decidable for 2x2 nonsingular integer matrices. In this talk I will present a proof of this result which is based on a combination of different ideas from linear algebra, group theory and automata theory.