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?
 A: 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.
A: 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}
A: 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$.  
A: 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
A: 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$.
