# Can i prove that this matrix is PSD?

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.

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.