Given a finite set $\mathcal{M}$ of $n \times n$ matrices over the integers, can you express the zero matrix as a product of matrices in $\mathcal{M}$?
This is known as the mortality problem.
Michael Paterson showed in 1970 that it is undecidable, even for $n=3$.
Later it was shown that mortality remains undecidable for $n=3$ and $|\mathcal{M}| = 7$, and for $n=21$ and $|\mathcal{M}| = 2$.
Decidability of mortality for $n=2$ is open.
If all matrices in $\mathcal{M}$ are nonnegative, the mortality problem becomes decidable, because then it matters only whether matrix entries are $0$ or not. Specifically, view the given matrices as transition matrices of a nondeterministic finite automaton where all states are initial and accepting, and check whether there is a word that is not accepted. This problem is decidable and PSPACE-complete. One can construct cases where the shortest word that is not accepted by the automaton has exponential length.
In this post we focus on the nonnegative case $\mathcal{M} \subseteq \mathbb{N}^{n \times n}$, where $\mathbb{N} = \{0, 1, 2, \ldots\}$. The automaton view is convenient, so let us associate to $\mathcal{M}$ a bijection $M : \Sigma \to \mathcal{M}$ for a finite alphabet $\Sigma$, and extend $M$ to $M : \Sigma^* \to \mathbb{N}^{n \times n}$ in the natural way, that is, so that $M(a b b) = M(a) M(b) M(b)$ etc. The mortality problem is then: given $M: \Sigma \to \mathbb{N}^{n \times n}$, is there a word $w \in \Sigma^*$ such that $M(w) = 0$? We call such a word a killing word and I apologize for my violent language.
As I said, whether a killing word exists is PSPACE-complete and the shortest killing word may be exponentially long. If one can form only finitely many different products of the given matrices, in other words if the image of $M$ under $\Sigma^*$ is finite, then the computational picture becomes much more “polynomial-time”. First of all, one can check in polynomial time whether $M(\Sigma^*)$ is finite (not trivial but not very hard). Let's assume that $M(\Sigma^*)$ is finite for the rest of the post. Then mortality can be decided in polynomial time: compute the average matrix \[ \frac{1}{|\Sigma|} \sum_{a \in \Sigma} M(a) \] and its spectral radius $\rho$. If $\rho < 1$ then there is a killing word; if $\rho = 1$ then there is no killing word; the case $\rho > 1$ is impossible.
I find it intriguing that the mortality algorithm above is efficient but not constructive: it tells you whether a killing word exists but it does not construct a killing word. The algorithm doesn't even say anything about the length of the killing word. In one of my first blog posts I essentially asked whether there exists a polynomially short killing word whenever there exists a killing word. I also asked if a killing word can be computed in polynomial time. A smart undergraduate student, Corto Mascle from the ENS Paris-Saclay, visited me last summer and found positive answers to both questions:
Replacing the length bound in the (second) theorem with $(n-1)^2$ would imply a vast generalization of Černý's conjecture, a notorious problem in automata theory. As far as I know, this vast generalization of Černý's conjecture has not yet been refuted.
This post is based on a STACS'19 paper, where more details can be found.
If all matrices in $\mathcal{M}$ are nonnegative, the mortality problem becomes decidable, because then it matters only whether matrix entries are $0$ or not. Specifically, view the given matrices as transition matrices of a nondeterministic finite automaton where all states are initial and accepting, and check whether there is a word that is not accepted. This problem is decidable and PSPACE-complete. One can construct cases where the shortest word that is not accepted by the automaton has exponential length.
In this post we focus on the nonnegative case $\mathcal{M} \subseteq \mathbb{N}^{n \times n}$, where $\mathbb{N} = \{0, 1, 2, \ldots\}$. The automaton view is convenient, so let us associate to $\mathcal{M}$ a bijection $M : \Sigma \to \mathcal{M}$ for a finite alphabet $\Sigma$, and extend $M$ to $M : \Sigma^* \to \mathbb{N}^{n \times n}$ in the natural way, that is, so that $M(a b b) = M(a) M(b) M(b)$ etc. The mortality problem is then: given $M: \Sigma \to \mathbb{N}^{n \times n}$, is there a word $w \in \Sigma^*$ such that $M(w) = 0$? We call such a word a killing word and I apologize for my violent language.
As I said, whether a killing word exists is PSPACE-complete and the shortest killing word may be exponentially long. If one can form only finitely many different products of the given matrices, in other words if the image of $M$ under $\Sigma^*$ is finite, then the computational picture becomes much more “polynomial-time”. First of all, one can check in polynomial time whether $M(\Sigma^*)$ is finite (not trivial but not very hard). Let's assume that $M(\Sigma^*)$ is finite for the rest of the post. Then mortality can be decided in polynomial time: compute the average matrix \[ \frac{1}{|\Sigma|} \sum_{a \in \Sigma} M(a) \] and its spectral radius $\rho$. If $\rho < 1$ then there is a killing word; if $\rho = 1$ then there is no killing word; the case $\rho > 1$ is impossible.
I find it intriguing that the mortality algorithm above is efficient but not constructive: it tells you whether a killing word exists but it does not construct a killing word. The algorithm doesn't even say anything about the length of the killing word. In one of my first blog posts I essentially asked whether there exists a polynomially short killing word whenever there exists a killing word. I also asked if a killing word can be computed in polynomial time. A smart undergraduate student, Corto Mascle from the ENS Paris-Saclay, visited me last summer and found positive answers to both questions:
Given $M : \Sigma \to \mathbb{N}^{n \times n}$ such that $M(\Sigma^*)$ is finite and a killing word exists, one can compute in polynomial time a killing word of length at most $\frac{1}{16} n^5 + \frac{15}{16} n^4$.
The proof is elementary but not easy.
The arguments are combinatorial in nature and are best expressed in the language of unambiguous automata.
We actually have a more general theorem:
Given $M : \Sigma \to \mathbb{N}^{n \times n}$ such that $M(\Sigma^*)$ is finite, one can compute in polynomial time a word $w$ of length at most $\frac{1}{16} n^5 + \frac{15}{16} n^4$ such that $M(w)$ has minimum rank in $M(\Sigma^*)$.
The latter theorem implies the former, as the zero matrix is the only matrix of rank $0$.
Curiously, the latter theorem had already been known for the case when the minimum rank is not $0$, that is, when a killing word does not exist.
That had been proved in a 1988 paper by Arturo Carpi in the context of synchronization and the theory of codes.
His proof is easier and his bound on the length of $w$ is better, $O(n^4)$, but his argument doesn't work for killing words.
Replacing the length bound in the (second) theorem with $(n-1)^2$ would imply a vast generalization of Černý's conjecture, a notorious problem in automata theory. As far as I know, this vast generalization of Černý's conjecture has not yet been refuted.
This post is based on a STACS'19 paper, where more details can be found.
Comments
Post a Comment