On nonnegative integer matrices and short killing words
Let n be a natural number, and let \scrM be a set of n\times n-matrices over the nonnegative integers such that the joint spectral radius of \scrM is at most one. We show that if the zero matrix 0 is a product of matrices in \scrM , then there are M1, . . . , Mn5 \in \scrM with M1 \cdot \cdot \cdot...
Main Authors: | , |
---|---|
Format: | Journal article |
Language: | English |
Published: |
Society for Industrial and Applied Mathematics
2021
|
Summary: | Let n be a natural number, and let \scrM be a set of n\times n-matrices over the nonnegative integers such that the joint spectral radius of \scrM is at most one. We show that if the zero matrix 0 is a product of matrices in \scrM , then there are M1, . . . , Mn5 \in \scrM with M1 \cdot \cdot \cdot Mn5 = 0. This result has applications in automata theory and the theory of codes. Specifically, if X \subset \Sigma \ast is a finite incomplete code, then there exists a word w \in \Sigma \ast of length polynomial in \sum x\in X | x| such that w is not a factor of any word in X\ast . This proves a weak version of Restivo's conjecture. |
---|