Let $A$ and $B$ be symmetric positive definite matrices of size $n\times n$
such that $\|A – B\| < \frac{1}{4}\lambda_{\min}(B)$
where $\|\cdot\|$ is the matrix 2-norm
and $0 < \lambda_{\min}(B)$.
[An additional condition is added]
For any $|A_{ij} – B_{ij}| < \frac{\lambda_{\min}(B)}{4n}$ for all $1\le i, j \le n$.
Can we say that
$$
(*)\quad \lambda_{\min}(A) \ge \frac{3}{4}\lambda_{\min}(B)?
$$
If them, how so?
Since $\|B\| = \lambda_{\max}(B)$, it seems that the following is true
$$
\frac{3}{4}\lambda_{\min}(B) \le \lambda_{\max}(B)-\frac{1}{4}\lambda_{\min}(B)=\|B\|-\frac{1}{4}\lambda_{\min}(B) < \|A\|
$$
however, not sure why the above (*) is true…and how to relate the smallest eigenvalue of $A$ out of this.
Any suggestions/comments/answers will be very appreciated.
Best Answer
Yes, we can say it. By spectral theorem, we can write $A=PDP^T$ where $P$ is orthogonal and $D>0$ is diagonal with each entry being eigenvalue of $A$. We observe that $$ \min_{\|x\|=1}x^TAx=\min_{\|x\|=1}(P^Tx)^TD(P^Tx)=\min_{\|y\|=1} y^TDy=\lambda_{\text{min}}(A).\tag{*} $$ ($(*)$ is a characterization of $\lambda_{\text{min}}(A)$.) So it suffices to show that $ \min_{\|x\|=1}x^TAx\ge \frac34 \lambda_{\text{min}}(B), $ or equivalently $x^TAx\ge \frac34 \lambda_{\text{min}}(B)$ for all unit vectors $x$. We find that $$ x^TAx=x^T(A-B)x+x^TBx. $$ For the first term, we have by Cauchy-Schwarz, $$ -x^T(A-B)x\le|\langle x,(A-B)x\rangle|\le \|x\|\|(A-B)x\|\le \|A-B\|\le \frac14\lambda_{\text{min}}(B) $$ and for the second term, by $(*)$, $$ x^TBx\ge \lambda_{\text{min}}(B). $$ Combining them, we get $$ x^TAx=x^T(A-B)x+x^TBx\ge \frac34\lambda_{\text{min}}(B) $$ as wanted. So $\lambda_{\text{min}}(A)\ge \frac34\lambda_{\text{min}}(B)$.
Note: The argument essentially shows that in general, $$ \lambda_{\text{min}}(A)\ge \lambda_{\text{min}}(B)-\|A-B\|. $$ In fact, in the same manner, we can also prove $$ \lambda_{\text{max}}(A)\le \lambda_{\text{max}}(B)+\|A-B\| $$ by using similar characterization $\max_{\|x\|=1}x^TAx=\lambda_{\text{max}}(A).$