Can i prove that this matrix is PSD?

Question

I have matrix $A \in \mathbb{R}^{N \times N}$, such that $A(i,j)=trace(B_iCB_j), \forall ij$.

Matrices $B_i$ and C are PSD and symmetric with positive entries. Can I prove that $A$ is PSD too?

In fact, I've tried different random matrices for $C$ and $B_i$ with different dimensions and $A$ was always PSD.

Answer 1

For any $x \in \mathbb{R}^n$ I will prove that $x^TAx \geq 0$. Let $x \in \mathbb{R}^n$, then $$\begin{align}x^TAx &= \sum_{i,j} x_i x_j \text{tr}(B_iCB_j) \\ &= \text{tr}(\sum_{i,j} x_i x_j B_iCB_j) \\ &= \text{tr}(\sum_{i} \sum_j (x_i B_i)C (x_j B_j)) \\ &= \text{tr}((\sum_{i} x_i B_i)C(\sum_j x_j B_j)) \\ \end{align}$$ Let $D = \sum_{i} x_i B_i$, then this expression equals $\text{tr}(DCD)$. Since $D$ is symmetric, $DCD=D^TCD$, which is positive semidefinite, so the trace is indeed nonnegative.