User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

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

Primary tabs

Jungers, Raphaël M. [UCL] Protasov, Vladimir Blondel, Vincent [UCL]

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.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2008
Language Anglais
Journal information "Linear Algebra and Its Applications" - Vol. 428, no. 10, p. 2296-2311 (2008)
Peer reviewed yes
Publisher Elsevier Science Inc (New York)
issn 0024-3795
e-issn 1873-1856
Publication status Publié
Affiliation UCL - FSA/INMA - Département d'ingénierie mathématique
Keywords joint spectral radius ; integer matrices ; binary matrices ; semigroup of matrices ; bounded semigroup
Links
Bibliographic reference Jungers, Raphaël M. ; Protasov, Vladimir ; Blondel, Vincent. Efficient algorithms for deciding the type of growth of products of integer matrices. In: Linear Algebra and Its Applications, Vol. 428, no. 10, p. 2296-2311 (2008)
Permanent URL http://hdl.handle.net/2078.1/36651