Back to Search
Start Over
On the membership of invertible diagonal and scalar matrices
- Source :
-
Theoretical Computer Science . Mar2007, Vol. 372 Issue 1, p37-45. 9p. - Publication Year :
- 2007
-
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]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 372
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 24143391
- Full Text :
- https://doi.org/10.1016/j.tcs.2006.11.011