# 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.

## 1 Answer

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.