# Upper bound of spectral radius of the sum of two matrices, one with spectral radius no larger than 1, and the other has small eigenvalues

Suppose I have one $pN\times pN$ matrix $\bf A$ with spectral radius no larger than 1 (maximum of absolute values of eigenvalues is no larger than 1), and the other matrix $\bf H$ is in a block-like format (empty means zero, only zeros in the top-left and bottom-right block are explicitly marked, the superscript like $N^{(N+1,N)}$ means this number "$N$" is at the $N+1$th row and $N$th column)

My question is how to derive a reasonably tight bound of the spectral radius of the sum $\bf A+H$. Again the spectral radius of $\bf A$ is smaller than 1 and $\bf A$ need not be symmetric or positive. The eigenvalue of $\bf H$ is $\pm \frac{1}{{n + 1}}$, so we believe the spectral radius of $\bf{A+H}$ should be near the spectral radius of $\bf A$.

Here is a general continuity type result on perturbations of the spectral radius:

Theorem. Let $A,B \in \mathbb{C}^{n \times n}$ be matrices and let $r(A)$ denote the spectral radius of $A$. For each $r > r(A)$ we set \begin{align*} \alpha(r) := \sup_{\lvert\lambda\rvert \ge r} \lVert (\lambda - A)^{-1} \rVert \end{align*} (note that $\alpha(r) < \infty$). If $\lVert B \rVert < 1/\alpha(r)$, then $r(A+B) < r$.

Proof. This is a simple consequence of the Neumann series: Let $\mu$ be a complex number of moduls $\lvert \mu \rvert \ge r$. Then $\lVert (\mu - A)^{-1} B \rVert < 1$, so the matrix \begin{align*} \mu - (A+B) = (\mu - A) (I - (\mu - A)^{-1} B) \end{align*} is invertible since $(\mu - A)$ and $I - (\mu - A)^{-1}B$ are invertible (the latter due to the Neumann series).

The following formulation of the theorem is probably a bit easier to read:

Corollary. Let $A \in \mathbb{C}^{n \times n}$. For every $r > r(A)$ there exists $\delta(r) > 0$ such that $r(A+B) < r$ for every matrix $B \in \mathbb{C}^{n \times n}$ which fulfils $\lVert B \rVert < \delta(r)$.

Proof. Take $\delta := 1/\alpha(r)$.

Remark 1. If $r(A) = 1$ and if $A$ is in addition power-bounded, i.e. $M := \sup_{n \in \mathbb{N}_0} \lVert A^n \rVert < \infty$, then we have $\alpha(r) \le M/(r - 1)$ for each $r > 1$ (this is again a simple consequence of the Neumann series representation of the resolvent). Hence, in this special case we can choose $\delta(r) = (r-1)/M$ in the corollary.

Remark 2. The above results are very rough (as indicated by their elementary proofs). There exist more precise (and quantitative) results, as for instance indicated by Federico Poloni in the comments.

• Thanks a lot Jochen, is above $\| \|$ denoting spectral norm or it can be any norm? – Tony Aug 28 '18 at 21:48
• Is there any intuitive interpretation of function $\alpha(r)$? Any references for this theorem? – Tony Aug 29 '18 at 3:24
• @Tony: A few answers to your comments: (i) $\lVert\cdot\rVert$ is allowed to be any submultiplicative norm on $\mathbb{C}^{n \times n}$. (ii) Well, that depends on what you find intuitive ;-). I tried to illustrate the meaning of $\alpha(r)$ in Remark 1. (iii) I don't know if the theorem is stated anywhere in precisely this form (that's why I included a proof). But the argument from the proof is pretty much standard in spectral and operator theory (for instance, almost the same argument is used to show that the set of invertible bounded operators on a Banach space is open). – Jochen Glueck Aug 29 '18 at 4:50

The spectral radius satisfies the triangle inequality, so $\rho(\mathbf{H} + \mathbf{A}) \leq \rho(\mathbf{A}) + \frac1{n+1}.$ Now, this is close to the spectral radius of $\mathbf{A}$ if this last is not too small, otherwise - not so much.

• Thanks Igor. Could you help give some explanation why spectral radius satisfy triangle inequality in this case? – Tony Aug 28 '18 at 3:24
• @Tony Consider a vector $v.$ $|Av|\leq\rho(A) |v|,$ $|Hv| \leq \rho(H) |v|,$ so the rest follows from the usual triangle inequality, with equality when $v$ is an eigenvector of both $A$ and $H,$ with eigenvalues whose ratio is a positive real. – Igor Rivin Aug 28 '18 at 4:39
• @Igor: I'm a bit confused, too. For general matrices the spectral radius is not subadditive; e.g. let $A, B$ be $2\times 2$-matrices where the only non-zero entry of $A$ is the number $1$ located at position $(1,2)$, and where $B$ is the transposed matrix of $A$. – Jochen Glueck Aug 28 '18 at 4:49
• It should hold that $\rho(A+H) \leq \rho(A) +\kappa(V_A)\|H\|$, though, where $\kappa(V_A)$ is the condition number of the eigenvector matrix of $A$. Maybe this is enough for OP to conclude (for instance, if $A$ is normal / symmetric). – Federico Poloni Aug 28 '18 at 6:54
• @FedericoPoloni Thanks Federico. $\bf A$ is general matrix which need not be symmetric or normal or anything. In this case will this inequality still hold? – Tony Aug 28 '18 at 13:38