On the membership of invertible diagonal and scalar matrices

Bell, Paul

Abstract

In this paper, we consider decidability questions that are related to the membership problem in matrix semigroups. In particular, we consider the membership of a given invertible diagonal matrix in a matrix semigroup and then a scalar matrix, which has a separate geometric interpretation. Both problems have been open for any dimensions and are shown to be undecidable in dimension 4 with integral matrices by a reduction of the Post Correspondence Problem (PCP). Although the idea of PCP reduction is standard for such problems, we suggest a new coding technique to cover the case of diagonal matrices.

Citation

Bell, P. (2007). On the membership of invertible diagonal and scalar matrices. Theoretical Computer Science, 37 - 45. https://doi.org/10.1016/j.tcs.2006.11.011

• Acceptance Date: Nov 19, 2006
• Publication Date: Mar 6, 2007
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Pages: 37 - 45
• DOI: https://doi.org/10.1016/j.tcs.2006.11.011
• Public URL: https://keele-repository.worktribe.com/output/423609
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S030439750600870X?via%3Dihub