What is the smallest real perturbation of a Hurwitz matrix where the result is no longer Hurwitz?

Question

What is the smallest real perturbation of a Hurwitz matrix where the result is no longer Hurwitz? In other words, given a matrix $A\in\mathbb{R}^{n\times n}$ where $\min_{i}\textrm{Re}\lambda_i(A) < 0$ what is the smallest matrix $B\in\mathbb{R}^{n\times n}$ in terms of norm where there exists $i$ such that $\textrm{Re}\lambda_i(A+B) \geq 0$? Here, $\lambda_i(A)$ denotes the $i$-th eigenvalue of $A$. In case it's not clear, the matrix $A$ is not necessarily symmetric.

Answer 1

Here's one reasonable bound that answers the question that I suspect you're trying to ask. As a measure for the "size" of a perturbation, I will use the spectral norm (i.e. maximal singular value). The upper bound I give is in terms of $\alpha$, the absolute value of the largest real part among the eigenvalues of $A$, and $\|A\|$, the spectral norm of $A$.

---

From Bhatia's Matrix Analysis Theorem VIII.1, we have the following bound on the Hausdorff distance between the spectral sets $\sigma(A)$ and $\sigma(A + B)$: $$ h(\sigma(A),\sigma(A + B)) \leq (\|A\| + \|A + B\|)^{1-1/n} \|B\|^{1/n} $$ Where $\|M\|$ denotes the spectral norm of $M$. Let $\epsilon = \|B\|$. With the triangle inequality, this can be simplified to the slightly weaker bound $$ h(\sigma(A),\sigma(A + B)) \leq (2\|A\| + \|B\|)^{1-1/n} \|B\|^{1/n} \\ = (2\|A\| + \epsilon)^{1-1/n} \cdot \epsilon^{1/n} $$ Now, suppose that the maximal real part among the eigenvalues of $A$ is given by $-\alpha$ where $\alpha>0$. In order for $A + B$ fails to be Hurwitz, then it has an positive eigenvalue (i.e. an eigenvalue with positive real part), and the distance between this positive eigenvalue and any of the eigenvalues of $A$ must be at least $\alpha$, which in turn means that the Hausdorff distance $h(\sigma(A),\sigma(A+B))$ has to be at least $\alpha$.

By contrapositive, this means that if $\epsilon$ is chosen so that $h(\sigma(A),\sigma(A + B)) < \alpha$, then we can guarantee that $A + B$ is stable. The right hand side is an increasing function of $\epsilon$, so if we find the solution $\epsilon_0$ to the equation $(2\|A\| + \epsilon)^{1-1/n} \cdot \epsilon^{1/n} = \alpha$, then $A + B$ can only be unstable if $\|B\| \geq \epsilon_0$.

---

We can get a more "concrete" upper bound if that is desired. Suppose that we stipulate that we must have $\epsilon \leq \|A\|$. Then, we can obtain the weaker upper bound on the Hausdorff distance $$ h(\sigma(A), \sigma(A + B)) \leq (3\|A\|)^{1-1/n} \epsilon^{1/n}. $$ The solution $\epsilon_1$ to the equation $(3\|A\|)^{1-1/n} \epsilon^{1/n} = \alpha$ is given by $$ \epsilon_1 = \frac{\alpha^n}{(3\|A\|)^{n-1}} = \alpha \cdot \left(\frac{\alpha}{3\|A\|}\right)^{n-1}. $$ Thus, if $A + B$ fails to be Hurwitz, then it must be the case that $$ \|B\| > \min\left\{\|A\|,\frac{\alpha^n}{(3\|A\|)^{n-1}}\right\}. $$ So, a perturbation $B$ that results in an unstable matrix $A + B$ must be at least this large.