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

DOI10.1016/j.laa.2007.08.001zbMath1145.65030OpenAlexW1622830285MaRDI QIDQ2483266

Raphaël M. Jungers, Vladimir Yu. Protasov, Blondel, Vincent D.

Publication date: 28 April 2008

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2007.08.001

zbMATH Keywords

binary matricesinteger matricespolynomial algorithmjoint spectral radiussemigroup of matricesbounded semigroup

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Eigenvalues, singular values, and eigenvectors (15A18) Matrices of integers (15B36)

Related Items

Growth degree classification for finitely generated semigroups of integer matrices, Lower bounds on complexity of Lyapunov functions for switched linear systems, The greedy strategy for optimizing the Perron eigenvalue, Overlap-free words and spectra of matrices, Matrix semigroups with constant spectral radius, On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers, Marginally unstable discrete-time linear switched systems with highly irregular trajectory growth, Computing the spectral gap of a family of matrices, Resonance and marginal instability of switching systems, A note on the marginal instability rates of two-dimensional linear cocycles, A Stability Dichotomy for Discrete-Time Linear Switching Systems in Dimension Two, On the asymptotic regularity of a family of matrices, Sets of nonnegative matrices without positive products, Exact computation of joint spectral characteristics of linear operators, The Euler binary partition function and subdivision schemes, On asymptotic properties of matrix semigroups with an invariant cone, On the marginal instability of linear switched systems, Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems, Matrix products with constraints on the sliding block relative frequencies of different factors, On the finiteness property for rational matrices, Observable graphs, FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME, On the computation of covert channel capacity, Consensus in asynchronous multiagent systems. III: Constructive stability and stabilizability, Unnamed Item, On finite monoids over nonnegative integer matrices and short killing words, On Nonnegative Integer Matrices and Short Killing Words, Non-Sturmian sequences of matrices providing the maximum growth rate of matrix products, Linear switching systems with slow growth of trajectories, On infinite words determined by L systems, Spectral simplex method

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A gap result for the norms of semigroups of matrices
• Sur les courbes limités de polygones obtenus par trisection
• On codes with local joint constraints
• Structure of extremal trajectories of discrete linear systems and the finiteness conjecture
• Bounded semigroups of matrices
• The Burnside problem for semigroups
• On finite semigroups of matrices
• Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices
• The generalized spectral radius and extremal norms
• The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
• Undecidable problems for probabilistic automata of fixed dimension
• The boundedness of all products of a pair of matrices is undecidable
• Interpolation through an iterative scheme
• Characterization of tile digit sets with prime determinants
• Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture
• On the Complexity of Computing the Capacity of Codes That Avoid Forbidden Difference Patterns
• Simple Regularity Criteria for Subdivision Schemes
• Two-Scale Difference Equations II. Local Regularity, Infinite Products of Matrices and Fractals
• Characterizations of Scaling Functions: Continuous Solutions
• The generalized joint spectral radius. A geometric approach
• An Elementary Counterexample to the Finiteness Conjecture
• Asymptotic behaviour of the partition function
• On codes that avoid specified differences
• Computationally Efficient Approximations of the Joint Spectral Radius
• Fractal curves and wavelets
• Depth-First Search and Linear Graph Algorithms
• A survey of computational complexity results in systems and control