# Matrix norm of $A-B$ and their smallest eigenvalues

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.

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).$$