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.
 A: 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.
