# Bound the minimum eigenvalue of a symmetric matrix via matrix norms

I'm reading a paper in which the authors prove an inequality of the following form:

$$\lVert H-H'\rVert_2 \leq \lVert H-H'\rVert_F \leq \epsilon \tag 1$$

Here $$H$$ and $$H'$$ are symmetric real matrices ($$H'$$ has all positive eigenvalues, if that matters), and the norms are the $$L_2$$ matrix norm and the Frobenius norm, respectively. With no justification the authors then claim:

$$\lambda_\text{min}(H) \geq \lambda_\text{min}(H') - \epsilon \tag 2$$

where $$\lambda_\text{min}$$ is the minimum eigenvalue of a matrix.

I can't see how to justify this, or even if (2) is even intended to be deduced from the (1). Here is the paper - the end of the proof of Lemma 3.2, page 6.

This answer is based on this one. Below we will be working with some arbitrary inner product, and when we take the norm of a matrix, this means the operator norm associated with the vector norm we're using. We have:

Theorem. If $$A$$ and $$B$$ are real symmetric, then:

$$\lambda_\text{min} (A) \geq \lambda_\text{min} (B) - \lVert A-B\rVert$$ $$\lambda_\text{max} (A) \leq \lambda_\text{max} (B) + \lVert A-B\rVert$$

To prove this, the key is the expression $$x^T Mx$$, where $$M$$ is a symmetric matrix and $$x$$ has unit norm. We need two lemmas about this expression.

Lemma 1. For any matrix $$M$$ and any unit norm $$x$$: $$-\lVert M\rVert \leq x^T Mx\leq \lVert M\rVert$$ Proof. Simple application of Cauchy-Schwartz and of the definition of an operator norm: $$|x^TMx|\leq\lVert x\rVert \lVert Mx\rVert\leq \lVert x\rVert^2 \lVert M\rVert=\lVert M\rVert$$

Lemma 2. For any symmetric matrix $$M$$ and any unit norm $$x$$: $$\lambda_\text{min}(M) \leq x^T M x \leq \lambda_\text{max}(M)$$ and the bounds are attained as $$x$$ varies over the unit sphere.

Proof. Let $$M=P^TDP$$ where $$P$$ is orthogonal and $$D$$ is diagonal. Then $$x^TMx = (Px)^TD(Px)$$ As $$x$$ varies over the unit sphere, $$Px$$ varies also over the entire unit sphere, therefore the range of the latter expression above is simply the range of $$y^TDy$$ as $$y$$ ranges over the unit sphere. By the rearrangement inequality and some other simple arguments, the minimum is attained when $$y$$ is an eigenvector associated with $$\lambda_\text{min}(M)$$ and the maximum when $$y$$ is an eigenvector associated with $$\lambda_\text{max}(M)$$.

Finally we can prove the theorem. For any unit norm $$x$$, we have

$$x^TAx = x^TBx + x^T(A-B)x$$

By applying Lemma 1 to the second term and Lemma 2 to the first term, the minimum of the left hand side is at least $$\lambda_\text{min} (B)-\lVert A-B\rVert$$. By Lemma 2, we know that the minimum of the left hand side is equal to $$\lambda_\text{min} (A)$$. A similar argument shows the other inequality in the theorem.