Finite metric spaces of strictly negative type. (English) Zbl 0894.51003
A metric space \((X,d)\) with \(| X| =n\) and distance matrix \(D\) is said to be of strictly negative type if (*) \({\mathbf x}D{\mathbf x}^T <0\) for all \({\mathbf x}=(x_1,\ldots x_n)\in {\mathbb R}^n\), with \({\mathbf x}\neq {\mathbf 0}\), \(\sum_{i=1}^n x_i=0\). It is called hypermetric if (*) holds for all \({\mathbf x}=(x_1,\ldots x_n)\in {\mathbb Z}^n\), with \({\mathbf x}\neq\mathbf{0}\), \(\sum_{i=1}^n x_i=1\). It is called regular if \(D\) is regular. Two points \(p,q\in X\) are called antipodal if \(d(p,q)\) is the diameter of \((X,d)\) and \(d(p,q)=d(p,r)+d(r,q)\) for all \(r\in X\).
The authors prove several results about finite metric spaces, the most important being: (1) If a finite metric space \((X,d)\) is hypermetric and regular, then \((X,d)\) is of strictly negative type; (2) A finite isometric subspace of an \(l\)-sphere \({\mathbb S}^l\), \((X,d_{{\mathbb S}^l})\), is of strictly negative type if and only if it contains at most one pair of antipodal points.
Together with results of J. J. Schoenberg [Ann. Math., II. Ser. 38, 787-793 (1937; Zbl 0017.36101)] and J. B. Kelly [Lect. Notes Math. 490, 17-31 (1975; Zbl 0325.52021)], (1) implies that finite metric subspaces of \({\mathbb R}^l\) are of strictly negative type. The authors conjecture that the same holds true for finite metric subspaces of cardinality \(\geq 2\) of hyperbolic \(l\)-dimensional space.
The authors prove several results about finite metric spaces, the most important being: (1) If a finite metric space \((X,d)\) is hypermetric and regular, then \((X,d)\) is of strictly negative type; (2) A finite isometric subspace of an \(l\)-sphere \({\mathbb S}^l\), \((X,d_{{\mathbb S}^l})\), is of strictly negative type if and only if it contains at most one pair of antipodal points.
Together with results of J. J. Schoenberg [Ann. Math., II. Ser. 38, 787-793 (1937; Zbl 0017.36101)] and J. B. Kelly [Lect. Notes Math. 490, 17-31 (1975; Zbl 0325.52021)], (1) implies that finite metric subspaces of \({\mathbb R}^l\) are of strictly negative type. The authors conjecture that the same holds true for finite metric subspaces of cardinality \(\geq 2\) of hyperbolic \(l\)-dimensional space.
Reviewer: V.V.Pambuccian (Phoenix)
References:
| [1] | Assouad, P., Sur les inégalités valides dans \(L_1\), European J. Combin., 5, 99-112 (1984) · Zbl 0549.52007 |
| [2] | Blumenthal, L. M., Theory and Applications of Distance Geometry (1970), Chelsea: Chelsea Princeton · Zbl 0208.24801 |
| [3] | Cottle, R. W., Manifestations of the Schur complement, Linear Algebra Appl., 8, 189-211 (1974) · Zbl 0284.15005 |
| [4] | Deza, M.; Grishukhin, V. P.; Laurent, M., The hypermetric cone is polyhedral, Combinatorica, 13, 397-411 (1993) · Zbl 0801.52009 |
| [5] | Deza, M.; Grishukhin, V. P.; Laurent, M., Extreme hypermetrics and \(L\)-polytopes, (Halász, G.; Lovász, L.; Miklós, D.; Szönyi, T., Sets, Graphs and Numbers. Sets, Graphs and Numbers, Colloq. Math. Soc. János Bolyai, 60 (1992), North-Holland: North-Holland New York), 157-209 · Zbl 0784.11027 |
| [6] | Deza, M.; Grishukhin, V. P.; Laurent, M., Hypermetrics in geometry of numbers, (Cook, W.; Lovâsz, L.; Seymour, P., Combinatorial Optimization. Combinatorial Optimization, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 20 (1994), Amer. Math. Soc.: Amer. Math. Soc. Amsterdam), 1-109 · Zbl 1071.52500 |
| [7] | Fáry, I., Sur la courbure totale d’une courbe gauche faisant un nœud, Bull. Soc. Math. France, 77, 128-138 (1949) · Zbl 0037.23604 |
| [8] | Golub, G.; van Loan, C., Matrix Computations (1983), Johns Hopkins U.P.: Johns Hopkins U.P. Providence · Zbl 0559.65011 |
| [9] | Gower, J. C., Properties of Euclidean and non-Euclidean distance matrices, Linear Algebra Appl., 67, 81-97 (1985) · Zbl 0569.15016 |
| [10] | Gower, J. C., Euclidean distance geometry, Math. Sci., 7, 1, 1-14 (1982) · Zbl 0492.51017 |
| [11] | Graham, R. L.; Hoffman, A. J.; Hosoya, H., On the distance matrix of a directed graph, J. Graph Theory, 1, 85-88 (1977) · Zbl 0363.05034 |
| [12] | Graham, R. L.; Winkler, P. M., On isometric embeddings of graphs, Trans. Amer. Math. Soc., 288, 527-536 (1985) · Zbl 0576.05017 |
| [13] | Grove, K.; Markvorsen, S., New extremal problems for the Riemannian recognition program via Alexandrov geometry, J. Amer. Math. Soc., 8, 1-28 (1995) · Zbl 0829.53033 |
| [14] | Hayden, T. L.; Wells, J., Approximation by matrices positive semidefinite on a subspace, Linear Algebra Appl., 109, 115-130 (1988) · Zbl 0667.15020 |
| [15] | Hayden, T. L.; Wells, J.; Liu, W. M.; Tarazaga, P., The cone of distance matrices, Linear Algebra Appl., 144, 153-169 (1991) · Zbl 0718.15011 |
| [16] | Kelly, J. B., Combinatorial inequalities, (Guy, R.; etal., Combinatorial Structures and Their Applications (1970), Gordon and Breach), 201-207 · Zbl 0335.52009 |
| [17] | Kelly, J. B., Hypermetric spaces and metric transforms, (Shisha, O., Inequalities II (1970), Academic Press), 149-159 |
| [18] | Kelly, J. B., Hypermetric spaces, (Kelly, L. M., The Geometry of Metric and Linear Spaces. The Geometry of Metric and Linear Spaces, Lecture Notes in Math., 490 (1975), Springer), 17-31 · Zbl 0325.52021 |
| [19] | Landkof, N. S., Foundations of Modern Potential Theory, (Grundlehren Math. Wiss., 180 (1972), Springer) · Zbl 0253.31001 |
| [20] | Micchelli, C. A., Interpolation of scattered data: Distance matrices and conditionally positive definite functions, Constr. Approx., 2, 11-22 (1986) · Zbl 0625.41005 |
| [21] | Nielsen, F., On the sum of distances between \(n\) points on a sphere, Nordisk Mat. Tidskrift, 13, 45-50 (1965), (in Danish) · Zbl 0132.17403 |
| [22] | Pólya, G.; Szegő, G., Uber den transfiniten Durchmesser (Kapazitätskonstante) von ebenen und räumlichen Punktmengen, J. Reine Angew, Math., 165, 4-39 (1931) · JFM 57.0094.03 |
| [23] | Reid, L.; Sun, X., Distance matrices and ridge function interpolation, Canad. J. Math., 45, 1313-1323 (1993) · Zbl 0793.41007 |
| [24] | Schoenberg, I. J., On certain metric spaces arising from Euclidean spaces by a change of metric and their embedding in Hilbert space, Ann. of Math., 38, 787-793 (1937) · Zbl 0017.36101 |
| [25] | Winkler, P., On graphs which are metric spaces of negative type, (Alavi, Y.; etal., Graph theory and Its Applications to Algorithms and Computer Science (1985), Wiley), 801-810 · Zbl 0576.05049 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
