Distance Matrices and Isometric Embeddings
We review the relations between distance matrices and isometric embeddings and give simple proofs that distance matrices de ned on euclidean and spherical spaces have all eigenvalues except one nonpositive. Several generalizations are discussed.
Gespeichert in:
| Datum: | 2008 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН України
2008
|
| Schriftenreihe: | Журнал математической физики, анализа, геометрии |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/106492 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Distance Matrices and Isometric Embeddings / E. Bogomolny, O. Bohigas, C. Schmit // Журнал математической физики, анализа, геометрии. — 2008. — Т. 4, № 1. — С. 7-23. — Бібліогр.: 14 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-106492 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1064922016-09-30T03:02:43Z Distance Matrices and Isometric Embeddings Bogomolny, E. Bohigas, O. Schmit, C. We review the relations between distance matrices and isometric embeddings and give simple proofs that distance matrices de ned on euclidean and spherical spaces have all eigenvalues except one nonpositive. Several generalizations are discussed. 2008 Article Distance Matrices and Isometric Embeddings / E. Bogomolny, O. Bohigas, C. Schmit // Журнал математической физики, анализа, геометрии. — 2008. — Т. 4, № 1. — С. 7-23. — Бібліогр.: 14 назв. — англ. 1812-9471 http://dspace.nbuv.gov.ua/handle/123456789/106492 en Журнал математической физики, анализа, геометрии Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We review the relations between distance matrices and isometric embeddings and give simple proofs that distance matrices de ned on euclidean and spherical spaces have all eigenvalues except one nonpositive. Several generalizations are discussed. |
| format |
Article |
| author |
Bogomolny, E. Bohigas, O. Schmit, C. |
| spellingShingle |
Bogomolny, E. Bohigas, O. Schmit, C. Distance Matrices and Isometric Embeddings Журнал математической физики, анализа, геометрии |
| author_facet |
Bogomolny, E. Bohigas, O. Schmit, C. |
| author_sort |
Bogomolny, E. |
| title |
Distance Matrices and Isometric Embeddings |
| title_short |
Distance Matrices and Isometric Embeddings |
| title_full |
Distance Matrices and Isometric Embeddings |
| title_fullStr |
Distance Matrices and Isometric Embeddings |
| title_full_unstemmed |
Distance Matrices and Isometric Embeddings |
| title_sort |
distance matrices and isometric embeddings |
| publisher |
Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН України |
| publishDate |
2008 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/106492 |
| citation_txt |
Distance Matrices and Isometric Embeddings / E. Bogomolny, O. Bohigas, C. Schmit // Журнал математической физики, анализа, геометрии. — 2008. — Т. 4, № 1. — С. 7-23. — Бібліогр.: 14 назв. — англ. |
| series |
Журнал математической физики, анализа, геометрии |
| work_keys_str_mv |
AT bogomolnye distancematricesandisometricembeddings AT bohigaso distancematricesandisometricembeddings AT schmitc distancematricesandisometricembeddings |
| first_indexed |
2025-07-07T18:33:36Z |
| last_indexed |
2025-07-07T18:33:36Z |
| _version_ |
1837014153111273472 |
| fulltext |
Journal of Mathematical Physics, Analysis, Geometry
2008, vol. 4, No. 1, pp. 7�23
Distance Matrices and Isometric Embeddings
E. Bogomolny, O. Bohigas, and C. Schmit
Universit�e Patis-Sud, CNRS, UMR 8626
Laboratoire de Physique Th�eorique et Mod�eles Statistiques
91405 Orsay Cedex, France
E-mail:eugene.bohomolny@lptms.u-psud.fr
oriol.bohigas@lptms.u-psud.fr
Received October 10, 2007
We review the relations between distance matrices and isometric embed-
dings and give simple proofs that distance matrices de�ned on euclidean
and spherical spaces have all eigenvalues except one nonpositive. Several
generalizations are discussed.
Key words: Anderson model, localization, Wegner estimate.
Mathematics Subject Classi�cation 2000: 15A52, 82B41.
1. Introduction
Matrices with random (or pseudorandom) elements appear naturally in dif-
ferent physical problems and their statistical properties have been thoroughly
studied (see e.g. [1]). A special case of random matrices, called distance matrices,
has been recently proposed in [2]. They are de�ned for any metric space X with
a probability measure � on it as follows. Choose N points ~xj 2 X randomly
distributed according to the measure �. The matrix element Mij of the N � N
distance matrix M equals the distance on X between points ~xi and ~xj
Mij = distance(~xi; ~xj); i; j = 1; : : : ; N : (1)
In [3] we discussed the eigenvalue density for distance matrices de�ned on certain
manifolds. When �rst numerical calculations were performed, an intriguing fact
was observed, namely, all eigenvalues (except one) of distance matrices on eu-
clidean and spherical manifolds were nonpositive. However, this property was not
ful�lled e.g. for points on a torus. Typically, the eigenvalues of generic random
matrices occupy the whole available energy space. To have all of them but one
nonpositive one needs to control the signs of all principal minors (see Sect. 3.)
which is usually di�cult to do. While studying this fact we found a direct proof
that for distance matrices over manifolds embedded into the euclidean space this
c
E. Bogomolny, O. Bohigas, and C. Schmit , 2008
E. Bogomolny, O. Bohigas, and C. Schmit
property is automatically ful�lled. The relation between very basic geometri-
cal properties of a manifold and spectral properties of its distance matrix was
unexpected for us but analyzing the literature we found that it was proved by
Schoenberg in the thirties [4, 5]. In [3] we noted this fact without details. Nev-
ertheless, after many discussions on di�erent occasions it became clear that this
type of problems is practically unknown in the physics community and we think
that it is of interest to present simple proofs of the main statements. The material
in this note is not new (general references are [6�8]) but it seems that it has not
been discussed in the random matrix community.
By de�nition of distance the matrix elements of a distance matrix have the
following properties:
a) positivity
Mij � 0 and Mij = 0 only when i = j; (2)
b) symmetry
Mij = Mji; (3)
c) triangular inequalities
Mij �Mik +Mkj for all i, j, k: (4)
Eigenvalues �p and eigenvectors u
(p)
j of distance matrices are de�ned in the usual
way
NX
j=1
Miju
(p)
j = �pu
(p)
i : (5)
Distance matrices (1) are real symmetric matrices and their eigenvalues are real.
As all matrix elements of distance matrices are nonnegative, the application of
the Perron�Frobenius theorem ([9, v. 2 p. 49]) states that these matrices have one
special positive eigenvalue �0 > 0 with the largest modulus. All other eigenvalues
obey the inequality
j�j j � �0: (6)
As distance matrices have only real eigenvalues the equality is possible only if
there is a negative eigenvalue �0 = ��0.
The subject of this note is to show that the eigenvalues of distance matrices
de�ned on the euclidean or a spherical space� are all nonpositive
�i � 0; i = 1; : : : ; N � 1; (7)
except the above-mentioned Perron�Frobenius eigenvalue �0 and that this re-
markable property is mainly a consequence of the possibility of isometric em-
bedding of a �nite metric space with a given distance matrix into the euclidean
space.
�It means that the points ~xj lie in the d-dimensional euclidean space or on a sphere.
8 Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1
Distance Matrices and Isometric Embeddings
We also note that if, instead of distance matrix (1), one considers new matrices
M
(
)
ij = [distance(~xi; ~xj)]
; (8)
their eigenvalues also obey inequality (7) provided the exponent in the range
0 <
� 2 for the euclidean space and 0 <
� 1 for the spherical one.
The plan of this paper is the following. It is shown in Sect. 2 that if a �nite
metric space can be isometrically embedded into the euclidean space, then the
matrix whose elements are the squares of distances between initial points is of
negative type (cf. (20)�(21)). The inverse theorem is also true, namely, if a matrix
N is of negative type, then the matrix with elements
p
Nij can be embedded into
the euclidean space. A direct proof of the main theorem that matrices of negative
type have all eigenvalues, except one, nonpositive, is presented in Sect. 3. In
Section 4 it is shown that if a matrix Nij is of negative type, a new matrix N
ij
with 0 <
� 1 will also be of negative type. The general form of such metric
transforms is also shortly discussed in this section. The spherical spaces are
discussed in Sect. 5 and in Sect. 6 a simple proof that geodesic distance matrices
for the spherical spaces are of negative type is presented. A resum�e of the results
is given in Sect. 7. The derivation of the Cayley�Menger formula for the volume
of multidimensional simplex is reproduced for completeness in the Appendix.
2. Isometric Embedding
Assume that we know a �nite matrix M whose matrix elements Mij , i; j =
1; : : : ; N , obey all properties of the distance (2)�(4). The isometric embedding
into the euclidean space is to �nd points ~xi, if any, belonging to an euclidean space
Rn such that the euclidean distance between each pair of points i; j coincides with
Mij
jj~xi � ~xj jj =Mij ; (9)
for all i, j = 1; : : : ; N . Here jj : : : jj is the euclidean distance
Dij � jj~xi � ~xj jj =
vuut nX
k=1
�
x
(k)
i � x
(k)
j
�2
(10)
and x
(k)
i with k = 1; : : : ; n are the euclidean coordinates of the n-dimensional
point ~xi.
The necessary and su�cient conditions of the existence of solutions of (9) can
be obtained from the following considerations [4] and [6, 7]. Choose a point, say
~xN , and consider the vectors ~yi = ~xi � ~xN with i = 1; : : : ; N � 1. They form
a simplex in the n-dimensional space Rn. Construct the (N � 1) � n matrix of
Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1 9
E. Bogomolny, O. Bohigas, and C. Schmit
coordinates of these vectors
Vik = y
(k)
i i = 1; : : : ; N � 1; k = 1; : : : ; n; (11)
and multiply it by its transpose. The result is a (N �1)� (N �1) real symmetric
matrix C = V T � V of scalar products
Cij = ~yi � ~yj; i; j = 1; : : : ; N � 1 : (12)
Because vectors ~yj belong to the euclidean space, their scalar products can be
expressed by the distances between points
~yi � ~yj =
1
2
(jj~yijj2 + jj~yj jj2 � jj~yi � ~yjjj2): (13)
Therefore the matrix Cij can be found from the squares of matrix elements of the
distance matrix
Cij =
1
2
(M2
iN +M2
jN �M2
ij): (14)
If points ~xj obeying (9) do exist, then by construction the matrix Cij is such that
the quadratic form
(�C�) =
N�1X
i;j=1
Cij�i�j �
NX
i=1
�i~yi
!2
(15)
is nonnegative (� 0) for any choice of real numbers �1; �2; : : : ; �N�1. Inversely, if
one has a symmetric positive matrix C, it can be written in the form
C = UTU; (16)
where matrix U can be chosen, e.g., in the lower triangular form (the Cholesky
decomposition). Then the elements of U = y
(k)
i give directly the coordinates y
(k)
i
of points obeying (14) which solve the problem of the isometric embedding.
The quadratic form (15) can be rewritten in a simpler form by introducing a
new variable �N = �PN�1
j=1 �j. Then
(�C�) = �1
2
NX
i;j=1
M2
ij�i�j : (17)
Therefore the necessary and su�cient condition of the existence of isometric em-
bedding of a �nite metric space with the distance matrix M into the euclidean
space is that a new matrix N whose matrix elements equal the square of matrix
elements of the matrix M
Nij = M2
ij (18)
10 Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1
Distance Matrices and Isometric Embeddings
is such that the quadratic form associated with it,
(�N�) =
NX
i;j=1
Nij�i�j; (19)
is nonpositive
NX
i;j=1
�iNij�j � 0 (20)
for all choices of real numbers �j , j = 1; : : : ; N , with zero sum
NX
j=1
�j = 0: (21)
In general, a real symmetric matrix obeying these conditions is called a matrix of
negative type.
The Schoenberg theorem states that if a metric space with a distance matrix
Mij can be isometrically embedded into the euclidean space, the matrix M2
ij is of
negative type and if a matrix Nij is of negative type, the metric space with the
distance matrix
p
Nij can be isometrically embedded into the euclidean space.
The minimal dimension of the embedded euclidean space is the rank of the matrix
Cij in 14.
3. Eigenvalues of Negative Type Matrices
In this section we present, following [5], the direct proof that any matrix Nij
of the negative type has all eigenvalues except one nonpositive (� 0). An indirect
proof of this statement can be found in [8].
The law of inertia (see e.g. [9, v. 1 p. 298]) states that if a real quadratic form
(xNx) =
NX
i;j=1
Nijxixj (22)
is transformed into a sum of squares of independent linear forms Xi =
PN
j=1 cijxj
(xNx) =
rX
i=1
biX
2
i ; (23)
then the total number of positive and negative coe�cients bi is independent of
the representation. In particular, in the eigenbasis of the real symmetric matrix
Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1 11
E. Bogomolny, O. Bohigas, and C. Schmit
Nij
(xNx) =
NX
i=1
�iu
2
i (24)
and the law of inertia permits to determine the number of positive and negative
eigenvalues �i.
According to the Jacobi theorem (see e.g. [9, v. 1 p. 305]), if the principal
minors �j of a matrix are nonzero, then the number of positive (resp. negative)
terms in (23) coincides with the number of conservation (resp. alteration) of signs
in the sequence
1;�1;�2; : : : ;�N (25)
(we assume that the matrix aij is of full rank). Recall that the principal minor
�n of a matrix N is the determinant of the left-upper n� n submatrix
�n =
���������
N11 N12 N13 : : : N1n
N12 N22 N23 : : : N2n
...
...
...
...
...
N1n N2n : : : Nn�1 n Nnn
���������
: (26)
For distance matrices Nii = 0 and �1 � 0 which prevents the direct application
of the Jacobi theorem. This formal di�culty, for example, can be overcome as
follows. It is clear that the eigenvalues and other principal minors of generic
distance matrices are nonzero. Therefore if one adds to N a diagonal matrix �Æij
with small � the signs of eigenvalues will not change. But in such a case �1 = �
and the sequence (25) takes the form
1; �;�2;�3; : : : ;�N : (27)
We shall prove below that principal minors �n of distance matrices of negative
type have alternating sign
�n = (�1)n�1v2n; n = 2; 3; : : : ; N: (28)
Irrespective of the sign of � there is one conservation of sign and N �1 alterations
of signs in the sequence (27). Therefore, according to the Jacobi theorem, distance
matrices of negative type have one positive (the Perron�Frobenius) eigenvalue and
all other eigenvalues are nonpositive.
Because the matrix Nij is of negative type, the metric space with the distancep
Nij can be embedded into the euclidean space. It means that there exist points
~xj in the euclidean space such that the euclidean distances between any pairs of
points equal
~Dij =
p
Nij : (29)
12 Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1
Distance Matrices and Isometric Embeddings
Let us consider one of these points as the origin (say ~x1). Points ~x2; : : : ; ~xn can
be viewed as vertices of a (n � 1)-dimensional simplex. Denote ~D1i = ri. Then
the distance between any pair of points can be expressed as follows
~Dij =
q
r2i + r2j � 2rirj cos'ij ; (30)
where 'ij is the euclidean angle between vectors ~xi � ~x1 and ~xj � ~x1.
Let us perform an inversion ri ! 1=ri for all i = 2; : : : ; n. Then instead of
n�1 points ~x2; : : : ; ~xn we get a new set of n�1 euclidean points ~~x2; : : : ; ~~xn whose
mutual distances Dij can be expressed through the old distances as
Dij =
s
1
r2i
+
1
r2j
� 2
1
rirj
cos'ij =
~Dij
~D1i
~D1j
: (31)
Because the points ~xj belong to the euclidean space the new points ~~xj with
j = 2; : : : ; N plus the point ~x1 form a n� 1-dimensional euclidean simplex. The
volume of this simplex can be computed by the Cayley�Menger determinantal
formula (see e.g. [12, p. 124] and also [13] for an early reference) which expresses
the volume V (P1; : : : ; Pn) of an n-dimensional euclidean simplex by the lengths
of its sides
V 2(P1; : : : ; Pn) =
(�1)n
2n�1[(n� 1)!]2
D(P1; : : : ; Pn); (32)
where the Cayley�Menger determinant is
D(P1; : : : ; Pn) =
���������
0 1 1 : : : 1
1 0 D2
12 : : : D2
1n
...
...
...
...
...
1 D2
1n D2
2n : : : 0
���������
; (33)
and Dij are the distances between points i and j for i; j = 1; : : : ; n. For com-
pleteness we give a derivation of this formula in Appendix .
In our case the lengths of the transformed simplex are given by (31). As each
~Dij =
p
Nij, the squares of the lengths which enter the Cayley�Menger formula
(33) are
D2
ij =
Ni;j
N1iN1j
: (34)
Therefore for each n = 2; : : : ; N
D(~y2; : : : ~yn) �
������������
0 1 1 : : : 1
1 0 N23
N12N13
: : : N2n
N12N1n
1 N32
N13N12
0 : : : N3n
N13N1n
...
...
...
...
...
1 Nn2
N1nN12
Nn3
N1nN1n
: : : 0
������������
: (35)
Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1 13
E. Bogomolny, O. Bohigas, and C. Schmit
As the determinant is a multilinear form of row and columns by multiplication of
each row (ij) and each column (ji) by Nij one gets
D(~y2; : : : ~yn) = [N12N13 : : : N1N ]�2
�����������
0 N12 N13 : : : N1n
N21 0 N23 : : : N2n
N31 N32 0 : : : N3n
...
...
...
...
...
Nn1 Nn2 Nn3 : : : 0
�����������
: (36)
But the determinant in this expression coincides with the principal minor of the
initial distance matrix. Therefore
�n = (�1)n�1[N12N13 : : : N1N ]22n�1[(n� 1)!]2V 2(~y1; : : : ; ~yn) ; (37)
which proves that the principal minors of matrices of negative type are of alternate
signs. This relation, as explained above, implies that all eigenvalues of such
matrices (except possibly one) are nonpositive.
4. Metric Transform
The problem of isometric embedding gives rise to di�erent generalizations.
One type of question is the following. Let the points ~xj with j = 1; : : : ; N be
the points of the euclidean space Rn. Find all functions F (r) (called metric
transforms) such that the �nite metric space with the distance matrix
Mij = F (jj~xi � ~xjjj) (38)
can be embedded into an euclidean space Rk with certain k. Here jj~xi � ~xjjj is
the euclidean distance (10) between points ~xi and ~xj .
In [5] it was proved that general metric transforms can be expressed via radial
positive de�nite functions. A real function f(r) is called radial positive de�nite
provided
NX
i;j=1
f(jj~xi � ~xjjj)�i�j � 0 (39)
for all choices of points ~xi 2 Rn and of real numbers �.
An important example of this function is
f(r) = exp(��2r2) : (40)
The positive de�nite property of the function is a direct consequence of the well-
known formula
exp(��2jj~xjj2) = 1
(4�)n=2
Z
Rn
ei�~x�
~k exp(�jj~kjj2)dnk ; (41)
14 Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1
Distance Matrices and Isometric Embeddings
from which it follows that
NX
i;j=1
�i�je
��2jj~xi�~xj jj
2
=
1
(4�)n=2
Z
Rn
�����
NX
i=1
�ie
i�~xi�~k
�����
2
e�jj~kjj2dnk � 0 : (42)
The following theorem is easily proved [5]. The �nite metric space with a distance
matrix Mij can be isometrically embedded into the euclidean space if and only if
the quadratic form
NX
i;j=1
exp(��2M2
ij)�i�j (43)
is nonnegative (� 0) for all choices of real numbers �j and all �! 0.
The proof is as follows. If the space can be isometrically embedded into the
euclidean space, then there exist points ~xj 2 Rn such that Mij = jj~xi � ~xjjj.
Because exp(��2r2) is a radial positive de�nite function, the quadratic form (43)
is nonnegative. Conversely, if the quadratic form is nonnegative for �! 0, then
NX
i:j=1
(1� �M2
ij)�i�j � 0 (44)
for all �j. In view of the condition
PN
j=1 �j = 0; the �rst term vanishes and the
above inequality reduces to (19), thus proving the existence of the embedding.
The fact that exp(��2r2) is a radially positive de�nite function permits also
to prove [5] that the metric space with the distance equal a power of the euclidean
distance
M 0
ij = jj~xi � ~xj jj
i; j = 1; : : : ; N ; (45)
where ~xi 2 Rn and 0 <
� 1 can be embedded into the euclidean space. The
proof follows from the identity valid for 0 <
� 1
jtj2
= c
1Z
0
(1� exp(��2t2)) d�
�1+2
; (46)
with
c�1
=
1Z
0
(1� exp(�2))
d�
�1+2
> 0 : (47)
Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1 15
E. Bogomolny, O. Bohigas, and C. Schmit
One has
X
ij
jj~xi � ~xj jj2
�i�j = c
X
ij
�i�j
1Z
0
(1� e��2jj~xi�~xj jj
2
)
d�
�1+2
= c
1Z
0
��X
i
�i
�2
�
�X
ij
e��2jj~xi�~xj jj
2
�i�j
��
d�
�1+2
: (48)
If
P
i �i = 0; then the �rst term is zero and as e��2r2 is radial positive de�nite,
the right-hand side is negative which proves that the matrix
jj~xi � ~xj jj2
(49)
with 0 <
� 1 is of negative type and the metric space with the distance (45)
can be embedded into the euclidean space.
Combining together the above theorems, one concludes that if a matrix Nij is
of negative type, then the matrix N
ij with 0 <
� 1 is also of negative type and
all its eigenvalues, except at most one, are nonpositive.
General radial positive de�nite functions f(r) have the form [5]
f(r) =
1Z
0
N (ru)d�(u) ; (50)
where the measure � is nonnegative, �(u) � 0, and the function
N (r) is the
integral of ei
~k�~x with jj~xjj = r over the (N � 1)-dimensional sphere
N(r) =
1
!N�1
Z
SN�1
ei~x�
~kd�N�1 = �
�
N
2
��
2
r
�(N�2)=2
J(N�2)=2(r) : (51)
Here !N�1 = 2�N=2=�(N=2) is the volume of the (N � 1)-dimensional sphere,
�(x) is the Gamma function, and Jn(x) is the Bessel function.
From the theorem (43) it follows [5] that the general form of a metric transform
is
F (r) =
8<
:
1Z
0
1�
N (ru)
u2
d�(u)
9=
;
1=2
(52)
with a positive measure �(u) such that
R1
0 d�(u)=u2 exists.
16 Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1
Distance Matrices and Isometric Embeddings
5. Spherical Spaces
Equation (52) gives the general form of the metric transforms which transform
an euclidean space into another euclidean space. Similar questions can be asked
about the unit radius spherical spaces� Sd�1 which consist of points ~xj 2 Rd
obeying
~x21 + ~x22 + : : :+ ~x2d = 1: (53)
The geodesic distance on the sphere is
d(~x; ~y ) = arccos(~x � ~y ): (54)
The necessary and su�cient conditions that a metric space with the distance ma-
trix Mij can be embedded isometrically into the spherical space with the distance
(54) coincide with the condition that N initial points plus one point at the origin
can be embedded into the euclidean space. From (13) it follows that the later can
be expressed as the nonnegativity condition of the quadratic form
NX
i;j=1
cos(Mij)�i�j � 0 (55)
for all choices of real numbers �j .
Similarly as for the euclidean spaces one can �nd all positive de�nite functions
on the spherical spaces. In [10] it was proved that these functions have the form
g(t) =
1X
l=0
alC
p=2
l (cos t); (56)
where all coe�cients al are nonnegative al � 0. Here p = d� 2 and Ck
l (cos t) are
the Gegenbauer polynomials.
This condition can easily be understood from the expression of the Gegenbauer
polynomial through the orthogonal set of the hyperspherical harmonics Y
(k)
l (~x )
(see e.g. [11, 11.4.2])
C
p=2
l (~x � ~y )
C
p=2
l (1)
=
!d�1
h(p; l)
h(p;l)X
k=1
Y
(k)
l (~x )Y
(k)
l (~y ); (57)
where h(p; l) is the dimension of the irreducible representations of the d � 1 di-
mensional rotation group
h(p; l) = (2l + p)
(l + p� 1)!
p! l!
: (58)
�Modi�cations for spherical spaces of radius R are evident.
Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1 17
E. Bogomolny, O. Bohigas, and C. Schmit
If (56) is valid, one has
NX
i;j=1
g(d(~xi; ~xj))�i�j = !d�1
1X
l=0
al
h(p; l)
h(p;l)X
k=1
������
NX
j=1
Y
(k)
l (~xj)�j
������
2
; (59)
which is evidently nonnegative (� 0).
6. Embedding of the Spherical Space into the Euclidean Space
In this section we show that distance matrices resulting from spherical geo-
desic distances are of negative type and, consequently, the metric space with the
distance equal the square root of spherical distances can be embedded into the
euclidean space.
The proof is based on the following lemma: the spherical geodesic distance
(54) has the expansion
d(~x; ~y) � arccos(~x � ~y ) = �0 +
X
l=odd
�lC
p=2
l (~x � ~y) ; (60)
where all �l with odd l are negative but �0 is positive.
Equation (60) is the expansion of arccos(t) over d-dimensional spherical har-
monics. The coe�cients �l of this series are
�l =
1
hl(p)
�Z
0
�C
p=2
l (cos �) sinp �d� ; (61)
where hl(p) is the normalization integral of the Gegenbauer polynomials
hl(p) =
�Z
0
[C
p=2
l (cos �)]2 sinp �d� (62)
whose explicit expression is (see e.g. [11, 10.9.7])
hl(p) =
p
�(l + p� 1)!�((p+ 1)=2)
(l + p=2)l!(p� 1)!�(p=2)
: (63)
As C�
0 = 1, one gets
�0 =
�
2
: (64)
To compute �l with l 6= 0 it is convenient to use the Gegenbauer integral (see e.g.
[11, 10.9.38])
n!
�Z
0
eiz cos �C�
n(cos �) sin
2� �d� = 2�
p
��(�+ 1=2)
�(n + 2�)
�(2�)
inz��Jn+�(z); (65)
18 Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1
Distance Matrices and Isometric Embeddings
from which one obtains (cf. [11, 11.4])
�l = il2p=2(l + p=2)�(p=2)
1Z
�1
t�p=2Jl+p=2(t)f̂(t)dt; (66)
where f̂(t) is the Fourier transform of the initial function
f̂(t) =
1
2�
�Z
0
� sin �e�it cos �d� =
1
2it
(eit � J0(t)): (67)
To the two terms in f̂(t) there are two corresponding terms in �l. The integral
including eit is zero for all l 6= 0 and the integral with J0(t) is zero for even l. For
odd l
�l = �il�12p=2(l + p=2)�(p=2)
1Z
0
t�1�p=2Jl+p=2(t)J0(t)dt : (68)
The last integral can be computed using the integral ([11, 7.7.4.30])
1Z
0
t��J�(t)J�(t)dt = (69)
�(�)�((1 + � + �� �)=2)
2��((1 + � � �+ �)=2)�((1 + � + �+ �)=2)�((1 + �� � + �)=2)
:
The �nal result is
�l = �p(p+ 2l)
8�
�
�(p=2)�(l=2)
�(1 + (l + p)=2)
�2
: (70)
This expression is negative which proves the lemma.
Using this lemma and (57), one concludes that
NX
i;j=1
d(~xi; ~xj)�i�j = �0(
NX
i=1
�i)
2 +
X
l=odd
�l
h(p; l)
h(p;l)X
k=1
������
NX
j=1
�jY
(k)
l (~xj))
������
2
: (71)
As all �l with l � 1 are negative, this expression is negative for all choices of
�j such that
PN
j=1 �j = 0, i.e., the spherical geodesic distance matrices are of
negative type.
From the theorem of the preceding sections it follows that a new metric space
with the distance
d(
)(~x; ~y) = [arccos(~x � ~y )]
(72)
Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1 19
E. Bogomolny, O. Bohigas, and C. Schmit
is also of negative type when 0 <
� 1 and the space with the distance
[arccos(~x � ~y )]
=2 (73)
can be isometrically embedded into the euclidean space.
7. Conclusion
The distance matrices for points in the euclidean and spherical spaces are of neg-
ative type and, consequently, they have all eigenvalues, except one, nonpositive.
More generally, if points ~xj belong to the euclidean space, the above statement
is true for the matrices
jj~xi � ~xj jj2
(74)
with 0 <
� 1.
If points ~xj belong to the spherical space with the distance d(~xi; ~xj) given by
(54), then the matrix
d
(~xi; ~xj) (75)
with 0 <
� 1 is of negative type and has all eigenvalues, except one, non-
negative.
The following theorems are also of interest.
The matrices with elements
exp(��2jj~xi � ~xj jj2
) (76)
with 0 <
� 1 are positive de�nite and have all eigenvalues positive for all �! 0.
For
= 1 this fact was mentioned in [14].
The similar theorem for the spherical space states that matrices
exp(��2d
(~xi; ~xj)) (77)
with 0 <
� 1 are positive de�nite for all �.
Acknowledgments
The Authors are indebted to A.M. Vershik for discussion on his work [2] prior
to publication and to L.A. Pastur for stimulating remarks.
20 Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1
Distance Matrices and Isometric Embeddings
Appendix
The purpose of this Appendix is to give, following [12], a proof of the Cayley�
Menger determinantal formula (32).
The volume Vn of the n-dimensional Euclidean simplex with one vertex on a
point ~xn+1 and n vertices on points ~xj with j = 1; : : : ; n is proportional to the
determinant of components of the n vectors ~xj � ~xn+1
Vn =
1
n!
����������
x
(1)
1 � x
(1)
n+1 x
(2)
1 � x
(2)
n+1 : : : x
(n)
1 � x
(n)
n+1
x
(1)
2 � x
(1)
n+1 x
(2)
2 � x
(2)
n+1 : : : x
(n)
2 � x
(n)
n+1
...
...
...
...
x
(1)
n � x
(1)
n+1 x
(2)
n � x
(2)
n+1 : : : x
(n)
n � x
(n)
n+1
����������
: (78)
As above the subscripts denote the points and the superscripts denote their coor-
dinates. This expression can be rewritten in a more symmetric form through the
determinant of the (n+ 1)� (n+ 1) matrix
Vn =
1
n!
������������
x
(1)
1 x
(2)
1 : : : x
(n)
1 1
x
(1)
2 x
(2)
2 : : : x
(n)
2 1
...
...
...
...
...
x
(1)
n x
(2)
n : : : x
(n)
n 1
x
(1)
n+1 x
(2)
n+1 : : : x
(n)
n+1 1
������������
: (79)
Simple manipulations show that it can be transformed in two di�erent ways
Vn =
(�1)n
2nn!
detAn = � 1
n!
detBn; (80)
where the (n+ 2)� (n+ 2) matrices An and Bn have the following forms:
An =
0
BBBBBBBB@
1 0 : : : 0 0
(~x1)
2 �2x(1)1 : : : �2x(n)1 1
(~x2)
2 �2x(1)2 : : : �2x(n)2 1
...
...
...
...
...
(~xn)
2 �2x(1)n : : : �2x(n)n 1
(~xn+1)
2 �2x(1)n+1 : : : �2x(n)n+1 1
1
CCCCCCCCA
; (81)
Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1 21
E. Bogomolny, O. Bohigas, and C. Schmit
and
Bn =
0
BBBBBBBB@
0 0 : : : 0 1
1 x
(1)
1 : : : x
(n)
1 (~x1)
2
1 x
(1)
2 : : : x
(n)
2 (~x2)
2
...
...
...
...
...
1 x
(1)
n : : : x
(n)
n (~xn)
2
1 x
(1)
n+1 : : : x
(n)
n+1 (~xn+1)
2
1
CCCCCCCCA
: (82)
Notice the position of the column of 1 in Bn. Therefore
V 2
n =
(�1)n+1
2n(n!)2
detCn; (83)
where Cn = An �BT
n .
Direct calculations give the Cayler�Menger formula
V 2
n =
(�1)n+1
2n(n!)2
0
BBBBBBB@
0 1 1 : : : 1
1 0 D2
12 : : : D2
1 n+1
1 D2
12 0 : : : D2
2 n+1
...
...
...
...
...
1 D2
1 n : : : 0 D2
n n+1
1 D2
1 n+1 : : : D2
n n+1 0
1
CCCCCCCA
; (84)
where Dij = jj~xi�~xjjj is the length of the edge (i; j) of the n-dimensional simplex.
References
[1] M.L. Mehta, Random Matrices (3rd Ed.) Acad. Press, New York, 2004.
[2] A.M. Vershik, Distance Matrices, Random Metrics and Urysohn Space. 2002,
math/0203008. (Random Mertic Spaces and Universality. � Russian Math. Sur-
veys 59 (2004), 259�295.)
[3] E. Bogomolny, O. Bohigas, and C. Schmit, Spectral Properties of Distance Matrices.
� J. Phys. A: Math. Gen. 36 (2003), 3595�3616.
[4] I.J. Schoenberg, Remarks to Maurice Fr�echet article `Sur la d�e�nition axiomatique
d'une classe d'espace distanci�es vectoriellement applicable sur l'espace de Hilbert'.
� Ann. Math. 36 (1935), 724�732.
[5] I.J. Schoenberg, On Certain Metric Spaces Arising from Euclidean Spaces by a
Change of Metric and their Imbedding in Hilbert Space. � Ann. Math. 38 (1937),
787�793.
[6] J.H. Wells and L.R. Williams, Embeddings and Extensions in Analysis. Springer�
Verlag, Berlin, Heidelberg, New York, 1975.
22 Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1
Distance Matrices and Isometric Embeddings
[7] L.M. Blumenthal, Theory and Applications of Distance Geometry. Chelsea House
Pub. (2nd Ed.), New York, 1970.
[8] M. Deza and M. Laurent, Geometry of Cuts and Metrics. Springer�Verlag, Heidel-
berg, 1997.
[9] F.R. Gantmacher, Th�eorie des Matrices. Vol. 1 and 2. Dunod, Paris, 1966.
[10] I.J. Schoenberg, Positive De�nite Functions on Spheres. � Duke Math. J. 9 (1942),
96�108.
[11] Higher transcendental functions. Vol. 2. (A. Erd�elyi, Ed.). McGraw-Hill, New York,
Toronto, London, 1953.
[12] D.M.Y. Sommerville, An Introduction to the Geometry of N Dimensions. Dover,
New York, 1958.
[13] C.W. Borchardt, �Uber die Aufgabe des Maximum, welche der Bestimmung des
Tetraeders von gr�o�stemVolumen bei gegebenem Fl�acheninhalt der Seiten��achen f�ur
mehr als drei Dimensionen entspricht. Mathematische Abhandlungen der Akademie
der Wissenschaften zu Berlin, 1866.
[14] M. M�ezard, G. Parisi, and A. Zee, Spectra of Euclidean Random Matrices. � Nucl.
Phys. B 559 (1999), 689�701.
Journal of Mathematical Physics, Analysis, Geometry, 2008, vol. 4, No. 1 23
|