It's widely known that, given a matrix of squared Euclidean distances, $\mathbf{D}_{ij} = \| \mathbf{X}_i - \mathbf{X}_j \|^2$, and the centering matrix $\mathbf{H} = \mathbf{I} - \dfrac{1}{n}11^T$, the matrix: $$ -\dfrac{1}{2} \mathbf{HDH}$$ is positive semidefinite. This can be verified pretty easily for centered $\mathbf{X}$ as $-0.5 \mathbf{HDH}=\mathbf{XX^T}$.
In some (more modern sources), this is presented as an if-and-only-if condition (i.e. $-\mathbf{HDH}$ is PSD iff $\mathbf{D}$ is a squared Euclidean distance matrix), and I believe that this is a bit misleading.
Schoenberg (1935) (a nice summary can be found here) states that $\mathbf{X}$ can isometrically be embedded into the Euclidean space if and only if this is PSD: $$ \mathbf{A}_{ij} = d(x_0, x_i)^2 + d(x_0, x_j)^2 - d(x_i, x_j)^2 $$ for any distance metric $d$, suggesting that for some metrics, we can find a Euclidean embedding such that its Euclidean distances result in the distance matrix under our original metric. So, $-\mathbf{HDH}$ would be PSD for these cases.
Given a lack of stronger results known about these matrices, and the folk wisdom that one should be careful with assuming PSDness of double centered distance matrices for non-Euclidean distance matrices, especially while doing MDS, I'm looking for:
An example that shows that $-\mathbf{HDH}$ is not PSD using a certain distance metric and a certain set of points, where $\mathbf{D}_{ij} = d(\mathbf{X}_i, \mathbf{X}_j)^2$ for some distance metric.
I guess corresponding to the case where one can't isometrically embed the data into a Euclidean space. If possible, I'd love for the distance metric in the example to be a non-graph based distance function.
