Document Open Access Logo

On the Identity Problem for Unitriangular Matrices of Dimension Four

Author Ruiwen Dong

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.43.pdf
  • Filesize: 0.68 MB
  • 14 pages

Document Identifiers

Author Details

Ruiwen Dong
  • Department of Computer Science, University of Oxford, UK

Cite AsGet BibTex

Ruiwen Dong. On the Identity Problem for Unitriangular Matrices of Dimension Four. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.43

Abstract

We show that the Identity Problem is decidable in polynomial time for finitely generated sub-semigroups of the group UT(4, ℤ) of 4 × 4 unitriangular integer matrices. As a byproduct of our proof, we also show the polynomial-time decidability of several subset reachability problems in UT(4, ℤ).

Subject Classification

ACM Subject Classification
  • Computing methodologies → Symbolic and algebraic manipulation
Keywords
  • identity problem
  • matrix semigroups
  • unitriangular matrices

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, and Eugene M. Luks. Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 498-507, 1996. Google Scholar
  2. Paul C. Bell and Igor Potapov. On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups. International Journal of Foundations of Computer Science, 21(06):963-978, 2010. Google Scholar
  3. Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. Google Scholar
  4. Christian Choffrut and Juhani Karhumäki. Some decision problems on integer matrices. RAIRO-Theoretical Informatics and Applications-Informatique Théorique et Applications, 39(1):125-131, 2005. Google Scholar
  5. Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, and James Worrell. On reachability problems for low-dimensional matrix semigroups. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 44:1-44:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.44.
  6. Sang-Ki Ko, Reino Niskanen, and Igor Potapov. On the identity problem for the special linear group and the heisenberg group. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 132:1-132:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.132.
  7. Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. Algebra and Computer Science, 677:138-153, 2016. Google Scholar
  8. V. M. Kopytov. Solvability of the problem of occurrence in finitely generated soluble groups of matrices over the field of algebraic numbers. Algebra and Logic, 7(6):388-393, 1968. Google Scholar
  9. Engel Lefaucheux. Private Communication, 2022. Google Scholar
  10. A. Markov. On certain insoluble problems concerning matrices. Doklady Akad. Nauk SSSR, 57(6):539-542, 1947. Google Scholar
  11. K. A. Mikhailova. The occurrence problem for direct products of groups. Matematicheskii Sbornik, 112(2):241-251, 1966. Google Scholar
  12. Michael S. Paterson. Unsolvability in 3 × 3 matrices. Studies in Applied Mathematics, 49(1):105-107, 1970. Google Scholar
  13. Igor Potapov and Pavel Semukhin. Decidability of the membership problem for 2 × 2 integer matrices. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 170-186. SIAM, 2017. Google Scholar
  14. Igor Potapov and Pavel Semukhin. Membership problem in GL(2, Z) extended by singular matrices. In Kim G. Larsen, Hans L. Bodlaender, and Jean-François Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, volume 83 of LIPIcs, pages 44:1-44:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.44.
  15. Joseph J. Rotman. An introduction to the theory of groups, volume 148. Springer Science & Business Media, 2012. Google Scholar
  16. Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact