Qualitative stability of linear systems (Q579276)

A square matrix A is defined to be semistable (stable) if each eigenvalue has nonpositive (negative) real part, and quasistable if it is semistable and eigenvalues with zero real part are simple in the minimum polynomial of A. Let Q(A) denote the convex cone of all matrices having the same sign pattern as A. The matrix A is said to be sign-semistable (sign- quasistable, sign-stable) if every member of Q(A) is semistable (quasistable, stable). It has been known that sign-stability of a matrix can be tested using either cycle conditions on its associated signed digraph [\textit{Quirk} and \textit{Ruppert}, ``Qualitative economics and the stability of equilibrium'', Rev. Econ. Stud. 32, 311-326 (1965)], or coloring conditions on its undirected graph [\textit{C. Jeffries, V. Klee} and \textit{P. van den Driessche}, ``When is a matrix sign stable?'', Can. J. Math. 29, 315-326 (1977; Zbl 0383.15005)]. The present paper investigates sign- quasistability of matrices using similar graph theoretic concepts, and provides a procedure to check a marix for sign-quasistability in polynomial time. The main result states that ``A properly presented \(n\times n\) matrix A can be tested in time O (n \(+\) number of nonzero entries of A) for sign-semistability, for sign-quasistability, and for sign-stability''.