Spectral properties of finite metric sets

Question

Given a finite metric set $S=\{P_1,\dots,P_n\}$, one gets a real symmetric matrix $M=M(S)$ with rows and columns indexed by elements of $S$ by setting $M_{i,j}=d(P_i,P_j)$. It is easy to see that $M$ has at least one strictly positive and one strictly negative eigenvalue if $S$ contains at least $2$ points. For metric sets of three points, the matrix $M$ has always signature $(1,2)$ (one strictly positive and two strictly negative eigenvalues). (This holds in fact for any symmetric $3\times 3$ matrix with zero diagonal and strictly positive off-diagonal coefficients.) In particular, we have always at least two strictly negative eigenvalues if $n\geq 3$.

It seems quite difficult to have more than one strictly positive eigenvalue if $n$ is small (I have an example with $n=9$).

Given an integer $d\geq 2$, what is the smallest number $n=n(d)$ such that there exists a finite metric space $S$ with $n$ elements giving rise to a matrix $M$ having $d$ non-negative eigenvalues?

So far, all I know is $3< n(2)\leq 9$.

Update: $n(2)=4$, realized by the metric space with two pairs of points $A,B$ and $C,D$ at distance $2$, all other distances between distinct points are $1$. (The corresponding matrix $M$ has eigenvalues $-2,-2,0,4$).

I have an example with five points having two strictly positive eigenvalues.

Other bounds: $n(3)\leq 6$ (my example has however $0$ as an eigenvalue and only for $n=7$ do I have an example with three strictly positive eigenvalues), $n(4)\leq 9$ and $n(5)\leq 12$.

Answer 1

Here's an answer if you make a further assumption on your metric space: if $M$ is of strictly negative type, then it has $n-1$ negative eigenvalues, according to Lemma 3.6 of this paper. This condition means that $$ \sum_{i,j} M_{ij} x_i x_j < 0 $$ whenever $\sum_i x_i = 0$ and the $x_i$ are not all $0$, and it holds, for example, if your metric space is a subset of Euclidean space.

Added: it's maybe worth adding (although it doesn't directly bear on your question) that if $M$ is just of negative type (only $\le$ holds in the inequality above), then Lemma 3.6 also shows that $M$ has exactly one positive eigenvalue.

NB: There's a statement about 4-point spaces in the abstract of that paper which appears to contradict your 4-point example. The actual result (Proposition 6.1) includes an extra hypothesis that excludes that example.

Added, part 2: I realized I wrote the above in a way that emphasizes the wrong points. Lemma 3.6 in that paper is of course trivial. The real point is that the terminology strictly negative type is worth knowing, so that you can find out which metric spaces have that property (and subsets of Euclidean space are among such spaces).