Decidability of strict stability for rational matrix families
Let $\widehat\rho(\mathcal M)$ be the joint spectral radius of a finite set $\mathcal M$ of real square matrices and $\rho$ the spectral radius. The condition $\widehat\rho(\mathcal M) < 1$ is stability of the switched linear system $x_{t+1} = A_t x_t$, $A_t \in \mathcal M$. With $P$ ranging over the products of $t$ matrices from $\mathcal M$ and $\|\cdot\|$ an operator norm, answering yes once $\max_P \|P\|^{1/t} < 1$ and no once $\max_P \rho(P)^{1/t} \ge 1$, for $t = 1, 2, \dots$, gives the correct answer after finitely many steps unless $\widehat\rho(\mathcal M) = 1$ and $\rho(P)^{1/t} < 1$ for every $t$ and every such $P$. So stability is decidable for sets with $\widehat\rho(\mathcal M) = \rho(A_k \cdots A_1)^{1/k}$ for some $A_1, \dots, A_k \in \mathcal M$ (Jungers and Blondel). Blondel and Tsitsiklis proved that it is undecidable whether $\widehat\rho(\mathcal M) \le 1$, even for pairs of matrices with rational entries.
Problem. Is there an algorithm (a Turing machine) that, given $d \ge 1$ and a finite nonempty list $\mathcal M$ of matrices in $\mathbb{Q}^{d \times d}$, with entries encoded by binary integer numerators and positive denominators, always halts and correctly decides whether $\widehat\rho(\mathcal M) < 1$? The dimension and the length of the list are part of the input, no separation of $\widehat\rho(\mathcal M)$ from $1$ is promised, and no polynomial bound on the running time is required.
Source: Blondel and Tsitsiklis (1999), Open Problem 2 (for each dimension and number of matrices); as one algorithm for all finite sets, Jungers (2009), §2.2.3, Open Question 1 (already in his 2008 thesis). Rational entries in binary are fixed by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- DS — Dynamical Systems
- Secondary
- NA, OC
- Keywords
- decidability, joint spectral radius, OpenProblemsInNLA, switched linear systems
- Literature checked
- Oct. 7, 2026 by clemens-admin
References
@incollection{blondel1999,
author = {Blondel, Vincent D. and Tsitsiklis, John N.},
title = {Three problems on the decidability and complexity of stability},
booktitle = {Open Problems in Mathematical Systems and Control Theory},
editor = {Blondel, Vincent and Sontag, Eduardo D. and Vidyasagar, Mathukumalli and Willems, Jan C.},
series = {Communications and Control Engineering},
publisher = {Springer},
address = {London},
year = {1999},
pages = {45--51},
doi = {10.1007/978-1-4471-0807-8_11},
}
@book{jungers2009,
author = {Jungers, Rapha{\"e}l},
title = {The Joint Spectral Radius: Theory and Applications},
series = {Lecture Notes in Control and Information Sciences},
volume = {385},
publisher = {Springer},
address = {Berlin},
year = {2009},
doi = {10.1007/978-3-540-95980-9},
}
@article{jungers2008,
author = {Jungers, Rapha{\"e}l M. and Blondel, Vincent D.},
title = {On the finiteness property for rational matrices},
journal = {Linear Algebra Appl.},
volume = {428},
number = {10},
year = {2008},
pages = {2283--2295},
doi = {10.1016/j.laa.2007.07.007},
eprint = {math/0702489},
archivePrefix = {arXiv},
}
@article{blondel2000,
author = {Blondel, Vincent D. and Tsitsiklis, John N.},
title = {The boundedness of all products of a pair of matrices is undecidable},
journal = {Systems Control Lett.},
volume = {41},
number = {2},
year = {2000},
pages = {135--140},
doi = {10.1016/S0167-6911(00)00049-9},
}
@misc{openproblemsinnla-mf09,
author = {Townsend, Alex},
title = {{MF-09}: Decidability of strict stability for rational matrix families},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/matrix-functions-and-stability/MF-09/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00162, "Decidability of strict stability for rational matrix families", clopen.solutions.