Matrix mortality problem explained

In computer science, the matrix mortality problem (or mortal matrix 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 when n ≥ 3. In fact, it is already undecidable for sets of 6matrices (or more) when n = 3, for 4 matrices when n = 5, for 3 matrices when n = 9, and for 2 matrices when n = 15.

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, and for sets of matrices which contain at most one invertible matrix.

Notes

^{[1] [2] [3] [4]}

Notes and References

1. Paterson . Michael S. . Mike Paterson . 10.1002/sapm1970491105 . Studies in Applied Mathematics . 255400 . 105–107 . Unsolvability in matrices . 49 . 1970.
2. 1404.0644 . Cassaigne . Julien . Halava . Vesa . Harju . Tero . Nicolas . Francois . Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More . cs.DM . 2014 .
3. Bournez . Olivier . Branicky . Michael . The Mortality Problem for Matrices of Low Dimensions . Theory of Computing Systems . 35 . 2002 . 433–448 . 10.1007/s00224-002-1010-5 .
4. 1912.09991 . Heckman . Christopher Carl . The 2×2 Matrix Mortality Problem and Invertible Matrices . math.RA . 2019 .