On Nonnegative Integer Matrices and Short Killing Words

Let $n$ be a natural number and $\mathcal{M}$ a set of $n\times n$-matrices over the nonnegative integers such that the joint spectral radius of $\mathcal{M}$ is at most one. We show that if the zero matrix $0$ is a product of matrices in $\mathcal{M}$, then there are $M_1, \ldots, M_{n^5} \in $\mathcal{M}$$with$M_1 \cdots M_{n^5} = 0$. This result has applications in automata theory and the theory of codes. Specifically, if $X\subset {\mathrm{\Sigma }}^{\ast }$ is a finite incomplete code, then there exists a word $w\in {\mathrm{\Sigma }}^{\ast }$ of length polynomial in ${\sum }_{x\in X}\mathrm{\mid }x\mathrm{\mid }$ such that $w$ is not a factor of any word in $X^{\ast }$. This proves a weak version of Restivo’s conjecture.