# Is $k(A, B) = \text{Tr}[(A^{1/2} B A^{1/2})^{1/2}]$ a positive definite kernel?

Let $$\mathbb{S}_n$$ denote the set of $$n \times n$$ symmetric positive semidefinite matrices. I am trying to figure out whether $$k: \mathbb{S}_n \times \mathbb{S}_n \to \mathbb{R}_+$$ defined as:

$$k(A, B) = \text{Tr}[(A^{1/2} B A^{1/2})^{1/2}]$$

is a positive definite kernel. Can anyone find a counterexample showing it is not? Or prove it is indeed a positive definite kernel?

Some analysis so far: Having failed to find a counterexample numerically, I am trying to show: $$\sum_{ij} k(A_i, A_j) x_i x_j \geq 0$$ holds for any $$A_1, \dots, A_m \in \mathbb{S}_n$$ and $$x_1, \dots, x_m \in \mathbb{R}$$. Without loss of generality we can assume that $$x_1, \dots, x_m \in \{-1, +1\}$$ since the change of $$x_i \mapsto \text{sign}(x_i)$$ and $$A_i \mapsto x_i^2 A_i$$ preserves the value on the left hand side above and all matrices remain positive semidefinite after this change of variables.

Let $$\mathcal{P}$$ denote the set of indices where $$x_i x_j = +1$$ and let $$\mathcal{N}$$ denote the set of indices where $$x_i x_j = -1$$. Then we just need to show the following inequality holds: $$\sum_{i=1}^m \text{Tr}[A_i] + 2 \sum_{(i,j)\in\mathcal{P}} k(A_i, A_j) \geq 2 \sum_{(i,j)\in\mathcal{N}} k(A_i, A_j)$$ This is where I'm stuck, or maybe a different approach is needed.

• Unless if I'm misunderstanding the definition of positive definite kernel, I think no. Take $A = \text{diag}(1,0)$, $B=\text{diag}(1,1)$ and $C = \text{diag}(0,1)$ and form the associated kernel matrix. The determinant should be $\sqrt{2}-2<0$. Commented Feb 20, 2023 at 5:42
• $\mathbb{S}$ depends on a dimension (size of matrices) and hence the answer should depend on $n$. Shouldn't $\mathbb{S}$ be denoted $\mathbb{S}_n$? (I also assume they are meant to be symmetric)
– YCor
Commented Feb 20, 2023 at 9:09
• Indeed in restriction to 2-dim nonnegative diagonal matrices, this reads as $k((x_1,y_1),(x_2,y_2))=\sqrt{x_1x_2}+\sqrt{y_1y_2}$. For the three matrices $A,B,C$ proposed by @JasonGaitonde we get the Gram matrix $\begin{pmatrix}1 & 1 & 0\\1 & 2 & 1\\ 0 & 1 & 1\end{pmatrix}$ whose eigenvalues are $0,1,3$, so it is $\ge 0$.
– YCor
Commented Feb 20, 2023 at 9:19
• @YCor ah whoops -- bad algebra error! I thought the middle 2 was $\sqrt{2}$... Commented Feb 20, 2023 at 10:41
• Indeed, now that I think about it, diagonal matrices cannot provide a counterexample, as the entries are a genuine Gram matrix after applying the coordinate-wise square root to the underlying diagonal matrices. Interesting question! Commented Feb 20, 2023 at 10:47

Counterexample for $$n = 2$$ :
Let $$A_k$$ be the orthonormal projection on the span of $$(\cos(2 \pi (k-1) / 5), \sin(2 \pi (k-1) / 5))^\mathsf{T} , \quad k = 1...5.$$
Then $$k(A_k,A_l) = \vert \cos(2 \pi (k-l) / 5) \vert$$ .
The corresponding matrix has the eigenvalue $$-0.11803398874989484820458683436563811772$$ with multiplicity $$2$$ .