# Why a positive definite matrix X plus a matrix whose induced 2-norm is smaller than the smallest eigenvalue of X is still positive definite

I read following conclusion from a paper:

Say $X$ is a positive definite $n \times n$ matrix, if $\|Y\|_2 < \sigma_n(X)$, where $\sigma_n(X)$ is the smallest eigenvalue of $X$, then $X+Y$ is also positive definite.

Why is that?

both $X$ and $Y$ are symmetric matrix here.

• $\sigma_n (X)$ is a singular value of $X$, not an eigenvalue of $X$. Jun 7, 2016 at 21:05
• @RodrigodeAzevedo I think the author of the paper re-defined the notation. Jun 7, 2016 at 21:08
• For positive definite matrices, dont the singular values coincide with the eigenvalues? Jun 7, 2016 at 21:16
• @Roland Well, no. They coincide for a symmetric positive-definite matrix. But $[[2,1],[-1,2]]$ is positive definite, hence has positive singular values, but complex eigenvalues. Jun 7, 2016 at 22:27
• Are you leaving something out? Maybe something that was clear from the context in the paper, but not stated in the sentence you're referring to? In particular are these symmetric matricies? A positive-definite matrix in general can have complex eigenvalues, in which case saying $||Y||$ is less than the smallest eigenvalue makes no sense. Jun 7, 2016 at 22:30

A general matrix $A$ is said to be positive definite if and only if $$A + A^T$$ is symmetric positive definite or equivalently if and only if $$u^T(A+A^T) u > 0, \quad u \not = 0.$$
If $A$ is symmetric, then this condition is obviously equivalent to $$u^T A u > 0, \quad u \not = 0.$$ As pointed out by David C. Ullrich, the equivalence hold regardless of whether $A$ is symmetric or not, because $$u^TAu = (u^TAu)^T = u^T A^T u,$$ which implies $$u^T (A + A^T) u = 2 u^T A u.$$
In our case, both $X$ and $Y$ are symmetric and our goal is to show that $Z = X + Y$ is symmetric positive definite, i.e. $$u^TZ u > 0, \quad u \not = 0.$$ By the spectral theorem, we have $$u^T X u \ge \lambda_{\min}(X) \|u\|^2,$$ where $\lambda_{\min}(X) > 0$ denotes the smallest eigenvalue of $X$. Cauchy-Schwartz's inequality implies that $$|u^T Y u| \leq \|Y\| \|u\|^2.$$ In particular, we have $$u^T Y u \ge - |u^T Y u| \ge - \|Y\| \|u\|^2,$$ from which it follows that $$u^TZu = u^T X u + u^T Y u \ge \lambda_{\min}(X)\|u\|^2 - \|Y\| \|u\|^2 = (\lambda_{\min}(X) - \|Y\|) \|u\|^2.$$ By assumption, $\|Y\| < \lambda_{\min}(X)$, so $$u^TZu > 0, \quad u \not = 0.$$ It follows, that $Z$ is symmetric positive definite.
In popular terms, if the perturbation $Y$ is small enough, then $Z = X + Y$ is certainly nonsingular and the threshold is determined by the smallest eigenvalue of $X$.
• Two comments: Actually $u^TAu>0$ is equivalent to $u^T(A+A^T)u>0$ whether $A$ is symmetric or not, because $(u^TAu)^T=u^TA^Tu$. And the "By assumption" seems a little not quite right - the inequality that follows is true, but it needs to be proved from the assumptions (it's clear from the Spectral Theorem for example). Jun 8, 2016 at 16:40