Decidability of a matrix product being the identity

This is undecidable in dimension 4 or up see http://cgi.csc.liv.ac.uk/~igor/papers/matrixcomp.pdf

The result is proved in Bell, P. C., Potapov, I.: On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups, International Journal of Foundations of Computer Science, 21(6), 2010, 963–978.

The problem is at least NP-hard in dimension 2.


There is a new algorithm (in manuscript) that shows that Identity Problem for SL(2,Z) is in NP, meaning that it is also NP-complete.

Also point to point reachability for SL(2,Z) is also shown recently to be decidable, see proceeding of MFCS 2016 http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6492

Which question was raised by Kontsevich and what is the connection with identity matrix? Could you please comment.

Tags:

Decidability

Related

Are rounded rectangle billiard dynamics ergodic? "Fraïssé limits" without amalgamation Is there a finitely generated residually finite group with solvable word problem that does not embed in a finitely presented residually finite group? Function extensionality: does it make a difference? why would one keep it out of the axioms? Basics on anabelian geometry and Grothendieck's section conjecture Does the generator of a 1-parameter group of Banach space isometries know which elements are entire? history of calculus of several variables How many unit cylinders can touch a unit ball? Class 1 vs. class 2 in regular graphs Models of intuitionistic linear logic that reflect the resource interpretation Very Large Cardinal Axioms and Continuum Hypothesis Moore decomposition, dual to Postnikov tower

Recent Posts