The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
From MaRDI portal
Publication:1367098
DOI10.1007/BF01219774zbMath0888.65044OpenAlexW1978242229MaRDI QIDQ1367098
John N. Tsitsiklis, Blondel, Vincent D.
Publication date: 12 May 1998
Published in: MCSS. Mathematics of Control, Signals, and Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01219774
Analysis of algorithms and problem complexity (68Q25) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Eigenvalues, singular values, and eigenvectors (15A18) Complexity and performance of numerical algorithms (65Y20) Matrices of integers (15B36)
Related Items (96)
Estimates for the joint spectral radius ⋮ Reachability analysis of quantum Markov decision processes ⋮ PERIODIC SEQUENCES OF ARBITRAGE: A TALE OF FOUR CURRENCIES ⋮ Overlap-free words and spectra of matrices ⋮ The Tendency toward a Moving Equilibrium ⋮ Lyapunov exponents for branching processes in a random environment: the effect of information ⋮ The generalized spectral radius and extremal norms ⋮ Multigrid at Scale? ⋮ An inequality for the matrix pressure function and applications ⋮ Shortest positive products of nonnegative matrices ⋮ Falseness of the Finiteness Property of the Spectral Subradius ⋮ It is undecidable whether the growth rate of a given bilinear system is 1 ⋮ Stability of shuffled switched linear systems: A joint spectral radius approach ⋮ Matrix semigroups with constant spectral radius ⋮ Multivariate refinement equation with nonnegative masks ⋮ A Note on Riccati Matrix Difference Equations ⋮ Asymptotics of products of nonnegative random matrices ⋮ An experimental study of approximation algorithms for the joint spectral radius ⋮ On codes with local joint constraints ⋮ \(p\)-dominant switched linear systems ⋮ A rapidly-converging lower bound for the joint spectral radius via multiplicative ergodic theory ⋮ Robust periodic stability implies uniform exponential stability of Markovian jump linear systems and random linear ordinary differential equations ⋮ Performance analysis of asynchronous parallel Jacobi ⋮ Equivalence of several characteristics of dual switched linear systems ⋮ Antinorms on cones: duality and applications ⋮ Antinorms and self-polar polyhedra ⋮ Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated ⋮ Necessary and Sufficient Conditions for Template-Dependent Ordering of Path-Complete Lyapunov Methods ⋮ Convergent bivariate subdivision scheme with nonnegative mask whose support is non-convex ⋮ Optimal Switching Sequence for Switched Linear Systems ⋮ On primitivity of sets of matrices ⋮ Spectrum Maximizing Products Are Not Generically Unique ⋮ Intrinsic stability: stability of dynamical networks and switched systems with any type of time-delays ⋮ Sets of nonnegative matrices without positive products ⋮ Exact computation of joint spectral characteristics of linear operators ⋮ An explicit counterexample to the Lagarias-Wang finiteness conjecture ⋮ Lower bounds and dense discontinuity phenomena for the stabilizability radius of linear switched systems ⋮ Almost sure convergence of observers for switched linear systems ⋮ Polytopic uncertainty for linear systems: new and old complexity results ⋮ On the entropy of a hidden Markov process ⋮ Necessary conditions for the convergence of subdivision schemes with finite masks ⋮ Windows of opportunity for the stability of jump linear systems: almost sure versus moment convergence ⋮ On multivariate subdivision schemes with nonnegative finite masks ⋮ A new characterization of convergent multivariate subdivision schemes with nonnegative masks ⋮ A limit formula for joint spectral radius with \(p\)-radius of probability distributions ⋮ Subdivision schemes with nonnegative masks ⋮ Generic properties of the lower spectral radius for some low-rank pairs of matrices ⋮ A survey of computational complexity results in systems and control ⋮ Random matrix products and applications to cellular automata ⋮ Some sufficient conditions for convergent multivariate subdivision schemes with nonnegative finite masks ⋮ A new computable sufficient condition for the convergence of subdivision schemes with nonnegative masks ⋮ Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture ⋮ An algorithm for finding extremal polytope norms of matrix families ⋮ On the finiteness property for rational matrices ⋮ Efficient algorithms for deciding the type of growth of products of integer matrices ⋮ Optimal norms and the computation of joint spectral radius of matrices ⋮ Approximation of the joint spectral radius using sum of squares ⋮ Is the Multigrid Method Fault Tolerant? The Two-Grid Case ⋮ Corrigendum/addendum to: Sets of matrices all infinite products of which converge ⋮ Continuity properties of the lower spectral radius ⋮ On the accuracy of the ellipsoid norm approximation of the joint spectral radius ⋮ Chaotic behavior of discrete-time linear inclusion dynamical systems ⋮ An upper bound for the largest Lyapunov exponent of a Markovian product of nonnegative matrices ⋮ Uniform stabilization of discrete-time switched and Markovian jump linear systems ⋮ When do several linear operators share an invariant cone? ⋮ On the joint spectral radius of matrices of order 2 with equal spectral radius ⋮ Construction of invariant Lyapunov norms of planar dynamical systems ⋮ Robust stability of polytopic time-inhomogeneous Markov jump linear systems ⋮ Criteria for the stability of the finiteness property and for the uniqueness of Barabanov norms ⋮ A new inequality about matrix products and a Berger-Wang formula ⋮ Zeno chattering of rigid bodies with multiple point contacts ⋮ Consensus in asynchronous multiagent systems. III: Constructive stability and stabilizability ⋮ Multivariate contemporaneous-threshold autoregressive models ⋮ Anti-windup strategies for discrete-time switched systems subject to input saturation ⋮ Generalized Input-to-State $\ell_2$-Gains of Discrete-Time Switched Linear Control Systems ⋮ Towards a Unified Approach for Proving Geometric Ergodicity and Mixing Properties of Nonlinear Autoregressive Processes ⋮ Characterization of some convergent bivariate subdivision schemes with nonnegative masks ⋮ Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution ⋮ The outer spectral radius and dynamics of completely positive maps ⋮ Fault tolerant control design for a class of multi-sensor networked control systems ⋮ Effective estimates on the top Lyapunov exponents for random matrix products ⋮ Markovian Trees Subject to Catastrophes: Would They Survive Forever? ⋮ On the joint spectral radius of nonnegative matrices ⋮ Feedback stabilization of discrete-time homogeneous semi-linear systems ⋮ Non-Sturmian sequences of matrices providing the maximum growth rate of matrix products ⋮ Finiteness property of pairs of \(2\times 2\) sign-matrices via real extremal polytope norms ⋮ The finiteness conjecture holds in (SL2Z⩾0)2 * ⋮ The boundedness of all products of a pair of matrices is undecidable ⋮ Temporal interactions facilitate endemicity in the susceptible-infected-susceptible epidemic model ⋮ A characterization of convex cones of matrices with constant regular inertia ⋮ Matrix concentration for products ⋮ Fast Approximation of the $p$-Radius, Matrix Pressure, or Generalized Lyapunov Exponent for Positive and Dominated Matrices ⋮ CLT with explicit variance for products of random singular matrices related to Hill’s equation ⋮ Stability of Linear Problems: Joint Spectral Radius of Sets of Matrices ⋮ Switching between stabilizing controllers ⋮ Subdivision schemes, network flows and linear optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- When is a pair of matrices mortal?
- Power law scaling of the top Lyapunov exponent of a product of random matrices
- Algebraic unsolvability of problem of absolute stability of desynchronized systems
- Sets of matrices all infinite products of which converge
- Bounded semigroups of matrices
- Lyapunov exponents. Proceedings of a conference, held in Oberwolfach, Germany, May 28-June 2, 1990
- Subadditive ergodic theory
- The finiteness conjecture for the generalized spectral radius of a set of matrices
- An upper bound for the largest Lyapunov exponent of a Markovian product of nonnegative matrices
- The generalized spectral-radius theorem: An analytic-geometric proof
- Stability of discrete linear inclusion
- Computing the joint spectral radius
- Matrix Analysis
- On the stability of asynchronous iterative processes
- The Complexity of Markov Decision Processes
- Subadditivity, Generalized Products of Random Matrices and Operations Research
- Constructive stability and asymptotic stability of dynamical systems
- Linear Matrix Inequalities in System and Control Theory
- NP-Hardness of Some Linear Control Design Problems
- Exact Lyapunov exponent for infinite products of random matrices
- Unsolvability in 3 × 3 Matrices
- The biennial life strategy in a random environment
This page was built for publication: The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
