// Workers AI · dad joke modeWhat did the Matrix say to mortality? You're coded to die.

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]

The current frontier of knowledge
n\m	1	2	3	4	5	6
2	✅	✅
3	✅					✖️
4	✅					✖️
5	✅			✖️	✖️	✖️
...	✅			✖️	✖️	✖️
9	✅		✖️	✖️	✖️	✖️
...	✅		✖️	✖️	✖️	✖️
15	✅	✖️	✖️	✖️	✖️	✖️

References

↑ Paterson, Michael S. (1970). "Unsolvability in $3 \times 3$ matrices". Studies in Applied Mathematics. 49: 105–107. doi:10.1002/sapm1970491105. MR 0255400.
↑ 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" (PDF). Theory of Computing Systems. 35 (4): 433–448. doi:10.1007/s00224-002-1010-5.
↑ 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.
Halava, Vesa (August 1997). Decidable and Undecidable Problems in Matrix Theory (Report). Turku Centre for Computer Science.>

This computer science article is a stub. You can help Wikipedia by adding missing information.

[paterson-1] Paterson, Michael S. (1970). "Unsolvability in $3 \times 3$ matrices". Studies in Applied Mathematics. 49: 105–107. doi:10.1002/sapm1970491105. MR 0255400.

[cassaigne-halava-harju-nicolas-2] 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-branicky-3] Bournez, Olivier; Branicky, Michael (2002). "The Mortality Problem for Matrices of Low Dimensions" (PDF). Theory of Computing Systems. 35 (4): 433–448. doi:10.1007/s00224-002-1010-5.

[heckman-4] Heckman, Christopher Carl (2019). "The 2×2 Matrix Mortality Problem and Invertible Matrices". arXiv:1912.09991 [math.RA].

[1]

[2]

[3]

[4]