What is the necessary and sufficient condition (if there is any) that $n$ orthonormal vectors $v_1,v_2,\cdots,v_n$ are eigenvectors of a Euclidean distance matrix. When $n=2$, the orthonormal vectors are easily charcterized, i.e., $(1/\sqrt{2}, 1/\sqrt{2})$ and $(1/\sqrt{2}, 1/\sqrt{2})$.
This isn't an answer, but it's too long for a comment. As you're maybe aware, a real $n \times n$ matrix $M$ is a Euclidean distance matrix if and only if the following conditions hold:
 $M_{ij} \geq 0$ for all $i, j$
 $M_{ii} = 0$ for all $i$
 $M$ is symmetric
 $M$ is conditionally negative definite, that is, $$ x^t M x \leq 0 $$ whenever $x \in \mathbb{R}^n$ with $\sum_i x_i = 0$.
This was shown in: I. J. Schoenberg, Metric spaces and positive definite functions, Transactions of the AMS 44 (1938), 522536.

$\begingroup$ +1, Thanks, I know this fact. Do you think if it is possible to characterize the orthogonal matrix $P$ such that $P^TMP$ is diagonal? $\endgroup$– SunniAug 8 '11 at 22:56

$\begingroup$ OK, sorry not to have added anything new. (Personally I find this fact of Schoenberg's rather surprising, in that the triangle inequality doesn't have to be mentioned.) I'm afraid I don't have any further thoughts. $\endgroup$ Aug 9 '11 at 0:22