Decision problems for Matrix Semigroups

19^th February 2020, 14:00
Igor Potapov
University of Liverpool

Abstract

A large number of naturally defined matrix problems are still unanswered despite the long history of matrix theory. Originally in Arthur Cayley's "A Memoir on the Theory of Matrices" in 1858, the notion of a matrix arises naturally from abbreviated notations for a set of linear equations where he also defined associated operation of multiplication, notions of determinant, inverse matrices, etc. Nowadays questions on matrices and matrix problems emerge in much larger context as they appear in the analysis of various digital processes, verification problems, in the context of control theory questions, etc. Surprisingly, many simply formulated problems for matrices such as Membership (including special cases of Identity and Mortality), Vector reachability, Scalar reachability, Freeness, etc. are inherently difficult to solve even in dimension two, and most of these problems become undecidable in general starting from dimension three or four. In this talk I will discuss the decidability and the complexity of reachability problems for matrix semigroups highlighting known decidability/undecidability borders, open problems and closely related questions in mathematics and computer science.