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
基金
美国国家科学基金会;
关键词
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].
BERGER, MA ;
WANG, Y .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1992, 166 :21-27
[2]   When is a pair of matrices mortal? [J].
Blondel, VD ;
Tsitsiklis, JN .
INFORMATION PROCESSING LETTERS, 1997, 63 (05) :283-286
[3]   A survey of computational complexity results in systems and control [J].
Blondel, VD ;
Tsitsiklis, JN .
AUTOMATICA, 2000, 36 (09) :1249-1274
[4]   Complexity of stability and controllability of elementary hybrid systems [J].
Blondel, VD ;
Tsitsiklis, JN .
AUTOMATICA, 1999, 35 (03) :479-489
[5]   COMPUTATIONAL-COMPLEXITY OF MU-CALCULATION [J].
BRAATZ, RP ;
YOUNG, PM ;
DOYLE, JC ;
MORARI, M .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1994, 39 (05) :1000-1002
[6]  
CONDON A, 1989, COMPLEXITY SPACE BOU
[7]  
Condon Anne, 1989, P 30 ANN S FDN COMP, P462
[8]   SETS OF MATRICES ALL INFINITE PRODUCTS OF WHICH CONVERGE [J].
DAUBECHIES, I ;
LAGARIAS, JC .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1992, 161 :227-263
[9]  
GURVITS L, 1995, LINEAR ALGEBRA APPL, V231, P47, DOI 10.1016/0024-3795(94)00010-7
[10]  
GURVITS L, 1996, 96173 TR