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

被引：135

作者：

Blondel, VD

Tsitsiklis, JN

机构：

[1] Univ Catholique Louvain, Ctr CESAME, Div Appl Math, B-1348 Louvain, Belgium

[2] MIT, Informat & Decis Syst Lab, Cambridge, MA 02139 USA

来源：

SYSTEMS & CONTROL LETTERS | 2000年 / 41卷 / 02期

基金：

美国国家科学基金会;

关键词：

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

D O I：

10.1016/S0167-6911(00)00049-9

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：135 / 140

页数：6

共 24 条

[1] BOUNDED SEMIGROUPS OF MATRICES [J].