1. On the membership of invertible diagonal and scalar matrices
- Author
-
Bell, Paul and Potapov, Igor
- Subjects
- *
MATRICES (Mathematics) , *MATRIX groups , *SCALAR field theory , *ABSTRACT algebra , *UNIVERSAL algebra - Abstract
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. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF