Matrix mortality problem
In computer science, the matrix mortality problem (or mortal matrix problem) is a decision problem that asks, given a set of size m 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 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]
| n\m | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 2 | ✅ | ✅ | ||||
| 3 | ✅ | ✖️ | ||||
| 4 | ✅ | ✖️ | ||||
| 5 | ✅ | ✖️ | ✖️ | ✖️ | ||
| ... | ✅ | ✖️ | ✖️ | ✖️ | ||
| 9 | ✅ | ✖️ | ✖️ | ✖️ | ✖️ | |
| ... | ✅ | ✖️ | ✖️ | ✖️ | ✖️ | |
| 15 | ✅ | ✖️ | ✖️ | ✖️ | ✖️ | ✖️ |
References
- ↑ "Unsolvability in 3 × 3 matrices". Studies in Applied Mathematics 49: 105–107. 1970. doi:10.1002/sapm1970491105.
- ↑ 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 (2002). "The Mortality Problem for Matrices of Low Dimensions". Theory of Computing Systems 35 (4): 433–448. doi:10.1007/s00224-002-1010-5. https://www.lix.polytechnique.fr/~bournez/load/Papier-TOCS-2002.pdf.
- ↑ Heckman, Christopher Carl (2019). "The 2×2 Matrix Mortality Problem and Invertible Matrices". arXiv:1912.09991 [math.RA].
- Bell, Paul; Potapov, Igor (2008-02-04). "On undecidability bounds for matrix decision problems". Theoretical Computer Science. Combinatorics, Automata and Number Theory 391 (1): 3–13. doi:10.1016/j.tcs.2007.10.025. ISSN 0304-3975. https://www.sciencedirect.com/science/article/pii/S0304397507007840.
- Halava, Vesa (August 1997). Decidable and Undecidable Problems in Matrix Theory (Report). Turku Centre for Computer Science. https://dl.acm.org/doi/10.5555/893250.>
 |  |
