×

Checking robust nonsingularity is NP-hard. (English) Zbl 0780.93027

Summary: We consider the following problem: given \(k+1\) square matrices with rational entries, \(A_ 0,A_ 1,\dots,\) \(A_ k\), decide if \(A_ 0+r_ 1 A_ 1+\cdots +r_ k A_ k\) is nonsingular for all possible choices of real numbers \(r_ 1,\dots,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.

MSC:

93B35 Sensitivity (robustness)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] F. Barahona, A solvable case of quadratic 0-1 programming,Discrete Appl. Math.,13 (1986), 24-36. · Zbl 0597.90059 · doi:10.1016/0166-218X(86)90065-X
[2] T. A. Brown and J. Spencer, Minimization of ?1-matrices under line shifts,Colloq. Math. (Poland),23 (1971), 165-171. · Zbl 0222.05016
[3] A. Deif,Sensitivity Analysis in Linear Systems, Springer-Verlag, Berlin, 1986. · Zbl 0624.65019
[4] Ch. Delorme and S. Poljak, Laplacian Eigenvalues and the Maximum Cut Problem, Technical Report 599, L.R.I., Universit? Paris-Sud, 1990. · Zbl 0797.90107
[5] M. Deza and M. Laurent, Facets for the cut cone, I,Math. Programming,56 (to appear). · Zbl 0768.90074
[6] J. C. Doyle, Analysis of feedback systems with structured uncertainties,Proc. IEEE,129 (1982), 242-250.
[7] P. Erd?s and J. Spencer,Probabilistic Methods in Combinatorics, Akademiai Kiad?, Budapest, 1974. · Zbl 0308.05001
[8] M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. · Zbl 0411.68039
[9] K. J. Lieberherr and E. Specker, Complexity of partial satisfaction,J. Assoc. Comput. Mach.,28 (1981), 411-421. · Zbl 0456.68078
[10] M. Mansour, Robust stability of interval matrices,Proceedings of the 28th Conference on Decision and Control, Tampa, FL, 1989, pp. 46-51.
[11] B. Mohar and S. Poljak, Eigenvalues and the max-cut problem,Czech. Math. J.,115 (1990), 343-352. · Zbl 0724.05046
[12] S. Poljak, V. R?dl, and J. Spencer, Tournament ranking with expected profit in polynomial time,SIAM J. Discrete Math.,1 (1988), 372-376. · Zbl 0667.05030 · doi:10.1137/0401037
[13] S. Poljak and D. Turzik, A polynomial time heuristic for certain subgraph optimization problems with a guaranteed worst case bound,Discrete Math.,58 (1986), 99-104. · Zbl 0585.05032 · doi:10.1016/0012-365X(86)90192-5
[14] J. Rohn, Systems of linear interval equations,Linear Algebra Appl.,126 (1989), 39-78. · Zbl 0712.65029 · doi:10.1016/0024-3795(89)90004-9
[15] A. Schrijver,Theory of Integer and Linear Programming, Wiley, Chichester, 1986. · Zbl 0665.90063
[16] A. Tarski,A Decision Method for Elementary Algebra and Geometry, University of California Press, Berkeley, CA, 1951. · Zbl 0044.25102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.