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.

• How $U^*x$ becomes $x$? And the $U$ matrix is not the same for $A$ and for $B$. – enzotib May 7 '14 at 10:03
• Is it given that $A,B$ have the same eigenvectors? – Samrat Mukhopadhyay May 7 '14 at 10:21
• @enzotib Since $U$ is unitary, norm of $U*x$ = norm of $x$. Can I say this? – nam May 7 '14 at 10:22
• @Samrat The question does not give that $A$ and $B$ have the same eigenvectors. – nam May 7 '14 at 10:23
• @Pavel So, am I correct on the whole? – nam May 7 '14 at 10:24

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

• Very thanks to your hint. I just had some readings on Rayleigh quotients but I get lost and do not know how to apply your hint on this question (it seems to pick up second large eigenvalue from some subspaces of smaller dimension). Would you mind giving me lines of answers. Thank you so much. – nam May 7 '14 at 10:45
• @nam It should be quite complete now :) – Algebraic Pavel May 7 '14 at 10:49
• Thank you for your illustration for the theorem. I know what I missed and I am looking for other examples to check. Thank you so much. – nam May 7 '14 at 11:02
• You are welcome. – Algebraic Pavel May 7 '14 at 11:02
• Just for fun, I've tried to make a proof which does not use the min-max principle. However, it's a bit longer. – Algebraic Pavel May 7 '14 at 13:03