# Spectral properties of finite metric sets

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$.

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.
• Thank you for these informations. It seems to me that there is no known example of subsets of points in a $CAT(0)$ space giving rise to at least two non-negative eigenvalues. Feb 17 '11 at 11:17
• @Suresh: negative type is actually a stronger property than that. The matrix $M$ is of negative type if and only if the matrices $K_{i,j} = e^{-t M_{i,j}}$ are positive definite for every $t > 0$. Feb 17 '11 at 15:49