I am confused about the following inequality appeared in the journal Greedy Quasi-Newton Methods with Explicit Superlinear Convergence
(https://arxiv.org/pdf/2002.00657.pdf).
Let $A \in \mathcal{R}^{n\times n}$ be a positive definite matrix and $R \in \mathcal{R}^{n\times n}$ be a positive semidefinite matrix, then it follows:
$R \preceq \langle A^{-1}, R\rangle A$
Note that $\langle A^{-1}, R \rangle = Trace(A^{-1}R)$.
I attempted to prove the above inequality. One sufficient condition of the above inequality is:
$\lambda_1(R) \leq \langle A^{-1}, R \rangle \lambda_n(A)$
where $\lambda_1(R)$ is the largest eigenvalue of $R$ and $\lambda_n(A)$ is the smallest eigenvalue of $A$.
We can bound $\langle A^{-1}, R\rangle$ by
$ \sum_{i=1}^n (\lambda_i(R) / \lambda_i(A)) = \sum_{i=1}^n \lambda_{n-i}(A^{-1}) \lambda_i(R) \leq \langle A^{-1}, R \rangle \leq \sum_{i=1}^n \lambda_i(A^{-1}) \lambda_i(R) = \sum_{i=1}^n (\lambda_i(R) / \lambda_{n-i}(A))$.
However, I cannot derive $\frac{\lambda_1(R)}{\lambda_n(A)} \leq \langle A^{-1}, R \rangle$ given the above inequality. How to resolve this issue?
Best Answer
Let $S=A^{-1/2}RA^{-1/2}$. The inequality in question is then equivalent to $S\preceq\operatorname{tr}(S)I$, which is true because $x^TSx\le\lambda_\max(S)x^Tx\le\operatorname{tr}(S)x^Tx$ for every vector $x$.