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

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)less than or equal to1 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. (C) 2000 Elsevier Science B.V. All rights reserved