Skip to main content
2 of 4
added 1866 characters in body

In relation to the undecidability for 3x3 matrices and the comment of http://mathoverflow.net/users/1587/john-stillwell that

"The corresponding problem for 2×2 matrices is apparently still open":

There is a recent proof that the membership for non-singular 2×2 integer matrices is decidable (i.e. for 2x2 integer matrices with nonzero determinant). http://arxiv.org/abs/1604.02303

However in terms of uncedaibiltity the identity problem for 3x3 integer matrices is still open, while the general open problem about the identity matrix was proved to be undecidable for 4x4 matrices over integers , see

Paul C. Bell, Igor Potapov: On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups. Int. J. Found. Comput. Sci. 21(6): 963-978 (2010) and arxiv.org/abs/0902.1975

solving the long standing open problem see Problem 10.3 in http://press.princeton.edu/math/blondel/solutions.html Unsolved Problems in Mathematical Systems and Control. Theory, Princeton Univ. Press, 2004.

It also follows that whether a matrix semigroup is a group is undecidable for 4x4 integer matrices.

--- extra comments ------

Finally here are the comments about the importance of the are on matrix products.

Matrices and matrix products play a crucial role in the representation and analysis of various computational processes, i.e., linear recurrent sequences, arithmetic circuits, hybrid and dynamical systems, probabilistic and quantum automat, stochastic games, broadcast protocols, optical systems, etc. Many simply formulated and elementary problems for matrices are inherently difficult to solve even in dimension two, and most of these problems become undecidable in general starting from dimension three or four. One such hard question is the Membership Problem.

Even algorithmic problems for matrices over SL(2,Z) have many important complexity questions. They are appear in the context of many fundamental problems from hyperbolic geometry, dynamical systems, Lorenz/modular knots, braid groups, particle physics, high energy physics, M/string theories, ray tracing analysis, music theory, etc.

I would like to also to cite Prof. J. N. Tsitsiklis http://www.mit.edu/~jnt/complex.html from the webpage "Computational complexity in systems and control" which contains results on computational problems for matrix products:

"The subject is multifaceted and interesting in many different ways. It can help the practitioner in choosing problem formulations, and in calibrating expectations of what can be algorithmically accomplished. For the systems theorist or the applied mathematician, it raises a variety of challenging open problems that require a diverse set of tools from both discrete and continuous mathematics. Finally, for the theoretical computer scientist, the problems in systems and control theory provide the opportunity to relate abstractly defined complexity classes and specific problems of practical interest."