Is there a way to efficiently check if all matrices in the following set are Hurwitz stable (eigenvalues strictly in the lefthand plane)?$$\left\{ A \in \Bbb R^{n \times n} : \ell_{i,j}\leq A_{i,j} \leq u_{i,j} \right\}$$ I could work with eigenvalues on the imaginary axis, too. I am looking for a result similar to that of Kharitonov's.
Given affine function $A : \Bbb R^m \to \Bbb R^{n \times n}$, where $m < n$, is there a similar result for checking the stability of the following set? $$\left\{ A(u_1, u_2, \dots, u_m): 0 \leq u_1, u_2,\dots, u_m \leq 1 \right\}$$

$\begingroup$ Not exactly an answer, but there is a notion of signstable patterns. These are matrices whose entries belong to $\{,0,+\}$, such that every compatible realisation is a stable matrix. See exercise #29 on my webpage perso.enslyon.fr/serre/DPF/exobis.pdf . $\endgroup$– Denis SerreCommented Dec 27, 2021 at 9:17

$\begingroup$ @DenisSerre Thanks for the pointer. $\endgroup$– DSMCommented Dec 28, 2021 at 3:03

$\begingroup$ @RodrigodeAzevedo (i) preferably, strictly in LHP (if a condition exists for closed LHP, can work with that too), (ii) A is real, (iii) size of A can be arbitrary (and, m<n in the second case). $\endgroup$– DSMCommented Dec 28, 2021 at 3:06

$\begingroup$ Good pointers to start with are "verified computation" and "interval arithmetic", since what you have is essentially an interval matrix. $\endgroup$– Federico PoloniCommented Jun 16, 2023 at 7:42
1 Answer
For the first question, a sufficient condition would be the existence of a symmetric positive function such that
$$A^TP+PA\prec0$$
for all $A\in\left\{ A \in \Bbb R^{n \times n} : A_{i,j}\in\{\ell_{i,j},u_{i,j}\}\right\}$. This follows from a simple application of Lyapunov theorem. The issue is that it has an exponential complexity in the dimension of the system. In fact, there are $2^{n^2}$ inequalities to verify.
If the matrices satisfy a particular structure, this can be simplified. For instance, if $A$ is Metzler, then a necessary and sufficient condition is that the upperbound $A$ with $A_{ij}=u_{ij}$ is Hurwitz stable.
The same applies for the second question.

$\begingroup$ Why is it enough to check the $2^{n^2}$ vertices? This does not seem obvious to me. $\endgroup$ Commented Jun 18, 2023 at 13:13

$\begingroup$ @FedericoPoloni This is a consequence of the convexity of set of all possible matrices $A$. $\endgroup$– KBSCommented Jun 18, 2023 at 13:39