Trace of product of semidefinite matrices is nonnegative

Question

I want to prove this:

$A$ is a symmetric positive semi-definite matrix $\Leftrightarrow$ $tr(AB) \geq 0$ $\forall $ B positive semi-definite.

I tried using eigenvalues, because they all have to be non-negative, but that didn't help me too much, as the eigenvalues of $AB$ are different from those of $A$ or $B$.

I would like some tips about where to start.

Answer 1

Here are some hints. I would prove your claim using a combination of the following facts:

1) Trace of a product of matrices is invariant under cyclic permutation of those matrices.

2) Every symmetric positive-semidefinite matrix has a symmetric positive-semidefinite square root.

3) If a matrix $A$ is symmetric positive-semidefinite, so is $M^TAM$ for any $M$.