The boundedness of all products of a pair of matrices is undecidable

DOI10.1016/S0167-6911(00)00049-9zbMath0985.93042OpenAlexW1991656001WikidataQ127740387 ScholiaQ127740387MaRDI QIDQ1583220

Blondel, Vincent D., John N. Tsitsiklis

Publication date: 26 October 2000

Published in: Systems \& Control Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6911(00)00049-9

zbMATH Keywords

linear time-varying systems decidability joint spectral radius computability matrix semigroup finiteness conjecture robust stability analysis generalised spectral radius problem complexity

Mathematics Subject Classification ID

Robust stability (93D09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Polynomially ambiguous probabilistic automata on restricted languages, Lower bounds on complexity of Lyapunov functions for switched linear systems, When is a pair of matrices mortal?, Reachability analysis of quantum Markov decision processes, PERIODIC SEQUENCES OF ARBITRAGE: A TALE OF FOUR CURRENCIES, Deciding the boundedness and dead-beat stability of constrained switching systems, On the decidability of semigroup freeness, The generalized spectral radius and extremal norms, An inequality for the matrix pressure function and applications, It is undecidable whether the growth rate of a given bilinear system is 1, Matrix semigroups with constant spectral radius, Collision-free second-order vehicle formation control under time-varying network topology, Positive recurrence of piecewise Ornstein-Uhlenbeck processes and common quadratic Lyapunov functions, On codes with local joint constraints, On the $m$-dimensional Cayley-Hamilton theorem and its application to an algebraic decision problem inferred from the $\mathcal{H}_2$ norm analysis of delay systems, Stochastic stability of switching linear systems with application to an automotive powertrain model, Tight bound for deciding convergence of consensus systems, Marginally unstable discrete-time linear switched systems with highly irregular trajectory growth, Convergence of the Nelder-Mead method, On random walks and switched random walks on homogeneous spaces, Some criteria for spectral finiteness of a finite subset of the real matrix space $\mathbb R^{d\times d}$, A Stability Dichotomy for Discrete-Time Linear Switching Systems in Dimension Two, Spectrum Maximizing Products Are Not Generically Unique, On continuous weighted finite automata, The membership problem for subsemigroups of $\operatorname{GL}_2(\mathbb{Z})$ is \textbf{NP}-complete, Rank-one characterization of joint spectral radius of finite matrix family, Lower bounds and dense discontinuity phenomena for the stabilizability radius of linear switched systems, $l_p$ Analysis and Synthesis of Linear Switched Systems: A Unified Input-Output and State-Space Approach, Set of possible values of maximal Lyapunov exponents of discrete time-varying linear system, On the marginal instability of linear switched systems, Almost sure convergence of observers for switched linear systems, Certifying Unstability of Switched Systems Using Sum of Squares Programming, Polynomial Norms, A Gel'fand-type spectral radius formula and stability of linear constrained switching systems, Uniformity of Lyapunov exponents for non-invertible matrices, On the Lyapunov exponents of a class of second-order discrete time linear systems with bounded perturbations, Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture, 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, Corrigendum/addendum to: Sets of matrices all infinite products of which converge, Sampled fictitious play for approximate dynamic programming, Chaotic behavior of discrete-time linear inclusion dynamical systems, A gap result for the norms of semigroups of matrices, When do several linear operators share an invariant cone?, On deciding stability of multiclass queueing networks under buffer priority scheduling policies, Invariant Polytopes of Sets of Matrices with Application to Regularity of Wavelets and Subdivisions, ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS, Consensus in asynchronous multiagent systems. III: Constructive stability and stabilizability, The Invariance Problem for Matrix Semigroups, A tree-based approach to joint spectral radius determination, Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution, Computable analysis with applications to dynamic systems, The outer spectral radius and dynamics of completely positive maps, Polynomially Ambiguous Probabilistic Automata on Restricted Languages, Decidability and $k$-regular sequences, On the joint spectral radius of nonnegative matrices, Extremal norms for fiber-bunched cocycles, Trajectory-dependent filter design for discrete-time switched linear systems, The stability of the deterministic Skorokhod problem is undecidable, $C^2$ subdivision over triangulations with one extraordinary point

Cites Work