CHECKING ROBUST NONSINGULARITY IS NP-HARD

We consider the following problem: given k + 1 square matrices with rational 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 closely related to the robust stability problem, is NP-hard. The proof relies on the new concept of radius of nonsingularity of a square matrix and on the relationship between computing this radius and a graph-theoretic problem.