Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
20
Chapter
3.
Preliminaries
x E
zn);
then,
we
write: A
~
o.
Equivalently, A
is
positive semidefinite if
and
only if all its eigenvalues are nonnegative, or if
det(AI)
2:
0 for every
principal
submatrix
AI
of A (setting A
I
:=
(aij)i,jEI for a subset
1<::;;
{l,
...
,n}
and
letting
det(AI)
denote
the
determinant
of
AI).
A
symmetric
n x n
matrix
A = (aij)
can
be
encoded by its
upper
triangular
part
(including
the
diagonal), i.e., by
the
vector (aijh::;i::;j::;n. We let
PSD
n
denote
the
set
of vectors (aij h::;i::;j::;n for which
the
symmetric
n x n
matrix
(aij)
(setting
aji = aij) is positive semidefinite.
The
set
PSD
n
is a cone
in
~En,
called
the
positive semidefinite cone.
A quadratic
form
is a function of
the
form:
x E
~n
,....
x
T
Ax
=
2:
aijXiXj
I::;i,j::;n
w here A = (aij) is
an
n x n
symmetric
matrix; it is said to
be
positive semidefinite
when
the
matrix
A is positive semidefinite.
The
Gram
matrix
Gram(
VI,
...
, v
n
) of a set of vectors VI,
...
,V
n
E
~k
(k
2:
1)
is
the
n x n
matrix
whose (i,
j)-
th
entry
is
vT
Vj.
It
is
easy
to
check
that
the
rank
of
the
matrix
Gram(vI,
...
, v
n
)
is
equal to
the
rank
ofthe
system
(Vb
...
, v
n
).
Every
Gram
matrix
is
obviously positive semidefinite.
It
is
well-known
that,
conversely,
every positive semidefinite
matrix
can
be
expressed as a
Gram
matrix.
We recall
this
result
below, as it will be often used
in
our
treatment.
Lemma
2.4.2.
Let
A = (aijh::;i,j::;n
be
a
symmetric
matrix
which is positive
semidefinite
and let k
S;
n
be
its rank. Then, A is a Gram matrix, i.e., there
exist vectors VI,
...
,V
n
E
~k
such that aij =
vT
Vj
for 1
S;
i, j
S;
n.
The
system
(VI,
...
, v
n
) has rank k . Moreover,
if
v~,
...
,v~
are other vectors
of
~k
such that
aij
= vi
T
vj
for 1
S;
i, j
S;
n,
then vi = U
Vi
(1
S;
i
S;
n)
for
some
orthogonal
matrix
U.
Proof.
By
assumption,
A has k nonzero eigenvalues which are positive. Hence,
there
exists
an
n x n
matrix
Qo such
that
A = QoDQ'6, where D
is
an
n x n
matrix
whose entries are all zero except k diagonal entries, say
with
indices
(1,1),
...
, (k, k), equal
to
1.
Denote by Q
the
n x k
submatrix
of Qo consisting
of
its
first k columns.
Then,
A =
QQT
holds, i.e., aij =
vT
Vj
for 1
S;
i, j
S;
n,
where
vf,
...
,V;
denote
the
rows of Q.
It
is
easy to see
that
(VI, .
..
,v
n
)
has
the
same
rank
k as
A.
The
unicity (up
to
orthogonal
transformation)
of VI,
...
,V
n
follows from
Lemma
2.4.1. I
Checking
whether
a given
symmetric
matrix
A is positive semidefinite can
be
done in
polynomial
time.
The
next result
is
given in (Grotschel, Lovasz
and
Schrijver [1988], page 295). For completeness,
we
recall
the
proof
here.
Proposition
2.4.3.
Let A = (aij)
be
a
symmetric
n x n
matrix
with ratio-
nal
entries. There exists an algorithm permitting to check whether A is positive
semidefinite and,
if
not, to construct a vector x E
IQ"
such that x
T
Ax
<
o.
This
2.4 Matrices
21
algorithm runs
in
time
polynomial in n and
in
the size
of
A.
Proof.
The
algorithm
is
based
on
Gaussian elimination
and
proceeds in
the
following way. Check first
whether
all
2:
o.
If
not,
then
A is not positive
semidefinite
and
x
T
Ax
=
all
< 0 for x
:=
(1,0,
...
,of.
Suppose
that
all
=
O.
Then,
A is
not
positive semidefinite if ali
=I-
0 for some i E {2,
...
,n}.
Indeed,
x
T
Ax
< 0
if
we
set
Xi
:=
-1,
Xj
:=
0 for j
=I-
1, i
and
if
we
choose
Xl
E Q such
that
2xlali
- aii >
O.
If
all
= al2 =
...
=
al
n
= 0
then
A
~
0
if
and
only
if
its
(n - 1) x
(n
-
1)
submatrix
A'
:=
(aij)f,j=2 is positive semidefinite. Moreover,
if
we
can
find Y E
Q"-l
such
that
yT
A'y
<
0,
then
x
T
Ax
< 0 for
the
vector
x:=
(O,y) E Qn.
Suppose now
that
all
>
O.
Consider
the
(n-l)
x
(n-l)
matrix
A'
= (a:j)f,j=2
(obtained
by pivoting A
with
respect to
the
entry
all)
defined by
I ail
aij
:=
aij -
-alj
for
i,j
=
2,
...
,n.
all
Then,
A
~
0
if
and
only
if
A'
~
O.
Moreover, suppose
that
we
can
find a vector
y E
Qn-l
such
that
yT
A'y
<
O.
We indicate how
to
construct a vector x E Q"
such
that
x
T
Ax
<
O.
We set x
:=
(0:,
y) where
0:
has to be
determined.
Write
(
a
bT)
A
:=
~l
B .
Then,
x
T
Ax
=
0:2all
+
20:y
T
b
+ yT
By,
where
T
n n I ail T
lIT
2
Y
By
=
2:
YiYjaij =
2:
YiYj(aij +
-alj)
=
yAy
+
-(y
b)
.
i,j=2
i,j=2
all
all
Therefore, x
T
Ax
=
0:
2
all
+20:y
T
b+yT
A'y+--.L(y
T
b)2.
Let D denote
the
discrim-
a11
inant
of
this
quadratic
expression (in
the
variable
0:);
then, D =
-allyT
A'y
>
O.
Hence,
if
we
choose
0:
E Q such
that
-y
T
b-"fi5
<
0:
<
-y
T
b+"fi5,
then
x
:=
au
all
(0:,
y) E Q" satisfies x
T
Ax
<
O.
In all cases
we
have reduced
our
task
to a problem
of
order n - 1. Moreover,
one can verify
that
the
entries of
the
smaller matrices to be considered do
not
grow
too
large, i.e.,
that
their
sizes
remain
polynomially
bounded
by
the
size
of
the
initial
matrix
A (see Grotschel, Lovasz
and
Schrijver
[1988]
for details). I
Let M
be
a
symmetric
n x n
matrix.
The
inertia
In(M)
of
M is defined
as
the
triple
(p,
q,
s),
where p (resp. q,
s)
denotes
the
number
of
positive (resp.
negative, zero) eigenvalues of
M;
hence, n = p + q + s.
If
P is a nonsingular
matrix,
then
it
is well-known
that
the
two matrices M
and
PM
pT
have
the
same
inertia;
this
result
is known as Sylvester's law
of
inertia.
The
following
result
is useful for
computing
the
inertia
of a
matrix.
Lemma
2.4.4.
Let
M
be
a
symmetric
matrix
with the following block decompo-
sition:
22
Chapter
3. Preliminaries
where 0
is
nonsingular. Then,
In(M)
= In(O) +
In(A
BO-
1
B
T
),
det
A1
=
det
0 .
det(A
-
BO-
l
B
T
).
(The
matrix
A - is known as
the
Schur complement
of
0 in
1'.1.)
Proof.
The
following identity holds:
(
A-
BO-IBT
0)
By
Sylvester's law of inertia,
the
two matrices
]1,1
and
OT
0 have
the
same inertia. Therefore, In(Af) In(
0)
+
In(A
-
BO-l
BT).
I
We conclude with a
lemma
that
will
be
needed later.
Lemma
2.4.5.
Let
}.1
be
a symmetric n x n matrix and let U
be
a subspace
of
lIn such that x
T
M x
s:
° holds for all x E U.
If
U has dimension n - 1, then M
has at most one positive eigenvalue.
Proof.
Suppose, for contradiction,
that
M
has
two positive eigenvalues Al
and
A2'
Let
Ul
and
U2
be
eigenvectors for
Al
and
A2,
respectively, with
ul
U2
= 0
and
II
Ul
112=11
U2
112=
1. Let V denote
the
subspace
of
lin
spanned
by
Ul
and
U2.
Then,
xTMx
> 0 holds for all x E
V,
x #
OJ
indeed, if x
alUl
+
a2U2,
then
]\1x =
a1A1
+a~A2
> 0
if(a1,a2)
# (0,0). As U
and
V have respective
dimensions
n - 1
and
2,
there exists x E U n V
with
x # 0.
Then,
x
T
M x
s:
°
since x E U
and
x
T
At x > 0 since x E
V,
yielding a contradiction. I
Part
I
Measure
Aspects:
£l-Embeddability
and
Probability
Introduction
A classical problem in analysis
is
the
isometric
embedding
problem, which con-
sists
of
asking
whether
a given distance space (X,
d)
can
be
isometrically em-
bedded
into some prescribed
important
"host" space.
The
case which
has
been
most
extensively
studied
in
the
literature
is when
the
host space
is
the
Hilbert
space. Work
in
this
area
was
initiated
by some results of Cayley
[1841]
and
later
continued, in
particular,
by Menger [1928, 1931, 1954]' Schoenberg [1935,
1937, 1938a, 1938b]
and
Blumenthal
[1953].
One
of Schoenberg's well-known
results asserts
that
a
distance
space (X,
d)
is isometrically L2-embeddable if
and
only if
the
squared
distance
d
2
satisfies a list of linear inequalities
(the
so-called
negative
type
inequalities).
These
results were
later
extended
in
the
context
of
Lp-spaces.
Of
particular
importance
for
our
purpose
is a result by Bretagnolle,
Dacunha
Castelle
and
Krivine [1966], which
states
that
(X,
d)
is isometrically
Lp-embeddable if
and
only if
the
same
holds for every finite subspace of (X,
d).
Our
objective here is
to
study
the
isometric
embedding
problem
in
the
case
when
the
host space is
the
Banach
L
1
-space.
Our
approach
is
mainly
combi-
natorial.
The
case p = 1
turns
out
to
be
specific
among
the
various Lp-spaces.
Indeed, by
the
above mentioned finiteness result,
we
may
restrict ourselves
to
finite
distance
spaces. Now, one
of
the
basic facts
about
L1
is
that
a finite
distance
space (X,
d)
is
isometrically L
1
-embeddable if
and
only if d belongs
to
the
so-called
cut
cone,
the
cone generated by all
cut
semimetrics.
This
cone is
finitely generated. Therefore, L
1
-embeddability of (X,
d)
can
be
characterized
by a finite list of linear inequalities.
However,
in
contrast
with
the
L
2
-case,
not
all inequalities
of
this
list are
known,
in
general.
In
fact, in view
of
the
complexity
status
of
the
related
max-
cut
problem, it is
quite
unlikely
that
this
list
can
be
completely described.
It
is
one
of
the
objective
of
this
book to survey
what
is known
about
this
list.
Therefore,
the
problem
of
characterizing L
1
-embeddability reduces
to
the
purely
combinatorial
problem
of
describing
the
linear
structure
of
the
cut
cone.
Interest
in
this
cone
is
also
motivated
by its relevance
to
several
hard
combina-
torial
optimization
problems.
Part
I is organized as follows.
Chapter
3 contains some preliminaries
about
distance
spaces. We present
the
basic connection existing between
the
cut
cone
and
L
1
-metrics
in
Chapter
4
and,
in
an
equivalent form in
the
context
of
covariances, in
Chapter
5.
Two of
the
main
known necessary conditions for
L
1
-embeddability, namely,
the
hypermetric
and
negative
type
conditions, are
26
Introduction
presented
in
Chapter
6.
Several characterizations for L
2
-metrics are discussed
there,
including Schoenberg's
result
in
terms
of
the
negative
type
condition
and
Menger's
compactness
result.
Chapters
7
and
9 describe several
operations
on
L
1
-metrics.
In
Chapter
8
we
investigate
the
metric spaces arising from
normed
vector spaces,
poset
lattices,
and
semigroups; in all cases, a
characterization
of
L
1
-embeddability
is given
in
terms
of
the
hypermetric
and
negative
type
con-
ditions. Lipschitz embeddings
with
some
distortion
are
treated
in
Chapter
10,
together
with
an
application
to
the
approximation
of
multicommodity
flows
in
graphs. Finally,
we
group
in
Chapter
11
several
additional
results
related
to
£1-
embeddings
in
a space
of
fixed dimension
and
to
the
minimum
£p-dimension
and,
in
Chapter
12,
we
attempt
to illustrate
the
wide range of use
of
the
L
1
-metric.
M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,
DOI 10.1007/978-3-642-04295-9_3, © Springer-Verlag Berlin Heidelberg 2010
Chapter
3.
Preliminaries
on
Distances
We
introduce
here
all
the
notions
and
definitions
that
we
need
in
Part
I,
in
particular,
about
distance
spaces,
isometric
embeddings,
measure
spaces,
and
our
main
host
spaces:
the
Banach
fp-
and
Lp-spaces for 1
:S:
p
:S:
00.
The
book
will
deal,
in
fact, essentially
with
the
case p = 1, also
with
the
Euclidean
case
p = 2
and
the
semimetric
case p =
00.
We will consider
the
general case p
2:
1
only
episodically. However,
we
now
introduce
the
definitions for p
arbitrary,
as
this
permits
us
to
have a unified
setting
for
the
various
parameters
and,
moreover,
to
emphasize
the
specificity
of
the
case p =
1.
3.1
Distance
Spaces
and
t'p-Spaces
Distances
and
Semimetrics:
Definitions
and
Examples.
Let
X
be
a set.
A
function
d : X x X --+ Il4 is called a distance
on
X
if
d is symmetric, i.e.,
satisfies
d(i,j)
=
d(j,i)
for all
i,j
E
X,
and
if
d(i,i)
= 0 holds for all i E
X.
Then,
(X,
d)
is called a distance space.
If
d satisfies,
in
addition,
the
following
inequalities:
(3.1.1 )
d(i,j)
:S:
d(i,
k)
+ d(j,
k)
for
all
i,j,
k E
X,
then
d is called a semimetric
on
X.
Moreover,
if
d(i,j)
= 0
holds
only
for i =
j,
then
d is called a metric
on
X.
The
inequality
(3.1.1) is
called
a triangle inequality.
Set
V
n
:=
{l,
...
,n}
and
E
n
:=
{ij
I
i,j
E Vn,i
=1=
j}, where
the
symbol
ij
denotes
the
unordered
pair
of
the
integers
i,j,
i.e.,
ij
and
ji
are
considered
identical.
Let
d
be
a
distance
on
the
set V
n
.
Because
of
symmetry
and
since
d(i,
i)
= 0 for i E V
n
, we
can
view
the
distance
d as a
vector
(dijh-::;i<j-::;n
E lffi.En.
Conversely, every
vector
d E
lffi.En
yields a
distance
d
on
Vn
by
symmetry
and
by
taking
distance
0
on
the
diagonal
pairs. Hence, a
distance
on
Vn
can
be
viewed
alternatively
as
a
(symmetric
with
zero
on
the
diagonal)
function
on
Vn
x
Vn
or
as
a
vector
in
lffi.En. We will use freely
these
two
representations
for a
distance
on
V
n
;
the
distinction
should
be
clear from
the
context. Moreover,
we
will use
both
symbols
d(i,j)
and
d
ij
for
denoting
the
distance
between
two
points
i
and
j.
Let
d
be
a
distance
on
the
set V
n
.
Its
distance matrix is defined as
the
n x n
symmetric
matrix
D whose (i,
j)-th
entry
is
d(
i,
j)
for all
i,
j E V
n
.
Hence, all
28
Chapter
3.
Preliminaries
diagonal entries
of
D are equal
to
zero.
The
triangle inequalities (3.1.1) (for
i,j,k
E V
n
)
define a cone in the space
R
E
,.,
called
the
semimetric cone
and
denoted by METn; its elements are precisely
the
semimetrics
on
V
n
.
Very simple examples of semimetrics
can
be constructed
in
the
following
way.
Given
an
integer t 2 1, let
tin
denote
1
the
equidistant metric
on
V
n
,
that
takes
value
t
on
every
pair
in
En;
t1n is obviously a metric
on
V
n
.
Given a subset 8
~
V
n
, let 6(8) denote
the
distance on
Vn
that
takes value
1
on
the
pairs
(i,j)
with i E
8,
j E
Vn
\
8,
and
value 0 on
the
remaining pairs.
Clearly, 6(8) is a semimetric (not a metric if
n
3);
it is called a cut semimetric
2
•
Given a normed
3
space (E,
II
.
II),
a metric
dll.11
can
be defined
on
E by
setting
x Y
II
for all
x,
y E E;
the
metric
dll.1!
is called a norm metric or Minkowski metric.
For any p 2 1,
the
vector space
JlRm
can
be
endowed with
the
fp-norm
II
.
lip
defined by
II
x
IIp=
( L
IXkIP)~
lsksm
for x E
JlR
m
.
Then,
the
associated
norm
metric is denoted by
dip
and
is called
the
fp-metric.
Thus,
dip
(x,y)
=11
x - y
lip
for
x,
y E
JlR
m
•
The
metric space
(JIR'"',
dip)
is abbreviated as
f;;'.
Similarly,.e~
denotes the metric space
(JlRm,
die.,)' where
de
oo
denotes
the
norm
metric associated
with
the
norm
II
. which is defined
by
for
x E
Rm.
For 1
S;
p <
00,
the
metric space
fC:
consists
of
the
set
of infinite sequences
x
(xik:::o
E RN for which the
sum
2:i>O
IXilP
is finite, endowed
with
the
1 -
distance
d(
x, y)
(2:i2:
0
IXi
-
Yi
IP
) p.
In
the same way
.e~
is the set
of
bounded
infinite sequences x E
RN,
endowed with the distance
d(x,
y)
= max(lxi -
Yil
: i 2 0).
Another classical distance
on
the
set R
m
is
the Hamming distance
dH
defined
by
dH(x,y):=
I{i
E [I,m]:
Xi
=1=
Yi}1
in
notation
tJl",
the
letter
n refers
to
the
number
of
points
on
which
the
metric
is
defined
and
not
to
the
dimensionality of
the
space containing
tJl".
2The
cut
semimetrics are also called in
the
literature
split metrics, or dissimilarities,
or
binary
metrics
(e.g., in
Bandelt
and
Dress [1992],
Fichet
[1987a], Le Calve [1987]).
3We
remind
that
a
norm
on a vector space E is a function x E E
......
11
x
liE
~
such
that
II
x
11==
0 if
and
only if x
0,
II
Ax
11=
IAIII
x
II
for A E
lR,
x E
E,
and
Ii
x + y
IiSII
x
Ii
+
II
y
II
for
x,y
E
E.
3.1
Distance Spaces
and
fp-Spaces
29
for all
x,
y E
ll~m.
Hence, when computed on binary vectors
x,
y E
{O,
1}m,
the
Hamming
distance dH(X, y)
and
the
iI-distance
del
(x, y) coincide.
Other
examples of metric spaces are the graphic metric spaces,
that
arise
from connected graphs. Let
G = (V,
E)
be a connected graph
and
let
do
(or
d(G))
denote
the
path
metric
of G where, for two nodes
i,j
E
V,
do(i,j)
denotes
the
shortest length of a
path
from i to j in
G.
Then,
(V,
do)
is
called the graphic
metric
space associated with G.
The
graphic metric space associated with a
hypercube
graph
H(m,2)
is
called a hypercube
metric
space. Observe
that
the
graphic metric space
of
H (m,
2)
coincides with the distance space
({
0,
1}m
, dl
l
)'
If
G = (V,
E)
is a graph and W
(We)eEE
are nonnegative weights assigned
to
its edges, one
can
define similarly
the
path
metric
4
do,w of the weighted graph
(G,
w).
Namely, for two nodes
i,j
E
V,
do,w(i,j)
denotes the smallest value of
LeEPwe
where P is a
path
from
ito
j in
G.
Isometric
Embeddings.
Let
(X,
d)
and
(X',
d') be two distance spaces.
Then,
(X,
d) is said
to
be isometrically embeddable into
(X',
d') if there exists a mapping
¢ (the isometric embedding) from X to
X,
such
that
d(x,
y)
d'(¢(x), ¢(y))
for all
x,
y
EX.
One also says
that
(X,
d) is
an
isometric subspace of
(X',
d
'
).
All
the
embed dings considered here are isometric, so
we
will often omit to mention
the
word "isometric".
For two graphs
G
and
H,
one writes G
'-t
H
and
says
that
G is
an
isometric
subgraph
of
H when
(V(G),dG)
is
an
isometric
sub..'lpace
of
(V(H),d
H
).
Clearly, if
(X,d)
is embeddable into
(X',d')
then
the
same holds for ev-
ery subspace
(Y, d), where Y
~
X.
It
may
sometimes be sufficient
to
check
all subspaces
(Y, d)
of
(X,
d)
on a limited number of points in order to ensure
embeddability of the whole space
(X,
d)
into
(X',
d').
The
smallest number
of
points
that
are enough
to
check is called (following Blumenthal
[1953])
the
or-
der of congruence of
(X',
d'). More precisely,
(X',
d
'
) is said to have order
of
congruence p
if,
for every distance space
(X,
d),
(Y,d)
embeds into
(X',d
'
)
for every Y
~
X with
IVI
~
p
.lJ.
(X,
d)
embeds into
(X',
d
'
)
and
p is
the
smallest such integer (possibly infinite).
A distance space
(X,
d)
is said to be fp-embeddable if
(X,
d)
is isometrically
embeddable into the space
f;'
for some integer m
2:
1.
The
smallest such integer
m is called the
fp-dimension of
(X,
d)
and
is
denoted by
mlp(X,
d).
Then,
we
define
the
minimum
fp-dimension
mlp(n)
by
would
be
more
correct
to
speak
of
'path
semimetric'
rather
than
'path
metric',
as
some
distinct
points
might
be
at
distance
zero
if
some
of
the
edge weights
are
equal
to
zero,
We
will
however
keep
the
terminology
of
'path
metric'
for simplicity.
30
Chapter
3.
Preliminaries
(3.1.2)
max(mt"
(X,
d)
:
IXI
n
and
(X,d)
is ip-embeddable);
that
is,
mt"
(n) is
the
smallest integer m such
that
every ip-embeddable distance
on
n points
can
be embedded in i;'. (It
is
known
that
mi" (n) is finite; in fact,
mt,,(n)
::;
G)
for all
nand
p. Cf. Section 11.2.)
The
distance space
(X,
d) is
said
to
be
ic;
-embeddable
if
it
is
an
isometric subspace of
ic;.
A distance space
(X,
d)
is said to be hypercube embeddable if
it
can
be isomet-
rically embedded in some hypercube metric space
({O,
l}m,diJ
for
some integer
m
:::::
1.
As
the
hypercube metric space
({O,
l}m, d
il
) is
an
isometric subspace of
i,{" every hypercube embeddable distance space is iI-embeddable. (In fact, if d
is rational valued,
then
the
space (X,
d)
is iI-embeddable if
and
only
if
(X,
Ad)
is hypercube embeddable for some integer
Ai
see Proposition 4.3.8.)
Basic
Observations
on
ip-Metrics.
Obviously, if a distance
dis
ip-embeddable
then
d is a semimetric and, moreover,
ad
is ip-embeddable for any a >
O.
On
the other hand, the sum d
l
+
d2
of two ip-embeddable distances d
l
and
d2
in
general, not ip-embeddable.
In
other words, the set of ip-embeddable distances
on
Vn
is not a cone in general. However, the two extreme cases p = 1
and
p =
00
are exceptionaL
In
each of these two cases the set of ip-embeddable distances
on
Vn
forms a cone
that,
in addition, is polyhedral.
The
case p = 1 is directly relevant
to
the central topic of this book. Indeed,
the distances
on
n points
that
are iI-embeddable are precisely
the
distances
that
can be decomposed as a nonnegative linear combination of
cut
semimetrics.
Hence, they form a cone, the
cut
cone
CUT
n
, which is a polyhedral cone as
it
is
generated by
the
2
n
-
1
cut
semimetrics. (Details are given
in
Section 4.1.)
Consider now
the
case p =
00.
Clearly every ioo-embeddable distance
is
a
semimetric. Conversely, every semimetric on
Vn
is
i~-I-embeddable.
Indeed,
the
following n vectors
Vb
.•.
,V
n
E
JRn-1
, where
Vi
(d(l,
i),
d(2, i),
...
,d(n
- 1,
i»
for
i = 1,
...
,
n,
provide
an
isometric embedding of
(V
n
,
d)
into (JRn-l, dt",,). Therefore,
METn
{d E
JRE"
I
dis
ioo-embeddable}.
Hence,
the
ioo-embeddable distances on
Vn
form a cone, the semimetric cone
MET
n'
This
cone is a polyhedral cone as METn is defined by finitely many linear
inequalities (namely, the 3
G)
triangle inequalities). Moreover, the minimum i
oo
-
dimension satisfies:
(3.1.3)
Although
the
ip-embeddable distances on
Vn
do not form a cone if 1 < p <
00,
the
p-th
powers of these distances do form a cone. For 1
::;
p <
00,
set