If $A,B$ are $n\times n$ Hermitian matrices, then a version of Weyl's inequalities states that
$$\lambda_k(A)+\lambda_n(B)\leq\lambda_k(A+B)\leq \lambda_k(A)+\lambda_1(B) \quad 1\leq k\leq n,$$
where $\lambda_i$ denotes the $i$th largest eigenvalue.
Consider the following proof of the rightmost inequality, making use of the min-max characterization of eigenvalues for a Hermitian matrix:
$$\lambda_k(A+B)=\min_{U\subset F^n, \text{dim } U=k} \max_{v\in U,v\neq 0} R_{A+B}(v)=\min_{U\subset F^n, \text{dim } U=k}\max_{v\in U,v\neq 0} [R_{A}(v)+R_B(v)]$$
$$\leq\min_{U\subset F^n, \text{dim } U=k} \max_{v\in U,v\neq 0}[ R_{A}(v)+\lambda_1(B)]=\min_{U\subset F^n, \text{dim } U=k}\max_{v\in U,v\neq 0} R_{A}(v) +\lambda_1(B)=\lambda_k(A)+\lambda_1(B),$$
where $R_{C}$ denotes the Rayleigh quotient of $C$.
In my notes it is written that the leftmost inequality can be proven similarly using the max-min characterization. However looking at the above proof it seems that replacing $\lambda_1(B)$ with $\lambda_n(B)$ and reversing the inequality sign also gives a proof.
Can we use both the min-max and max-min chracterization of eigenvalues to prove Weyl's inequalities? Thanks a lot for your help.
Best Answer
First of all, the proof you exhibited has got the dimension of $U$ wrong. E.g. when $k=1$, the first equality in your proof gives $$ \lambda_1(A+B)=\min_{U\subset F^n,\,\dim U=1}\ \max_{v\in U,v\neq 0} R_{A+B}(v). $$ If you write $U=\operatorname{span}(v)$, the RHS above reduces to $\min_{v\ne0}R_{A+B}(v)$, which is actually $\lambda_n(A+B)$, not $\lambda_1(A+B)$.
To correct the proof, the dimension of $U$ should be $n+1-k$ rather than $k$: \begin{align} \lambda_k(A+B) &=\min_{\dim U=n+1-k}\ \max_{v\in U\setminus0} R_{A+B}(v)\\ &=\min_{\dim U=n+1-k}\ \max_{v\in U\setminus0} \left(R_A(v)+R_B(v)\right)\\ &\leq\min_{\dim U=n+1-k}\ \max_{v\in U\setminus0} \left(R_A(v)+\lambda_1(B)\right)\tag{1}\\ &=\left(\min_{\dim U=n+1-k}\ \max_{v\in U\setminus0} R_A(v)\right)+\lambda_1(B)\\ &=\lambda_k(A)+\lambda_1(B). \end{align} Now, return to your question. Can we replace $\lambda_1(B)$ by $\lambda_n(B)$ in the first proof (that uses min-max characterisation) and reverse the directions of the inequalities? Yes, but we need to be careful in justifying the inequality analogous to line $(1)$. In line $(1)$, we may argue as follows. For every nonzero subspace $U$, let $v_0\in U\setminus0$ be the maximiser of $R_A(v)+R_B(v)$. Then \begin{align} \max_{v\in U\setminus0} \left(R_A(v)+R_B(v)\right) &=R_A(v_0)+R_B(v_0)\\ &\leq R_A(v_0)+\lambda_1(B)\\ &\leq\max_{v\in U\setminus0} \left(R_A(v)+\lambda_1(B)\right). \end{align} Since this is true for every $U$, it is also true for their minimum values over all $U$s of dimensions $n+1-k$. Hence $(1)$ is justified. However, if we simply replace $\lambda_1(B)$ by $\lambda_n(B)$ and reverse the directions of the inequalities in the above argument, we will get \begin{aligned} \max_{v\in U\setminus0} \left(R_A(v)+R_B(v)\right) &=R_A(v_0)+R_B(v_0)\\ &\geq R_A(v_0)+\lambda_n(B)\\ &\color{red}{\geq}\max_{v\in U\setminus0} \left(R_A(v)+\lambda_n(B)\right), \end{aligned} which is not correct. To correct the argument, we should pick $v_0$ as the maximiser of $R_A(v)$ over $U\setminus0$ instead. Then \begin{aligned} \max_{v\in U\setminus0} \left(R_A(v)+R_B(v)\right) &\color{red}{\geq} R_A(v_0)+R_B(v_0)\\ &\geq R_A(v_0)+\lambda_n(B)\\ &\color{red}{=}\max_{v\in U\setminus0} \left(R_A(v)+\lambda_n(B)\right), \end{aligned} Since this is true for every nonzero subspace $U$, if we minimises both sides in the above over all $(n+1-k)$-dimensional subspaces $U$, we obtain $\lambda_k(A+B)\ge\lambda_k(A)+\lambda_n(B)$.