Matrix mortality

This section will contain a proof that the \(3\times 3\) matrix mortality problem is undecidable. It uses a related problem which we saw in Exercise 21. This is the problem of deciding whether a given set of \(3\times 3\) matrices with integer entries has some finite product with a \(0\) in the upper-left corner. We called this \(M_0\), and showed that \(M_0 \leq M_{1,1}\), where \(M_{1,1}\) is the \(3\times 3\) matrix mortality problem. So we need only show that \(PCP\leq_m M_0\) in order to conclude our work, where \(PCP\) is from our work on Post’s Correspondence Problem.

Credits

The undecidability of matrix mortality was first proved in

Michael S. Paterson, (1970). “Unsolvability in 3 × 3 matrices”. Studies in Applied Mathematics. 49: 105–107.

The proof here comes from

Vesa Halava and Tero Harju, (2001). Mortality in Matrix Semigroups. The American Mathematical Monthly, 108(7), 649–653.