The Membership Problem for 2x2 integer matrices

Abstract: The Membership Problem for matrix semigroups is stated as follows: given a finite collection of square matrices F = { M_1,...,M_k } and a target matrix M, decide if M can be presented as a product of matrices from F. In other words, decide if M belongs to the semigroup generated by F. It has been known for a long time that the Membership Problem is undecidable for 3x3 matrices. On the other hand, it is a big open question whether this problem is decidable for 2x2 matrices or for some special cases of 3x3 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.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.