For a matrix, how to prove its max eigenvalue max inner product with any matrix which is semidefinite and has a trace less than 1?

Question

How to prove the equation in (22) in 1801.09344? For simplicity, I re-describe it here:

$$\max_{P \succeq0, \operatorname{trace}(P) \leq 1}\! \langle A,P\mkern1.5mu\rangle= \lambda_+(A)$$

where $\lambda_+(A)$ is the maximum eigenvalue of A.

Answer 1

For $P$ a self adjoint operator, consider a diagonalization $$P=\sum \mu_i |v_i \rangle \langle v_i|$$ where $|v_i \rangle$ is an orthonormal basis of the space. For $A$ any matrix, we have $$\langle A, P\rangle = \sum \mu_i \langle A v_i, v_i\rangle$$ If $A$ is self adjoint with $\lambda_{+}(A)$ its largest eigenvalue, and $P\succeq 0$ ( that is $\mu_i \ge 0$ for all $i$) we have $$\langle A, P\rangle\le \sum \mu_i \cdot \lambda_{+}(A)\langle v_i, v_i \rangle = \lambda_{+}(A)\cdot \sum \mu_i = \lambda_{+}(A) \cdot trace(P)$$

Moreover, if $e$ is a unit eigenvector of $A$ for the eigenvalue $\lambda_{+}(A)$ we have for $P=|e\rangle \langle e|$, $trace(P)=1$ and $\langle A,P\rangle = \langle A e, e\rangle = \lambda_{+}(A)$