𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Vincent D. Blondel; John N. Tsitsiklis

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
97 KB
Volume
41
Category
Article
ISSN
0167-6911

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the boundedness of the set of all products of a given pair of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius ( ) is not computable because testing whether ( )61 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 "ΓΏniteness conjecture". Our results are based on a simple reduction from the emptiness problem for probabilistic ΓΏnite automata, which is known to be undecidable.

πŸ“œ SIMILAR VOLUMES

When is a pair of matrices mortal?
When is a pair of matrices mortal?
✍ Vincent D. Blondel; John N. Tsitsiklis πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 379 KB

A set of matrices over the integers is said to be k-morrul (with k positive integer) if the zero matrix can be expressed as a product of length k of matrices in the set. The set is said to be mortal if it is k-mortal for some finite k. We show that the problem of deciding whether a pair of 48 x 48 i

A conjecture concerning the Hadamard pro
A conjecture concerning the Hadamard product of inverses of M-matrices
✍ M. Neumann πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 804 KB

We conjecture that for an n x n matrix A which is an inverse of an M-matrix, the Hadamard product A o A is also an inverse of an M-matrix. We have checked this conjecture without failure on many many examples. But here we show that for quite a few well known classes of inverses of M-matrices, the co