# Does $(\mathbf A+\epsilon \mathbf I)^{-1}$ always exist? Why?

Does $(\mathbf A+\epsilon \mathbf I)^{-1}$ always exist, given that $\mathbf A$ is a square and positive (and possibly singular) matrix and $\epsilon$ is a small positive number? I want to use this to regularize a sample covariance matrix ($\mathbf A = \Sigma$) in practice, so that I can compute the inverse, which I need to calculate a Mahalanobis distance between two samples. In practice, my covariance matrix is often singular. I know the term $(\mathbf A+\epsilon \mathbf I)^{-1}$ often appears in the context of least squares problems involving Tikhonov regularization (ridge regression). However, I've never seen a statement, proof, or reference which says that the expression is always invertible.

Can any of you help me with a proof or reference?

-
$\operatorname{det}(A+\epsilon X) = \operatorname{det}(A)+\operatorname{det}(A)\operatorname{tr}(A^{-1}X)\epsilon + O(\epsilon^2)$ – tatterdemalion Sep 1 '12 at 20:18
@Joe: While true, that doesn't help: it tells us $\det(A + \epsilon X) \in O(\epsilon^2)$ which doesn't rule out $0$. – Hurkyl Sep 1 '12 at 20:24
It should be noted that the positivity of $\mathbf A$ is irrelevant to the question at hand. Also, the opening sentence of the question could mislead: The statement is indeed true for all sufficiently small $\epsilon>0$, but how small depends on $\mathbf A$. (I got tricked into thinking the questioner really meant “positive definite”, so I posted an answer based on that assumption. I have deleted it after @TonyK pointed out my mistake.) For the record, “positive” usually means all the matrix entries are positive. It can be seen from the answers that this does not enter into the argument. – Harald Hanche-Olsen Sep 2 '12 at 6:41

Recall that $\det(A-t I)=p_A(t)$ is the characteristic polynomial of $A$, which is a degree $N$ polynomial in $t$, where $N$ is the number of rows of $A$. Hence, it is a continuous function in $t$, and has at most $N$ roots, so there is some largest negative root $t_0$, or possibly no negative roots at all (in that case, choose $t_0=-1$ just for completeness). For all $0 < \epsilon < - t_0$, $p_A(-\epsilon)$ is nonzero, meaning that $\det(A+ \epsilon I) \ne 0$, so $A+\epsilon I$ is invertible.

EDIT: Corrected signs to agree with the question

-
Hey Logan, thanks for your answer and sorry for my late answer :) So, is it true that the proposed regularization method fails if $-\epsilon$ is equal (or close) to one of the eigenvalues of $\mathbf A$? – benni Sep 3 '12 at 17:23
$A+ \epsilon I$ is invertible iff $-\epsilon$ is not an eigenvalue of $A$. In my above answer, $t_0$ is the largest (closest to 0) negative eigenvalue of $A$. So yes, you will have issues if $\epsilon$ is one of the eigenvalues (and potentially if they are close, though how close is hard to say). – Logan Maingi Sep 3 '12 at 22:15
But in this question, $A$ is positive semidefinite (in fact $A$ is a sample covariance matrix), so we can make a stronger statement: $A + \epsilon I$ is positive definite (hence invertible) for all $\epsilon > 0$. – littleO Nov 23 '12 at 15:42

To put it simple:

the set of invertible matrices is open in the normed space of all matrices.

Therefore if $A$ is invertible then $A+\epsilon I$ will also be invertible for small $\epsilon$.

-
And also if $\mathbf A$ is not invertible (for strictly positive $\epsilon$). – TonyK Sep 1 '12 at 19:03
I don't think just being open is enough. It means you can perturb an invertible matrix and if the perturbation is small enough, what you get is still invertible. But I think the question is: can even singular matrices be perturbed in the direction of the identity matrix, yielding an invertible matrix? – Michael Hardy Sep 1 '12 at 22:09

Yes, if $\mathbf A$ is any $n \times n$ matrix, then $\mathbf A+\epsilon \mathbf I$ is invertible for sufficiently small $\epsilon > 0$. This is because $\det (\mathbf A + \epsilon \mathbf I)$ is a polynomial in $\epsilon$ of degree $n$, and so it has a finite number of zeroes.

-

Because the determinant function is continuous, and because $A$ is invertible if and only if $\det A \neq 0$, we have that $\det(A)\neq 0 \Rightarrow \det(A+\epsilon B)\neq 0$ for sufficiently small $\epsilon$, regardless of what $B$ is.

If $A$ is singular, then we note that the characteristic polynomial of $A$, given by $\operatorname{ch}_A(t)=\det(A-tI)$ is a polynomial in $t$, and therefore has finitely many roots. Then, whenever $\epsilon$ has absolute value less than the size of the smallest nonzero root $\det(A+\epsilon I)\neq 0$.

-

If $A$ is symmetric positive semidefinite, and $\epsilon > 0$, then $A + \epsilon I$ is symmetric positive definite (and hence invertible).

To see this, note that if $x \neq 0$ then \begin{align} x^T(A + \epsilon I) x &= x^T A x + \epsilon x^T x \\ &= x^T A x + \epsilon \|x\|^2 \\ & > 0. \end{align}

-