Positive semi-definite Matrix and its eigenvalues (Please help checking/ improving my presentation)

Question

Let $A$ and $B$ are two $n \times n$ Hermitian matrices . Suppose $A-B$ is positive semidefinite.

(a) Show that $\lambda_k(A) \geq \lambda_k(B)$ for $k=1,2,\dots ,n,$ where $\lambda_i(A)$ and $\lambda_i(B)$ are eigenvalues of matrices $A$ and $B$ with $\lambda_i (A)\geq \lambda_{i+1}(A)$ and $\lambda_i (B)\geq \lambda_{i+1}(B)$.

(b) Find a counter example to prove the converse of (a) is not true. i.e.,

Find two Hermitian matrices $A$ and $B$ such that $\lambda_k(A) \geq \lambda_k(B)$ but $A-B$ is not positive semidefinite.

---

My Trial:

(a) Since $A-B$ is positve semi-definite, $x^*(A-B)x \geq 0 \Rightarrow x^{*}Ax \geq x^{*}Bx.$

Also, as $A$ and $B$ are two Hermitian matrices, by spectral decomposition, we have $x^{*}Ax = x^{*}UD_{A}U^{*}x=x^{*}D_{A} x$ and $x^{*}Bx = x^{*}UD_{B}U^{*}x=x^{*}D_{B} x$.

It implies $D_{A} \geq D_{B}$ and so for each of theire eigenvalues.

(b) Let $A=\begin{pmatrix} 1 &0 \\ 0 &1 \end{pmatrix}$ and $B=\begin{pmatrix} 2 &0 \\ 0 &0 \end{pmatrix}$.

---

Please help to check if I make mistake in my presentation because I am very new to this topic so I do not know if am correct or not. Thank you very much in advance.

Answer 1

To prove (a), you need to use the variational characterisation of eigenvalues (the min-max principle, Courant-Fischer theorem). For a Hermitian $A$ and the specified ordering of eigenvalues, $$\tag{$*$} \lambda_k(A)=\max_{S:\dim S=k}\min_{x\in S\setminus\{0\}}\frac{x^*Ax}{x^*x}=\min_{S:\dim S=n-k+1}\max_{x\in S\setminus\{0\}}\frac{x^*Ax}{x^*x}. $$ Let $S_*$ be the subspace of the dimension $n-k+1$ for which the minimum on the right-hand side of ($*$) is attained, that is, $$ \lambda_k(A)=\max_{x\in S_*\setminus\{0\}}\frac{x^*Ax}{x^*x}. $$ Then (using $x^*Ax\geq x^*Bx$ for all $x$) $$ \lambda_k(A)=\max_{x\in S_*\setminus\{0\}}\frac{x^*Ax}{x^*x} \geq\max_{x\in S_*\setminus\{0\}}\frac{x^*Bx}{x^*x} \geq\min_{S:\dim S=n-k+1}\max_{x\in S\setminus\{0\}}\frac{x^*Bx}{x^*x}=\lambda_k(B). $$

---

I was also thinking whether there would be an alternative proof which does not involve the variational characterisation and can thus be considered as more elementary. This is motivated by the proof here.

By exactly the same technique as in that proof, one can show the following:

Let $A,B\in\mathbb{C}^{n\times n}$ be Hermitian and let $i_{+,0}(A)$ and $i_+(A)$ denote the number of non-negative and positive eigenvalues, respectively, of $A$. Then $$ i_{+,0}(A+B)\leq i_+(A)+i_{+,0}(B). $$

Now replace in the statement above $A$ and $B$, respectively, by $A-\lambda_k(A)I$ and $\lambda_k(A)I-B$. We get $$\tag{1} i_{+,0}(A-B)\leq i_+(A-\lambda_k(A)I)+i_{+,0}(\lambda_k(A)I-B). $$ Since our $A$ and $B$ are such that $A-B$ is positive semi-definite and hence all its eigenvalues are non-negative, we have $i_{+,0}(A-B)=n$. Note that adding a multiple of the identity to $A$ just shifts the eigenvalues, so the $k$th eigenvalue of $A-\lambda_k(A)I$ is zero and thus there is at most $k-1$ positive eigenvalues of $A-\lambda_k(A)I$, that is, $i_+(A-\lambda_k(A)I)\leq k-1$. Putting this stuff to (1) gives $$ n\leq k-1+i_{+,0}(\lambda_k(A)I-B)\quad \Rightarrow \quad n-k+1\leq i_{+,0}(\lambda_k(A)I-B). $$ Since there is at least $n-k+1$ non-negative eigenvalues of $\lambda_k(A)I-B$, there is at most $k-1$ negative eigenvalues. Equivalently, the matrix $B-\lambda_k(A)I$ has a most $k-1$ positive eigenvalues and hence the $k$th eigenvalue of $B-\lambda_k(A)I$ is non-positive. But this eigenvalue is nothing but $\lambda_k(B)-\lambda_k(A)$ and hence $$ \lambda_k(B)-\lambda_k(A)\leq 0\quad\Rightarrow\quad\lambda_k(A)\geq\lambda(B). $$