Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

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

share|improve this answer
1  
More generally, another way to think about this is that if K is a positive definite matrix, then it can be viewed as encoding "similarities" between pairs of points. there's a natural induced distance metric that can be computed from K, and this distance metric is of negative type if and only if K is positive definite. This illustrates the negative eigenvalue matter quite clearly IMO. This post of mine explains things in more detail. geomblog.blogspot.com/2009/08/… –  Suresh Venkat Feb 17 '11 at 9:03
    
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. –  Roland Bacher 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$. –  Mark Meckes Feb 17 '11 at 15:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.