mortality problem
The mortality problem is the question if some product of a given set of matrices yields the 0-matrix. In general, the mortality problem is undecidable. To have a feeling for the difficulty of the problem, I only considered two 3x3-matrices with entries -1..1. The hardest problem I found so far is
$$ A = \begin{bmatrix} 0 & 1 & -1\\ 0 & 1 & -1\\ 1 & 0 & 1 \end{bmatrix} $$
$$ B = \begin{bmatrix} -1 & 0 & 1\\ -1 & -1 & 0\\ -1 & 1 & 1 \end{bmatrix} $$
Solution : [0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0]
0 stands for A, 1 for B, so $AB^2A^3B^4A^2BAB^2A=0$. There is no shorter product, the optimal length is 17.
An obvious condition for the matrices A and B is $\det(A)\det(B)=0$
Now my questions
- Is the mortality problem decidable for two 3x3-matrices ?
- What is the maximal possible length of an optimal solution depending on the size of the entries ?
How can it be proven that the general mortality problem is undecidacle, and where are the limits for decidability ?
My new record is :
18 [1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1]
a
$$ \begin{bmatrix} 1 & -1 & 0\\ -1 & 0 & -1\\ 0 & 0 & 1 \end{bmatrix} $$
b
$$ \begin{bmatrix} 1 & -1 & -1\\ 1 & 0 & 0\\ -1 & -1 & -1 \end{bmatrix} $$
$\endgroup$ 11 Answer
$\begingroup$The problem is undecidable for 3x3 matrices with integer entries:
Therefore, there is no (computable) bound on the size of the optimal solution. (otherwise one could decide the problem by first computing the bound, then testing all possible answers of this size)
More details and I guess an answer to your third point here:
$\endgroup$ 1
