2008 • Journal Article
Efficient algorithms for deciding the type of growth of products of integer matrices
Authors:
Jungers, Raphaël M. ,
Protasov, Vladimir,
Blondel, Vincent
Published in:
Linear Algebra and Its Applications
Volume: 428 • Number: 10 • Pages: 2296-2311
For a given finite set Sigma of matrices with nonnegative integer entries we study the growth with t of max {parallel to A(1)... A(t)parallel to : A(i) epsilon Sigma}. We show how to determine in polynomial time whether this growth is bounded, polynomial, or exponential, and we characterize all possible behaviors. (c) 2007 Elsevier Inc. All rights reserved.