Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
6.2
Characterization
of
L2-Embeddability
73
ance
mapping).
This
information
has
already
been
mentioned
in
Figure
5.2.6;
Lemma
6.1.14 below validates it. We first
introduce
a definition.
Definition
6.1.13.
A symmetric function p : X x X
---+
~
is said
to
be
of
positive
type
on X if, for all n
2:
2,
Xl,···,
Xn
EX,
the matrix (p(Xi, Xj)
)r,j=l
is positive semidefinite.
Lemma
6.1.14.
Let X
be
a set and
Xo
EX.
Let d
be
a distance on X and
p
=
~xo
(d)
be
the corresponding symmetric function on X \ {xo}.
(i)
(X,
d)
is
of
negative type
if
and only
if
p is
of
positive type on X \ {xo}.
(ii) (X,
d)
is hypermetric
if
and only
if
p satisfies:
for all
bE
£::n
and all XI,
...
,x
n
EX
\ {xo} (n
2:
2).
Proof.
Let
xI,
...
, xn
EX
\ {xo}, b
o
, b
l
, ... ,
b
n
E
£::,
and
set t
:=
2:£=0
b;.
The
proof
is
based
on
the
following observation:
L
bibjd(xi,xj)
O~i<j~n
= L bobip(Xi,
Xi)
+ L bibj(p(Xi,Xi)
+p(Xj,Xj)
- 2p(Xi,Xj))
l<i<n
19<j~n
=t-t
biP(Xi,Xi)-
L b;bjp(Xi,Xj).
As
an
immediate
application,
we
have:
(6.1.15)
I
In
other
words,
the
negative
type
cone
NEG
n
+1
is in one-to-one linear corre-
spondence
with
the
positive semidefinite cone
PSD
n
.
6.2
Characterization
of
L
2
-Embeddability
In
this
section,
we
study
the
distance
spaces
that
can
be
isometrically
embedded
into
some 1!2-space.
In
other
words,
we
consider
the
distances
that
can
be
realized
as
the
pairwise
Euclidean
distances
of
some configuration
of
points
in
a space
~m
(m
2:.
1).
Such
distance
spaces form,
in
fact,
the
topic
of a long
established
and
active
area
of research, known as distance geometry. Investigations
in
this
area
go back
to
Cayley [1841] who
made
several observations
that
were
later
system-
atized
by
Menger [1928], leading, in
particular,
to
the
theory
of
Cayley-Menger
determinants.
Research in
this
area
was
pursued,
in
particular,
by
Schoenberg
[1935] who discovered a new
characterization
of
1!2-embeddable
distances
in
terms
74
Chapter
6.
Conditions for L1-Embeddability
of
the
negative type inequalities.
The
monograph by Blumenthal
[1953]
remains
a classic reference
on
the
subject. Interest in
the
area of distance geometry was
stimulated in
the
recent years by its many applications, e.g., to
the
theory
of
multidimensional scaling (cf.
the
survey
paper
by de Leeuw
and
Heiser
[1982])
and
to
the
molecular conformation problem
(cf.
the
monograph by Crippen
and
Havel [1988]).
This
section contains several characterizations for flz-embeddable distance
spaces.
First,
we
present Schoenberg's result, which gives a characterization for
fl
2
-embeddability
in
terms
of the negative type inequalities (see Theorem 6.2.2).
As
an
application, checking flz-embeddability for a finite distance space can
be
done in polynomial time; this contrasts with the
1\
-case where the correspond-
ing R1-embeddability problem is known to be NP-complete.
We
then
mention
an
equivalent characterization in terms of Cayley-Menger matrices. Another
fundamental result is a result by Menger, concerning
the
isometric subspaces
of
the
m-dimensional Euclidean space. More precisely, Menger showed
that
a
distance space
(X,
d)
can be isometrically embedded into the m-dimensional Eu-
clidean space
(~m
,
d(2)
if and only if the same property holds for every subspace
of
(X,
d)
on m + 3 points (see Theorem 6.2.13).
Further
characterizations for
Rz-embeddability
can
be found in Theorem 6.2.16.
6.2.1
Schoenberg's
Result
and
Cayley-Menger
Determinants
In
a first step,
we
make
the
link between
the
notions
of
functions
of
positive
type
and
of
JR-covariances.
The
characterization
of
Lz-embeddable spaces in
terms
of
the
negative
type
inequalities given
in
Theorem 6.2.2 below will
then
follow as
an
immediate consequence, using Lemmas 5.3.2 and 6.1.14;
this
result
is
due
to
Schoenberg [1935, 1938b]. Figure 6.2.3 summarizes these connections
z
.
Lemma
6.2.1.
Let p
be
a symmetric function on
X.
Then, p is
of
positive type
on
X
if
and only
if
p is an
~-covariance
on
X.
Proof. Suppose first
that
p is
an
~-covariance
on
X.
Then,
for all
x,y
E
X,
where
fx
are real valued functions of L2(fl,A,,'L). Let
bE
with
finite
support.
Then,
This
shows
that
p is of positive type on
X.
Conversely, suppose
that
p is of
positive
type
on
X.
We
show
that
p
is
an
~-covariance
on
X.
In
view
of
the
2The
equivalence: is
i2-embeddable
~
p:=
~(d)
is a positive semidefinite
matrix
(for
a
distance
d
on
a finite
set)
was,
in
fact, known
to
several
other
authors.
It
is, for
instance,
explidted
in
a
paper
by
Young
and
Householder [1938].
6.2 Characterization
of
L
2
-Embeddability
75
finitude result from Theorem 3.2.1 and Lemma 5.3.2,
we
can suppose
that
X
is
finite. By assumption,
the
matrix
(P(x,
y) )X,l/EX is positive semidefinite. Hence,
by
Lemma
2.4.2,
it
is a
Gram
matrix. This shows
that
p is
an
lR-covariance on
X. I
TheoreIll
6.2.2.
Let
(X,
d)
be
a distance space. Then,
(X,
d)
is
of
negative type
if
and
only
if
(X,
v'd)
is L
2
-embeddable. I
We
remind
that
the cone NOR,.,(2) has been defined in (3.1.4) precisely as the
set
of
distances d on
Vr,
for which
v'd
is
i2-embeddable. Therefore,
NEG
n
NOR,.,(2).
The
distance
matrix
associated with a distance space
(Vr"
d)
where d E NOR,.,(2)
(i.e.,
v'd
is i
2
-embeddable) is also known
in
the
literature as a Euclidean dis-
tance
matrix
(see, e.g., Gower
[1985],
Hayden, Wells, Wei-Min Liu
and
Tarazaga
[1991]). Hence,
the
set of Euclidean distance matrices identifies with the negative
type cone. More information on this cone
and
on
its
projections will be given in
Section 31.4.
d distance on Vn+l
v'd
is i
2
-embeddable
~
i.e., d E NOR,.,(2)
~
dENEG
n
+
1
~
(Pij) is a
Gram
matrix
(setting
Pj;
= Pij)
~
(Pij) E PSD
n
Figure 6.2.3
As
an
immediate application,
the
problem
of
deciding whether a finite dis-
tance space
(X,
d)
is i2-embeddable
can
be solved
in
polynomial time. Indeed,
this
amounts
to checking whether the symmetric
matrix
(Pij) associated with
p:=
e(d
2
)
is positive semidefinite (which can be done in polynomial time; recall
Proposition 2.4.3).
In
contrast, checking whether (X,
d)
is iI-embeddable
is
an
NP-complete problem (recall problem (P5) in Section 4.4).
We
address now the following question: Given an i
2
-embeddable distance
space
(X,
d), what is the minimum dimension m of a Euclidean space
i'2
=
(lR
m
,
d
(2
)
in
which (X,
d)
can
be
embedded?
This
parameter
is the i
2
-dimension
of
(X,
d),
denoted as m£2(X,
d).
It
turns
out
that
this question
can
be very easily
answered, as
me
z
(X,
d)
can be expressed as the
rank
of
a related matrix.
76
Chapter
6. Conditions for L
1
-
Embeddability
We
introduce
some
notation.
Let (X,
d)
be a finite
distance
space with, say,
X =
{I,
...
,n}.
Let
Xo
E X
and
let p =
~xo(d)
denote
the
image
of
d
under
the
covariance
mapping
~xo
(recall
relation
(5.2.5)).
Then,
we
let Pxo(X,
d)
denote
the
(n
- 1) x
(n
- 1)
matrix
whose
(i,j)-th
entry
is
p(i,j)
for
i,j
EX
\
{xo}.
The
next
result
indicates a way to
compute
the
f
2
-dimension. For convenience,
we
formulate
it
for a distance space whose
square
root
is f
2
-embeddable.
Proposition
6.2.4.
Let
(X,
d)
be
a finite distance space
of
negative type,
i.e., such that
(X,Vd)
is f
2
-embeddable. Then, the f
2
-dimension
m£2(X,Vd)
of
(X,Vd)
is given
by
Proof. Apply
Lemma
2.4.2.
I
Corollary
6.2.5.
Let
(X,
d)
be
a finite distance space. Then,
(X,
Vd)
embeds
isometrically
into
f2
if
and only
if
the
matrix
P
xo
(X,
d)
is positive semidefinite
and has rank
::;
r.
Moreover,
if
m£2
(X,
Vd)
=
r,
then there exists a subset
y
<;;;
X such that
WI
= r + 1 and
m£2
(Y,
Vd)
=
r.
(There exists such a
set
Y
containing any given element
Xo
EX.)
I
Therefore,
(6.2.6) m£2(n) = n - 1,
where m£2(n) is
the
minimum
f
2
-dimension, defined as
the
minimum
integer
m
such
that
every f
2
-embeddable
distance
on
n
points
embeds
in
fr.
Some
other
formulations for
the
£2-dimension
of
a distance space
can
be derived using
Lemma
6.2.7
and
relation (6.2.10) below.
Lemma
6.2.7.
Let
(X,
d)
be
a distance space with associated distance
matrix
D and let
Xo
EX.
Then,
1 1
rank
Pxo(X,
d)
=
rank
(1
-
-J)D(1
-
-J).
n n
(Here, J denotes
the
all-ones
matrix
and
1
the
identity
matrix.)
Proof.
One
can
bring
the
matrix
(1
-
~J)D(1
-
~J)
to
Pxo(X,
d)
by
performing
some
row/column
manipulations.
I
Conditions
about
the
matrix
P
xo
(X,
d)
can
be
reformulated
in
terms
of
the
Cayley-Menger
determinants.
These
determinants
are a classical
notion
in
the
theory
of
distance
geometry (see
Blumenthal
[1953]).
They
are defined
in
the
following
manner.
Let (X,
d)
be a finite distance space with, say, X =
{I,
...
,
n}
and
let
D
be
its
associated distance
matrix.
Then,
the
(n +
1)
x (n +
1)
symmetric
matrix:
6.2
Characterization
of
L
2
-Embeddability
77
(6.2.8)
CM(X,d)
:=
(~
~)
(where e
denotes
the
all-ones vector) is called
the
Cayley-Menger matrix
of
the
distance
space
(X,
d)
and
det
CM(X,
d)
is its Cayley-Menger determinant.
The
matrices
CM(X,
d)
and
P
xo
(X,
d)
are, in fact, closely related. To see it, consider
the
2 x 2
submatrix
(~ ~)
of
CM(X,
d), whose first
row/column
is indexed
by
the
element
Xo
of X
and
whose second
row/column
corresponds
to
the
new
(n
+
1)-th
entry
in
CM(X,
d). One can easily verify
that
its Schur
complement
in
the
matrix
CM(X,
d)
coincides
with
the
matrix
-2P
xo
(X,
d). Therefore,
(6.2.9)
det
CM(X,d)
=
(-I)lxI2Ixl-ldetPxo(X,d),
(6.2.10)
rank
CM(X,
d)
=
rank
P
Xo
(X,
d)
+
2.
Positive semidefiniteness for P
xo
(X,
d)
can
also be expressed
in
terms
of
the
Cayley-Menger
determinants.
Indeed, P
Xo
(X,
d)
is positive semidefinite if
and
only if every principal
submatrix
has
a nonnegative
determinant.
But,
a principal
submatrix
of
Pxo(X,
d)
is
of
the
form Pxo(Y,
d)
for some Y
c,;;
X
with
Xo
E
Y.
Hence,
we
have
the
following result, which was formulated
under
this
form
in
Menger [1954].
Proposition
6.2.11.
Let
(X,
d)
be
a finite distance space. Then,
(i)
(X,
v'd)
is f
2
-embeddable
if
and only
if
(-I)I
Y
I
det
CM(Y,
d)
2:
0 for all
Y
c,;;
X (or for all Y
c,;;
X containing a given point
Xo
EX).
(ii) Suppose
IXI
=
r+
1; X = {xo,
Xl,
...
,x
T
}. Then,
(X,
v'd)
is f
2
-embeddable
with
f
2
-dimension r
if
and only
if
(_I)k+l
det
CM(
{Xo,
Xl,
...
,xd,
d)
> 0
for all k =
1,
...
, r.
(iii) Suppose
IXI
= r + 2. Then,
(X,
v'd)
is f
2
-embeddable with
f
2
-dimension
r
if
and only
if
the elements
of
X can
be
ordered
as
Xo,
Xl,
...
,X
n
XT+l
in
such a way that
(_I)k+l
det
CM(
{xo,
Xl,
...
,xd,
d)
> 0 for all k = 1,
...
,r
and
det
CM(X,
d)
=
O.
(iv) Suppose
IXI
= r + 3. Then,
(X,
v'd)
is f
2
-embeddable with
f
2
-dimension r
if
and only
if
the elements
of
X can
be
ordered
as
Xo,
Xl,
...
,XT)
XT+l,
X
T
+2
in such a way that
(-I)k+ldetCM({xO,Xl,
...
,xd,d)
> 0 for all k
1,
...
, r,
det
CM(X
\
{xT+d,
d)
= 0, and det
CM(X
\
{X
T
+2},
d)
=
o.
I
Remark
6.2.12.
Note
that
det
CM(X,
d)
= 2d(xo,
Xl)
2:
0 if
IXI
=
2,
X =
{xo,xd.
Moreover,
if
IXI
= 3, X = {XO,Xl,X2}
and
if
we
set a
:=
d(XO,Xl),
b
:=
d(xo,
X2)
and
c
:=
d(Xl'
X2),
then
one can check
that
Hence,
det
CM(X,
d)
~
0 if
v'd
satisfies
the
triangle inequalities.
That
is, every
semimetric
space
on
3
points
is f
2
-embeddable. Moreover,
if
(X,
d)
is a distance
78
Chapter
6.
Conditions
for
LI-Embeddability
space
on
IXI
= 4 points,
then
(X,
-id)
is £2-embeddable
if
and
only
if
-id
is a
semimetric
and
det
CM(X,
d)
2
o.
I
6.2.2
Menger's
Result
For
an
infinite
distance
space (X,
d),
we
know from
Theorem
3.2.1
that
(X,
d)
is L
2
-embeddable
if
and
only
if
this
property
holds for every finite
subspace
of
(X,
d).
Menger [1928] shows
3
that,
in
order
to
ensure
embeddability
in
the
m-
dimensional
space
£-q',
it
suffices
to
consider
the
subspaces of (X,
d)
on
m + 3
points.
Theorem
6.2.13.
Given
m 2 1, a distance space
(X,
d) can
be
isometrically
embedded
in
£-q'
if
and
only
if,
for
every4 Y
~
X
with
WI
= m + 3, (Y, d) can
be
isometrically
embedded
in
£-q'.
This
result
will follow from
the
following
sharper
statement.
Theorem
6.2.14.
Given
m 2 1, a distance space
(X,
d) can
be
isometrically
embedded
in
£-q'
if
and
only
if
there
exist
an
integer
r
(0
::;
r
::;
m)
and
a
subset
Y
:=
{xo,
Xl,
...
, x
T
}
of
X
such
that
(i)
the
distance space
(Y,
d) can
be
isometrically
embedded
in
£2
but
not
in
£;-1,
(ii)
for
every
x,
y
EX,
the distance space
(Y
U
{x,
y},
d) can
be
isometrically
embedded
in
£2'
Then,
mf
2
(X,d)
=
r.
Before giving
the
proof,
we
introduce
some
notation.
Let
(X,
d)
and
(X',
d
'
)
be
two
distance
spaces
and
let Xl,
...
,Xk
EX,
x~,
...
,x~
E
X'.
We write:
if
the
corresponding
subspaces
are
isometric, i.e.,
if
d(Xi' Xj) = d
'
(x;,
xj)
for all
i,
j =
1,
...
,k.
When
Xl,
...
,Xk
are
vectors
in
Rn
(n
2
1)
then
the
distance
is
imp
licit ely
supposed
to
be
the
Euclidean
distance. In
other
words,
the
notation:
Xl,
...
,
Xk
~
x~,
...
,
X~
means
then
that
II
Xi
- Xj
112=
d'(x;,
xj)
for all
i,j.
Pmof
of
Theorems
6.2.13
and
6.2.14.
Suppose
first
that
every subspace
of
(X,
d)
on
m + 3
points
embeds
in
£-q';
we
show
the
existence of
rand
Xo,
.
..
,X,. E X
3Details
about
this
topic
can
also
be
found
in
Menger
[1931]
and
in
the
monographs
by
Menger
[1954]
and
Blumenthal
[1953].
The
analogue
question
in
the
case
of
the
L1-space
will
be
addressed
in
Section
1l.l.
'In
fact,
the
result
remains
valid
if
we
only
assume
that
(Y, d)
can
be
isometrically
embedded
into
Cr
for
every
Y
c:;;
X
with
IYI
= m + 3
and
containing
a given
element
Xo
E
X.
This
fact
will
be
used
in
Section
6.4 for
the
proof
of
Theorem
6.4.8.
6.2
Characterization
of
L
2
-Embeddability
79
satisfying
the
conditions (i),(ii) from
Theorem
6.2.14. For this, define r as
the
smallest
integer such
that
every subspace of (X,
d)
on
r + 3
points
embeds
in
£2.
Then,
there
exists Y
<::;
X
with
WI
= r + 2
and
such
that
(Y,
d)
does
not
embed
in
£;-1. Hence, m£2(Y'd) = r.
By
Corollary 6.2.5,
we
can
find
points
Xo,
.
..
, X
T
E Y
<::;
X for which
m£2(
{xo,
...
,x
T
},
d)
= r. Hence, these
r+
1
points
satisfy
the
conditions (i),(ii).
Conversely, let us now suppose
that
there
exist
an
integer r
and
some
points
XO,Xl,
...
,X
T
E X satisfying
the
conditions (i),(ii) from
Theorem
6.2.14. We
show
that
(X,
d)
embeds in
£2.
By (i), there exist a set of vectors
x~,
..
. ,
x~
E
lffi.T
(of affine
rank
r + 1) such
that
Given x
EX,
the
distance space
({
xo, .
..
,xr,
x},
d)
embeds
in
£2
by (ii). Hence,
there
exist vectors xo, .
..
,xr,
x E
lffi.T
such
that
As
x~,
..
. ,
x~
~
xo,
...
,
xr,
we
can
find (by
Lemma
2.4.1)
an
orthogonal transfor-
mation
9
of
lffi.T
mapping
every
Xi
onto
x~
(for i = 0,1,
...
, r).
Setting
Xl
:=
g(x),
we
obtain
a vector
Xl
E
lffi.T
such
that
Such
a vector
Xl
is unique (as
x~,
xi,
...
,x~
have full affine
rank
r+
1). Hence,
this
defines a
mapping
x E X
f-t
Xl
E
lffi.T.
We now show
that
d(x, y)
=11
Xl
-
yl
112
for
all
x,
y
EX.
Let
x,
y
EX.
By
(ii),
there
exist vectors
x~, x~,
..
.
,x~,
x",
y" E
lffi.T
such
that
Therefore,
x~,xi,
...
,X~,XI
~
x~,x~,
...
,X~,X"
and
x~,xi,
...
,x~,yl
~
x~,x~,
...
,x~,y".
Using
Lemma
2.4.1,
we
can find
an
orthogonal
transformation
f'
(resp.
f")
of
lffi.T
mapping
x~
to
x;' (for i =
0,
1,
...
, r)
and
Xl
to
x"
(resp.
yl
to
y"). Therefore,
the
two
mappings
f'
and
f"
coincide (as
they
coincide
on
a set of full affine
rank).
This
implies
that
xl,yl
~
x",y".
As
x,y
~
x",y",
we
deduce
that
x,y
~
xl,yl.
This
concludes
the
proof. I
Let us observe
that
Theorem
6.2.13 is
best
possible. Indeed,
there
exist
distance
spaces
that
do not
embed
in
£'2'
while any subspace
on
m+ 2
points
does.
In
other
words,
the
order
of congruence of
the
distance space
£'2'
=
(lffi.
m
,
d£2)
is
equal
to
m + 3.
Such
an
example
can
be
constructed
as follows. Let xo,
Xl,
•..
,
Xm
E
lffi.m
be
the
vertices of
an
equilateral simplex
fl
in
lffi.m
with, say, side
length
a. Denote
by
Xm+l
the
center of
this
simplex
and
let b denote
the
Euclidean
distance from
Xm+l
to
any
vertex
Xi
of
fl.
Finally, let c denote
the
Euclidean
distance
from
80
Chapter
6.
Conditions for L1-Embeddability
Xm+l
to
the
hyperplane supporting any facet of
Ll.
\Ve
now define a distance d
on
the
set X
:=
{O,
1,
...
, m +
1,
m +
2}
by setting
d(i,j)
:=
G,
d(i,m+1)
d(i,m+2)
d(m+1,m+2)
2c.
for
i f. j E
{O,
1,
...
, m},
b
for i = 0,1,
...
,m,
Now,
(X,
d)
is
not
i!;"-embeddable (in fact, not i!2-embeddable).
On
the other
hand,
every subspace
of
(X,
d)
on m + 2 points embeds in
1!;".
(Indeed, this is
obvious for
the
subspaces (X \ {m + 2},
d)
and (X \ {m + I},
d).
This
is also
true
for the subspace (X \ {i},
d)
where i 0,
...
,m.
For this, let
xi
denote
the
symmetric of
Xm+I
around the hyperplane spanned by XQ,
...
,Xi-I,
Xi+I."
.
,X
m
;
then,
O,
...
,i
- 1, i + 1,
...
,
m,m
+
I,m
+
2""
Xo,·
..
,Xi-I,Xi+l>'"
,Xm,Xm+hX';,)
For instance, for dimension m =
1,
the distance
matrix
provides
an
example of a non i!2-embeddable metric for which every 3-point
subspace embeds on the line
£~.
On
the other hand, Menger showed
that,
for a distance space
(X,
d)
on more
than
m + 3 points, checking l';"-embeddability
of
its
subspaces on m + 2 points
suffices
for
ensuring l';"-embeddability of the whole space
(X,
d) (cf. Menger
[1931]
or Blumenthal [1953]).
Theorem
6.2.15.
Let
(X,d)
be
a distance space with
IXI
;:::
m +
4.
Then,
(X,
d)
is isometrically i!;,,-embeddable
if
and only
if
(Y,
d)
is isometrically
£;"-
embeddable for every Y
<;;;
X with
WI
:::;
m +
2.
I
The
proof
of
this result is based on a careful analysis of
the
properties of the
'obstructions'
to
Theorem 6.2.13;
that
is,
of
the distance spaces on m + 3 points
which do
not
embed in
£;"
while all their sllbspaces on m + 2 points do.
6.2.3
Further
Characterizations
We present here several additional equivalent characterizations
for
distance spaces
of negative type.
The
equivalence (i)
¢=}
(ii) in Theorem 6.2.16 below is given
in Gower [1982],
(i)
(iii) in Hayden and Wells
[1988J
and
(i)
===>
(iv) is
mentioned in
Graham
and
Winkler
[1985].
Theorem
6.2.16.
Let
(X,
d)
be
a finite distance space with X =
{I,
...
,n}.
Let
D
be
the associated n x n distance
matrix
and let CM(X,
d)
be
the Cayley-Menger
matrix
defined
by
(6.2.8). Consider the following assertions.
6.2 Characterization of L
2
-Embeddability
81
(i)
(X,
d)
is
of
negative type.
(ii)
The
matrix
(1
-
es
T
)(
-D)(I
seT)
is
positive
semidefinite
for
any s E
~n
with
sT
e 1 (e denoting the all-ones vector).
(iii)
The
matrix
CM(X,
d) has exactly one positive eigenvalue.
(iv)
The
matrix
D has exactly one positive eigenvalue
(if
D is
not
the zero
matrix).
Then,
(i)
~
(ii)
~
(iii)
=}
(iv).
Proof. (i)
~
(ii) Let s E
~n
with 1 and set K
:=
1 -
seT
and
A
:=
KT(
-D)K.
Then,
for x E
~n,
we
have
that
yT(
-D)y,
setting y =
Kx.
One checks easily
that
the
range of K consists of the vectors y E
~n
such
that
Li'=l
Yi
=
O.
Therefore,
we
obtain
that
A is positive semidefinite if
and
only if
yT
( _
D)y
~
0 for all y E
~n
such
that
Li':.d
Yi
0, i.e., if
(X,
d) is of negative
type.
(i)
~
(iii) Let
Xo
EX.
Consider the 2 x 2
submatrix
C
:=
(~ ~)
of
CM(X,
d)
with
row/column indices the two elements
Xo
and
n +
1.
We
use the
fact, already mentioned earlier,
that
the
Schur complement of C
in
CM(X,d)
is equal to
the
matrix
-2P
xo
(X,
d). Hence, applying Lemma 2.4.4
and
the
fact
that
C has one positive eigenvalue,
we
obtain
that
Pxo(X,
d)
~
0 if
and
only if
the
matrix
CM(X,
d) has exactly one positive eigenvalue.
The
result, now follows
as
Pxo(X,
d)
~
0 is equivalent to
(X,
d)
being
of
negative type.
(i)
=}
(iv)
The
matrix
D has
at
least one positive eigenvalue since D has all its
diagonal entries equal to
O.
If
(X,
d)
is
of
negative type then, by Lemma 2.4.5, D
has
at
most one positive eigenvalue since x
T
Dx
S;
0 holds for all x in
an
(n
1)-
dimensional subspace
of
~n.
Therefore, D has exactly one positive eigenvalue.
I
Remark
6.2.17.
Let (X,
d)
be
a distance space
with
X
{I,
...
,n}
and
let
s E
~n
with
sT
e 1. Set
d(i,.)
:=
LjEX
sjd(i,j)
for i E X
and
d(., .)
Li,jEX
sisjd(i,j).
Then
the
matrix
A
:=
(1 -
es
T
)(
-D)(I
-
seT)
considered in
Theorem
6.2.16 (ii) has its entries of
the
form:
aij
d(i,.)
+
d(j,.)
d(.,.)
-
d(i,j)
for
i,j
EX.
In
the
case when s this
matrix
A was already considered by Torgerson
[1952] who showed
that
(X,.Jd)
is
f
2
-embeddable if and only if A is positive
semidefinite.
Observe
that,
when (X,
d)
is
of negative type, one
can
choose the vectors
Ul,
...
,
Un
providing
an
f
2
-embedding of
(X,.Jd)
in such a way
that
LiEX
BiUi
0
and, then,
the
matrix
!A
coincides with
the
Gram
matrix
of
Ul,
.•.
,Un
(which
shows again
the
equivalence of (i)
and
(ii) in Theorem 6.2.16).
In
particular, if
Xo
is a given element of X
and
s is the corresponding coordinate vector,
then
~
A coincides with
the
matrix
P
xo
(X,
d)
augmented by a zero row
and
column
in
82
Chapter
6.
Conditions
for
L1-Embeddability
position
Xo.
I
The
next
result
considers
the
case
when
the
distance
matrix
D
has
a
constant
row
sum
(necessarily
equal
to
e~,~e);
that
is,
when
the
all-ones vector e is
an
eigenvector
of
D.
It
can
be
found
in
Hayden
and
Tarazaga
[1993]; see also
Alexander
[1977].
Theorem
6.2.18.
Let
(X,
d)
be
a distance space with X = {1,
...
,n}
and
with
nonzero distance
matrix
D.
The following assertions are equivalent.
(i)
(X,
d)
is
of
negative type and D has a constant row
sum.
(ii) D has exactly one positive eigenvalue and D has a constant row
sum.
(iii) There exist vectors
Ul,
...
,Un
providing an C
2
-embedding
of
(X,
Vd)
that
lie
on
a sphere whose center coincides with the barycentrum
of
the
Ui'S.
Moreover,
under
these conditions, me2(X,
Vd)
=
rank
D - 1
and
the radius r
of
the sphere containing the vectors Ui providing an C
2
-embedding
of
(X,
Vd)
is
given by:
r2
=
2~
LjEX
d
ij
.
Proof.
The
implication
(i)
===}
(ii) is
contained
in
Theorem
6.2.16.
(ii)
===}
(iii)
By
assumption,
De
=
Ae
where A
:=
~eT
De
and
the
matrix
~eeT
-D
is
positive
semidefinite. Hence,
there
exist vectors
Ul,
..•
,Un
such
that
~
-
dij
=
vTvj
for all
i,j
E
X.
Therefore,
dij
=
(II
Ui -
Uj
Ib?
for
i,j
E
X,
after
setting
Ui
:=
~Vi
(i
E
X).
By
construction,
the
Ui'S
lie
on
the
sphere
centered
at
the
origin
with
squared
radius
2~
and
their
barycentrum
is
the
origin since
""'
2
""'
T
""'
A T
(II
LVi
112)
= L Vi
Vj
= L
(-
-
dij)
=
nA
- e
De
=
O.
iEX
i,jEX i,jEX
n
Moreover,
me2
(X,
Vd)
is
equal
to
the
rank
of
the
system
(Ul'
...
, un), i.e.,
to
the
rank
of
matrix
~eeT
- D which
can
be
easily verified
to
be
equal
to
rank
D -
l.
(iii)
===}
(i)
Assume
that
Ul,
...
,Un
provide
an
C
2
-embedding
of
(X,
Vd)
and
that
LiEX
Ui = 0
and
II
Ui
112=
r for all i E
X,
for some r >
o.
Then,
L d
ij
= L
((II
Ui
112)2
+
(II
Uj
112)2
- 2uT
Uj)
=
2m2
JEX JEX
does
not
depend
on
i
EX.
This
also shows
the
desired
value for
the
radius
r. I
6.3
A
Chain
of
Implications
We
summarize
in
this
section
the
implications
existing
between
the
properties
of
being
L
1
-,
L
2
-embeddable,
of
negative
type,
and
hypermetric.
Theorem
6.3.1.
Let
(X,
d)
be
a finite distance space with associated distance
matrix
D.
Consider the following assertions.