T. Tao in his notes on eigenvalue inequalities uses Courant-Fischer min-max theorem to prove the eigenvalue stability inequality. Specifically, I am looking for proof of Eq. (13) where he states as an immediate result of Eq. (6) and (10). But the problem is that the min-max function is not convex. I have read Stewart & Sun's book on Matrix Perturbation Theory, but it seems that they have felt that it is obvious too.
Can someone provide more details on how to derive Eq. (13)?
It is a simple and repeated application of $\min$ and $\max$ operators.
$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op},\,\forall v\in R^n\wedge |v|=1.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op},\,\forall v\in V\wedge |v|=1,$$ then $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op}$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-\|B\|_{op}\le\lambda_i(A+B)$ and reach the desired inequality.
