# Invertibility of $(\textbf{A}^T\textbf{A}+\epsilon \textbf{I})$?

I'm given a problem:

$$\sigma_1 \geq \sigma_2 \geq ... \geq \sigma_r$$ are the nonzero singular values of $$\textbf{A}\in\mathbb{R}^{M\times N}$$. If $$\epsilon \neq 0$$ is a real scalar, s.t. $$|\epsilon| < \sigma^{2}_r$$, show that $$(\textbf{A}^T\textbf{A}+\epsilon \textbf{I})$$ is invertible.

But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $$\textbf{A}^T\textbf{A}$$ is invertible by definition, but I'm not sure if I can just plug $$\textbf{A}^T\textbf{A}$$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.

Can anyone help me understand WHY $$(\textbf{A}^T\textbf{A}+\epsilon \textbf{I})$$ is invertible? And/or point me in the right direction to construct a proof of it?

• Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis – operatorerror Dec 5 '18 at 21:59

Write out $$A$$ in its SVD, $$A=U\Sigma V^T$$. Then we have

$$A^TA+\epsilon I = V\Sigma^2 V^T+\epsilon I = V\Sigma^2V^T+\epsilon VV^T = V(\Sigma^2+\epsilon I)V^T.$$ From this, we have that the eigenvalues are exactly $$\sigma_i^2+\epsilon$$ for $$i=1\dots r$$ and $$\epsilon$$ for $$i=r+1\dots n$$. These are all nonzero, so the matrix is invertible.

• Thank you! Is there a straightforward way to find the limit of $(\textbf{A}^T\textbf{A}+\epsilon \textbf{I})^{−1}\textbf{A}^T$ as $\epsilon$ goes to 0? Obviously this reduces to $(\textbf{A}^T\textbf{A})^{-1}\textbf{A}^T$, but I'm not sure where to go from here without specific values for A – W. MacTurk Dec 6 '18 at 1:58

You can show that $$A^\top A$$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $$\sigma_1^2, \ldots, \sigma_r^2, 0, \ldots, 0$$).

[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]

Knowing this fact about $$A^\top A$$, can you explicitly write down the eigenvalues of $$A^\top A + \epsilon I$$? What values of $$\epsilon$$ make this matrix invertible or non-invertible?

• Wouldn't the eigenvalues just be $\sigma_{1}^{2}+\epsilon , \sigma_{2}^{2}+\epsilon , ...\sigma_{r}^{2}+\epsilon$, with trailing eigenvalues of $\epsilon$ if $\textbf{A}^T\textbf{A}$ was not invertible? – W. MacTurk Dec 7 '18 at 3:24