How to prove a trace matrix is positive (semi) definite?

Question

Assume $X,A,B,C$ are all positive (semi) definite matrices with the same dimension. Define $$ S = \begin{bmatrix} \mbox{tr}(XAXA) & \mbox{tr}(XAXB) & \mbox{tr}(XAXC) \\ \mbox{tr}(XAXB) & \mbox{tr}(XBXB) & \mbox{tr}(XBXC) \\ \mbox{tr}(XAXC) & \mbox{tr}(XBXC) & \mbox{tr}(XCXC) \end{bmatrix}. $$ Can we show that $S$ is a positive (semi) definite matrix? I think probably mathematical induction can be applied since the original problem itself is of $p>3$ dimension, but I still have no specific idea.

To validate if it is the truth, I run the R code below. Here I simulated different positive definite matrices $X,A,B,C$ for $1000$ times and the results showed that all the $S$ matrix is positive definite.

library(clusterGeneration)
K <- 50
ss <- 0
for(i in 1:1000){
  set.seed(i)
  X <- genPositiveDefMat(K)$Sigma
  A <- genPositiveDefMat(K)$Sigma
  B <- genPositiveDefMat(K)$Sigma
  C <- genPositiveDefMat(K)$Sigma
  S <- matrix(0, nrow = 3, ncol = 3)
  S[1,1] = tr(X%*%A%*%X%*%A)
  S[1,2] = S[2,1] = tr(X%*%A%*%X%*%B)
  S[1,3] = S[3,1] = tr(X%*%A%*%X%*%C)
  S[2,2] = tr(X%*%B%*%X%*%B)
  S[3,2] = S[2,3] = tr(X%*%B%*%X%*%C)
  S[3,3] = tr(X%*%C%*%X%*%C)
  ss <- ss + sum(eigen(S)$values > 0)
}
ss # The result ss = 3000 shows that all S is positive definite

---

Motivation

This question comes from the expectation of the 2nd order derivative of a specific log-likelihood function. I just simplified it to a $3$-dimensional problem with $A$, $B$, $C$ matrices.

Answer 1

1. Let $\mathfrak{M}_d(\mathbb{R})$ denote the set of all $d\times d$ matrices with real entries, and we equip this space with the bilinear form $\langle \cdot, \cdot \rangle$ given by

$$ \langle A, B \rangle = \operatorname{tr}(A^{\top}B) = \sum_{i,j\in[d]} a_{ij}b_{ij}. $$

Note that $\langle \cdot, \cdot \rangle$ defines an inner product on $\mathfrak{M}_d(\mathbb{R})$.

2. Now, let $X, A, B, C \in \mathfrak{M}_d(\mathbb{R})$ be positive semi-definite, and let

$$ A_1 = X^{1/2}AX^{1/2}, \qquad A_2 = X^{1/2}BX^{1/2}, \qquad A_3 = X^{1/2}CX^{1/2}, $$

where $X^{1/2}$ is the unique positive semi-definite square root of $X$. Then

$$ \operatorname{tr}(XAXB) = \operatorname{tr}(X^{1/2}AXBX^{1/2}) = \langle A_1, A_2 \rangle $$

and a similar relation for any other combinations. Therefore,

$$ S = \begin{pmatrix} \langle A_1, A_1 \rangle & \langle A_1, A_2 \rangle & \langle A_1, A_3 \rangle \\ \langle A_2, A_1 \rangle & \langle A_2, A_2 \rangle & \langle A_2, A_3 \rangle \\ \langle A_3, A_1 \rangle & \langle A_3, A_2 \rangle & \langle A_3, A_3 \rangle \end{pmatrix} $$

is a Gram matrix and hence is positive semi-definite.