CHECKING ROBUST NONSINGULARITY IS NP-HARD

Authors
POLJAK S ROHN J
Citation
S. Poljak et J. Rohn, CHECKING ROBUST NONSINGULARITY IS NP-HARD, MCSS. Mathematics of control, signals and systems, 6(1), 1993, pp. 1-9
Citations number
16
Categorie Soggetti
Controlo Theory & Cybernetics","Engineering, Eletrical & Electronic",Mathematics,"Computer Applications & Cybernetics
Journal title
MCSS. Mathematics of control, signals and systems → ACNP
ISSN journal
09324194
Volume
6
Issue
1
Year of publication
1993
Pages
1 - 9
Database
ISI
SICI code
0932-4194(1993)6:1<1:CRNIN>2.0.ZU;2-N
Abstract
We consider the following problem: given k + 1 square matrices with ra tional entries, A0, A1, ..., A(k), decide if A0 + r1A1 + ... + r(k)A(k ) is nonsingular for all possible choices of real numbers r1, ..., r(k ), in the interval [0, 1]. We show that this question, which is closel y related to the robust stability problem, is NP-hard. The proof relie s on the new concept of radius of nonsingularity of a square matrix an d on the relationship between computing this radius and a graph-theore tic problem.