Efficient algorithms for deciding the type of growth of products of integer matrices (Q2483266)

For a given set \(\Sigma\) of matrices, the joint spetral radius of \(\Sigma\), denoted \(\rho(\Sigma)\), is defined by the limit \(\rho(\Sigma)=\lim_{t\rightarrow \infty}\max\{\| A_1\cdots A_t\| ^{1/t}: A_t\in\Sigma\}\) independently of any norm. For any finite set \(\Sigma\) of \(n\times n\) matrices with nonnegative integer entries, the authors show that there is a polynomial algorithm that decides between the four cases: \(\rho=0\), \(\rho=1\) and bounded, \(\rho=1\) and polynomial growth, and \(\rho>1\). The polynomial solvability for \(\rho>1\) is somewhat surprising.