Paul Bell p.c.bell@keele.ac.uk
On the membership of invertible diagonal and scalar matrices
Bell
Authors
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. (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 |
Publisher URL | https://www.sciencedirect.com/science/article/pii/S030439750600870X?via%3Dihub |
Files
1-s2.0-S030439750600870X-main.pdf
(257 Kb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by-nc-nd/4.0/
On_the_Membership_of_Invertible_Diagonal_Matrices.pdf
(258 Kb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Towards Uniform Online Spherical Tessellations
(2022)
Journal Article
Freeness properties of weighted and probabilistic automata over bounded languages
(2019)
Journal Article
Towards Uniform Online Spherical Tessellations
(2019)
Book Chapter
On the decidability and complexity of problems for restricted hierarchical hybrid systems
(2016)
Journal Article
Downloadable Citations
About Keele Repository
Administrator e-mail: research.openaccess@keele.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search