Efficient algorithms for deciding the type of growth of products of integer matrices

Jungers, Raphaël; Protasov, Vladimir; Blondel, Vincent D.

Efficient algorithms for deciding the type of growth of products of integer matrices

Authors

Jungers, Raphaël

Protasov, Vladimir

Blondel, Vincent D.

Description

For a given finite set $Σ$ of matrices with nonnegative integer entries we study the growth of $$ \max_t(Σ) = \max\{\|A_{1}... A_{t}\|: A_i \in Σ\}.$$ We show how to determine in polynomial time whether the growth with $t$ is bounded, polynomial, or exponential, and we characterize precisely all possible behaviors.
20 pages, 4 figures, submitted to LAA