Invertibility of $A-\Delta Id$.

Question

Assume that $A\in\mathbb{R}^{n\times n}$ is positive semidefinite and let \begin{equation} \Delta=diag(\lambda_1,\ldots,\lambda_n), \end{equation} for $\lambda_1,\ldots,\lambda_n\in\mathbb{R}$. What can we say about the invertibility of $A+\Delta$? I mean, if $A$ is diagonal and none of the $\lambda_j$'s is equal to any of the eigenvalues of $A$, then $A+\Delta$ is invertible, because it is a diagonal matrix having non-zero eigenvalues. But what can we say in the general situation?

Answer 1

In general, this matrix is almost always invertible. Most matrices are. However, there is a simple condition which guarantees invertibility, which is that all the $\lambda_j$ are positive. In this case, $A+\Delta$ is positive definite, and therefore invertible. To see this, compute

$$ x^\intercal(A+\Delta)x = x^\intercal A x + x^\intercal \Delta x. $$

Both terms are at least zero, and the second term is positive if $x \neq 0$.

Answer 2

Aassuming $\Delta$ is invertible, let's consider $$A-(-\Delta)$$

There is a theorem found in Rudin's Principles of Mathematical Analysis book which provides conditions guaranteeing $A$ will be invertible.

For a given invertible linear map $E$ and linear map $F$ if $$\|F-E\|\cdot\|E^{-1}\|<1$$ then $F$ is invertible.

Note: The intuition may be that for a given linear map $$ and invertible linear map $$, as long as the distance $\|F-E\|$does not exceed (is strictly less than) $1/\|E^{-1}\|$ then is invertible.

We first consider $F=A$ and $E=-\Delta$ then the condition reads:

$$\|A-(-\Delta)\|\cdot\|-\Delta^{-1}\|<1$$

Here, the norm $\|\cdot\|$ can be the largest absolute value of all matrix entries.

Since $\Delta$ is assumed to be diagonal we have $\Delta^{-1}=\text{diag}\{\lambda_1^{-1},...,\lambda_n^{-1}\}$ and so the norm $$\|-\Delta^{-1}\|=\text{max}_{j=1,...,n}\{|\lambda_j^{-1}|\}=|\lambda_k^{-1}|$$ for some $k\in \{1,...,n\}$. So you will have the condition: if $\|A-(-\Delta)\|<|\lambda_k^{-1}|^{-1}=|\lambda_k|$ then $A$ will be invertible.

For $A+\Delta$ to be invertible, you can use the same idea; if $$\|A+\Delta-\Delta\|\cdot\|\Delta^{-1}\|<1$$ then the theorem implies $A+\Delta $ is invertible.