Skip to main content

Short Killing Words

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:
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

Popular posts from this blog

Tell me the price of memory and I give you €100

Markov Decision Processes (MDPs) are Markov chains plus nondeterminism: some states are random, the others are controlled (nondeterministic). In the pictures, the random states are round, and the controlled states are squares: The random states (except the brown sink state) come with a probability distribution over the successor states. In the controlled states, however, a controller chooses a successor state. What does the controller want to achieve? That depends. In this blog post, the objective is very simple: take a red transition . The only special thing about red transitions is that the controller wants to take them. We consider only MDPs with the following properties: There are finitely many states and transitions. The MDP is acyclic, that is, it has no cycles. There are a unique start state from which any run starts (in the pictures: blue, at the top) and a unique sink state where any run ends (in the pictures: brown, at the bottom). No matter what the controller does,

Calibrating Assessments

Last year I wrote a post on how Oxford selects undergraduate students for computer science. Oxford undergraduate admissions are politically charged: the British public suspects that Oxbridge is biased towards privileged applicants. This post is unpolitical though. I'm advocating a better way of solving a typical problem in academia: you have many candidates (think: papers, grant proposals, or Oxford applicants) and few assessors (think: members of program committees, assessment panels, or admission tutors), and the goal of the assessors is to select the best candidates. Since there are many candidates, each assessor can assess only some candidates. From a candidate's point of view: a paper may get 3 reviews, a grant proposal perhaps 5, and a shortlisted Oxford applicant may get 3 interviews. Each such review comes with a score that reflects the assessor's estimate of the candidate's quality. The problem is that different assessors will score the same candidate differ