The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
type: Item
instance of: scholarly article
title: The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
zbMATH Open document ID: 0888.65044
DOI: 10.1007/BF01219774
author: John N. Tsitsiklis
author: Vincent D. Blondel
published in: MCSS. Mathematics of Control, Signals, and Systems
publication date: 1998-05-12T00:00:00Z
review text: The authors show that the joint spectral radius and the generalized spectral radius of two integer matrices are not approximable in polynomial time, and that two related quantities -- the lower spectral radius and the largest Lyapunov exponent -- are not algorithmically approximable. Some applications of these results are discussed.
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 15A18
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1062600
zbMATH Keywords: Lyapunov exponent
zbMATH Keywords: joint spectral radius
zbMATH Keywords: generalized spectral radius
zbMATH Keywords: computational complexity
reviewed by: Alan L. Andrew
MaRDI profile type: Publication
cites work: Lyapunov exponents. Proceedings of a conference, held in Oberwolfach, Germany, May 28-June 2, 1990
cites work: Bounded semigroups of matrices
cites work: When is a pair of matrices mortal?
cites work: NP-Hardness of Some Linear Control Design Problems
cites work: Linear Matrix Inequalities in System and Control Theory
cites work: Constructive stability and asymptotic stability of dynamical systems
cites work: Subadditivity, Generalized Products of Random Matrices and Operations Research
cites work: Q3721532
cites work: Q3979037
cites work: Sets of matrices all infinite products of which converge
cites work: The generalized spectral-radius theorem: An analytic-geometric proof
cites work: Q4198056
cites work: An upper bound for the largest Lyapunov exponent of a Markovian product of nonnegative matrices
cites work: Computing the joint spectral radius
cites work: Stability of discrete linear inclusion
cites work: Q5592246
cites work: Matrix Analysis
cites work: Subadditive ergodic theory
cites work: Algebraic unsolvability of problem of absolute stability of desynchronized systems
cites work: The finiteness conjecture for the generalized spectral radius of a set of matrices
cites work: Exact Lyapunov exponent for infinite products of random matrices
cites work: Q5646734
cites work: Q4298260
cites work: The Complexity of Markov Decision Processes
cites work: Unsolvability in 3 × 3 Matrices
cites work: Power law scaling of the top Lyapunov exponent of a product of random matrices
cites work: The biennial life strategy in a random environment
cites work: Q3272731
cites work: On the stability of asynchronous iterative processes
full work available at URL: https://doi.org/10.1007/bf01219774
OpenAlex ID: W1978242229
description: scientific article; zbMATH DE number 1062600