THE LYAPUNOV-EXPONENT AND JOINT SPECTRAL-RADIUS OF PAIRS OF MATRICES ARE HARD - WHEN NOT IMPOSSIBLE - TO COMPUTE AND TO APPROXIMATE

Authors
TSITSIKLIS JN BLONDEL VD
Citation
Jn. Tsitsiklis et Vd. Blondel, THE LYAPUNOV-EXPONENT AND JOINT SPECTRAL-RADIUS OF PAIRS OF MATRICES ARE HARD - WHEN NOT IMPOSSIBLE - TO COMPUTE AND TO APPROXIMATE, MCSS. Mathematics of control, signals and systems, 10(1), 1997, pp. 31-40
Citations number
35
Categorie Soggetti
Controlo Theory & Cybernetics","Engineering, Eletrical & Electronic",Mathematics,"Robotics & Automatic Control
Journal title
MCSS. Mathematics of control, signals and systems → ACNP
ISSN journal
09324194
Volume
10
Issue
1
Year of publication
1997
Pages
31 - 40
Database
ISI
SICI code
0932-4194(1997)10:1<31:TLAJSO>2.0.ZU;2-T
Abstract
We analyze the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and ge neralized spectral radii of two integer matrices are not approximable iu polynomial time, and that two related quantities-the lower spectral radius and the largest Lyapunov exponent-are not algorithmically appr oximable.