Matrix mortality problem: Difference between revisions
added Category:Undecidable problems; removed {{uncategorized}} using HotCat |
added Category:Unsolved problems in computer science using HotCat |
||
| Line 67: | Line 67: | ||
[[Category:Undecidable problems]] |
[[Category:Undecidable problems]] |
||
[[Category:Unsolved problems in computer science]] |
|||
Revision as of 22:45, 24 April 2024
In computer science, the matrix mortality problem is a decision problem that asks, given a finite set of n×n matrices with integer coefficients, whether the zero matrix can be expressed as a finite product of matrices from this set.
The matrix mortality problem is known to be undecidable for when n ≥ 3[1]. In fact, it is already undecidable for sets of 6 matrices (or more) when n = 3, for 4 matrices when n = 5, for 3 matrices when n = 9, and for 2 matrices when n = 15[2].
In the case n = 2, it is an open problem whether matrix mortality is decidable, but several special cases have been solved: the problem is decidable for sets of 2 matrices[3], and for sets of matrices which contain at most one invertible matrix[4].
Notes
- ^ Paterson, Mike (1970). "Unsolvability in 3×3 matrices". Studies in Applied Mathematics. 49: 105–107.
- ^ Cassaigne, Julien; Halava, Vesa; Harju, Tero; Nicolas, Francois (2014). "Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More". arXiv:1404.0644 [cs.DM].
- ^ Bournez, Olivier; Branicky, Michael. "The Mortality Problem for Matrices of Low Dimensions" (PDF). Theory of Computing Systems. 35: 433–448. doi:10.1007/s00224-002-1010-5.
- ^ Heckman, Christopher Carl (2019). "The 2×2 Matrix Mortality Problem and Invertible Matrix". arXiv:1912.09991 [math.RA].
 | This computer science article is a stub. You can help Wikipedia by expanding it. |