Revisiting Finiteness of Matrix Monoids
Abstract
This paper concerns decision problems related to finite monoids of rational matrices. We show that determining finiteness of a given finitely presented monoid is in PSPACE, improving the known $\text{co}{-}\text{NEXP}^{\text{NP}}$ bound. We also show that the membership problem for finite matrix monoids is PSPACE-complete, improving the known NEXP-upper bound. Our two complexity results are corollaries of a new polynomial bit-size bound on matrix entries in finite monoids. This is obtained by reduction to the case of matrix groups, using the structure theory of noncommutative algebras and of matrix monoids. Our techniques also give us a polynomial-time algorithm for deciding whether a monoid of rational matrices is conjugate to a monoid of integer matrices.
- Comment
- 17 pages, published at ICALP 2026
- DOI
- 10.4230/LIPIcs.ICALP.2026.158