Bound the minimum eigenvalue of a symmetric matrix via matrix norms

Question

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.

Answer 1

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.