zbMATH — the first resource for mathematics

The boundedness of all products of a pair of matrices is undecidable. (English) Zbl 0985.93042
Summary: We show that the boundedness of the set of all products of a given pair \(\Sigma\) of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius \(\rho(\Sigma)\) is not computable because testing whether \(\rho(\Sigma)<1\) is an undecidable problem. As a consequence, the robust stability of linear systems under time-varying perturbations is undecidable, and the same is true for the stability of a simple class of hybrid systems. We also discuss some connections with the so-called “finiteness conjecture”. Our results are based on a simple reduction from the emptiness problem for probabilistic finite automata, which is known to be undecidable.

93D09 Robust stability
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI
[1] Berger, M.; Wang, Y., Bounded semigroups of matrices, Linear algebra appl., 166, 21-27, (1992) · Zbl 0818.15006
[2] Blondel, V.D.; Tsitsiklis, J.N., When is a pair of matrices mortal? informat. process. lett., 63, 283-286, (1997) · Zbl 1337.68123
[3] Blondel, V.D.; Tsitsiklis, J.N., Complexity of stability and controllability of elementary hybrid systems, Automatica, 35, 479-489, (1999) · Zbl 0943.93044
[4] V.D. Blondel, J.N. Tsitsiklis, A survey of computational complexity results in systems and control, Automatica 36(9) (2000) 1249-1274. · Zbl 0989.93006
[5] Braatz, R.; Young, P.; Doyle, J.; Morari, M., Computational complexity of μ calculation, IEEE trans. automat. control, 39, 1000-1002, (1994) · Zbl 0807.93020
[6] A. Condon, R.J. Lipton, On the complexity of space bounded interactive proofs, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, NC, 1989, pp. 462-467.
[7] A. Condon, R.J. Lipton, On the complexity of space bounded interactive proofs, unpublished Technical Report, 1989.
[8] Daubechies, I.; Lagarias, J.C., Sets of matrices all infinite products of which converge, Linear algebra appl., 162, 227-263, (1992) · Zbl 0746.15015
[9] Gurvits, L., Stability of discrete linear inclusions, Linear algebra appl., 231, 47-85, (1995) · Zbl 0845.68067
[10] L. Gurvits, Stability of linear inclusions - Part 2, Technical Report TR 96-173, NEC Research, 1996.
[11] Jacob, G., An algorithm for calculating the cardinal, finite or infinite, of the semigroups of matrices, Theoret. comput. sci., 5, 183-204, (1977)
[12] Kozyakin, V.S., Algebraic unsolvability of problem of absolute stability of desynchronized systems, Automat. remote control, 51, 754-759, (1990) · Zbl 0737.93056
[13] Lagarias, J.C.; Wang, Y., The finiteness conjecture for the generalized spectral radius of a set of matrices, Linear algebra appl., 214, 17-42, (1995) · Zbl 0818.15007
[14] Madani, O., On the computability of infinite-horizon partially observable Markov decision processes, AAAI98 fall symposium on planning with pomdps, (1998), Orlando FL
[15] Madani, O.; Hanks, S.; Condon, A., On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems, Proceedings of the sixteenth national conference on artificial intelligence, (July 1999), Orlando FL
[16] Nemirovskii, A., Several NP-hard problems arising in robust stability analysis, Math. control signals systems, 63, 99-105, (1993) · Zbl 0792.93100
[17] Paz, A., Introduction to probabilistic automata, (1971), Academic Press New York · Zbl 0234.94055
[18] Poljak, S.; Rohn, J., Checking robust nonsingularity is NP-hard, Math. control signals systems, 6, 1-9, (1993) · Zbl 0780.93027
[19] Rota, G.-C.; Strang, G., A note on the joint spectral radius, Nederl. akad. wetensch. indagationes math., 22, 379-381, (1960) · Zbl 0095.09701
[20] Toker, O., On the complexity of the robust stability problem for linear parameter varying systems, Automatica, 33, 2015-2017, (1997) · Zbl 0914.93046
[21] Toker, O.; Ozbay, H., On the complexity of purely complex μ computation and related problems in multidimensional systems, IEEE trans. automat. control, 43, 409-414, (1998) · Zbl 0905.93018
[22] Tsitsiklis, J.N., On the stability of asynchronous iterative processes, Math. systems theory, 20, 137-153, (1987) · Zbl 0637.65056
[23] Tsitsiklis, J.N., The stability of the products of a finite set of matrices, (), 161-163
[24] Tsitsiklis, J.N.; Blondel, V.D., The Lyapunov exponent and joint spectral radius of pairs of matrices are hard – when not impossible – to compute and to approximate, Math. control signals systems, 10, 31-40, (1997) · Zbl 0888.65044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.