Multispherical Euclidean distance matrices

In this paper we introduce new necessary and sufficient conditions for an Euclidean distance matrix to be multispherical. The class of multispherical distance matrices studied in this paper contains not only most of the matrices studied by Hayden et al. (1996) 2, but also many other multispherical structures that do not satisfy the conditions in Hayden et al. (1996) 2.We also study the information provided by the origin of coordinates when it is placed at the center of the spheres and the origin representation property is satisfied. These vectors associated with the origin of coordinates generate a number of supporting hyperplanes for a family of multispherical matrices and also describe part of the null space of the corresponding distance matrices.     

On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

Graph rigidity via Euclidean distance matrices

Let G=(V,E,ω) be an incomplete graph with node set V, edge set E, and nonnegative weights ω_ij's on the edges. Let each edge (v_i,v_j) be viewed as a rigid bar, of length ω_ij, which can rotate freely around its end nodes. A realization of a graph G is an assignment of coordinates, in some Euclidean space, to each node of G. In this paper, we consider the problem of determining whether or not a given realization of a graph G is rigid. We show that each realization of G can be epresented as a point in a compact convex set ; and that a generic realization of G is rigid if and only if its corresponding point is a vertex of Ω, i.e., an extreme point with full-dimensional normal cone.     

On the nonnegative rank of Euclidean distance matrices

The Euclidean distance matrix for n distinct points in R^r is generically of rank r + 2. It is shown in this paper via a geometric argument that its nonnegative rank for the case r = 1 is generically n.     

Euclidean distance matrices: new characterization and boundary properties

In this article we give a new characterization of Euclidean distance matrices using known necessary conditions. We also relate this characterization with the faces of the cone and give new properties for the boundary. Finally, a new characterization of spherical/non-spherical matrices is proposed.     

Two theorems on Euclidean distance matrices and Gale transform

We present a characterization of those Euclidean distance matrices (EDMs) D which can be expressed as D=λ(E−C) for some nonnegative scalar λ and some correlation matrix C, where E is the matrix of all ones. This shows that the cones

where is the elliptope (set of correlation matrices) and is the (closed convex) cone of EDMs.

The characterization is given using the Gale transform of the points generating D. We also show that given points , for any scalars λ₁,λ₂,…,λ_n such that

∑_j=1ⁿλ_jp^j=0, ∑_j=1ⁿλ_j=0,

we have

∑_j=1ⁿλ_jpⁱ−p^j2= forall i=1,…,n,

for some scalar independent of i.     

A group majorization ordering for Euclidean distance matrices

This paper investigates some properties of Euclidean distance matrices (EDMs) with focus on their ordering structure. The ordering treated here is the group majorization ordering induced by the group of permutation matrices. By using this notion, we establish two monotonicity results for EDMs: (i) The radius of a spherical Euclidean distance matrix (spherical EDM) is increasing with respect to the group majorization ordering. (ii) The larger an EDM is in terms of the group majorization ordering, the more spread out its eigenvalues are. Minimal elements with respect to this ordering are also described.     

Characterization of multispherical and block structures of Euclidean distance matrices

This paper presents some new characterizations of Euclidean distance matrices (EDMs) of special structures. More specifically, we discuss multispherical and block-structured EDMs, each of which can be viewed as a generalization of spherical EDM. We focus on a well-known inequality that characterizes spherical EDMs and extend it to the sets of multispherical and block-structured EDMs. Some related results are also presented.     

Some necessary and some sufficient trace inequalities for Euclidean distance matrices

In this article, we use known bounds on the smallest eigenvalue of a symmetric matrix and Schoenberg's theorem to provide both necessary as well as sufficient trace inequalities that guarantee a matrix D is a Euclidean distance matrix, EDM . We also provide necessary and sufficient trace inequalities that guarantee a matrix D is an EDM generated by a regular figure.     

Some necessary and some sufficient trace inequalities for Euclidean distance matrices

In this article, we use known bounds on the smallest eigenvalue of a symmetric matrix and Schoenberg's theorem to provide both necessary as well as sufficient trace inequalities that guarantee a matrix D is a Euclidean distance matrix, EDM. We also provide necessary and sufficient trace inequalities that guarantee a matrix D is an EDM generated by a regular figure.     

A remark on the faces of the cone of Euclidean distance matrices

A new characterization of the faces of the cone of Euclidean distance matrices (EDMs) was recently obtained by Tarazaga in terms of LGS(D), a special subspace associated with each EDM D. In this note we show that LGS(D) is nothing but the Gale subspace associated with EDMs.     

The asymptotic distribution of lattice points in Euclidean and non-Euclidean spaces

The asymptotic distribution of orbits for discrete subgroups of motions in Euclidean and non-Euclidean spaces are found; our principal tool is the wave equation. The results are new for the crystallographic groups in Euclidean space and for those groups in non-Euclidean spaces which have fundamental domains of infinite volume. In the latter case we show that the only point spectrum of the Laplace-Beltrami operator lies in the interval ($\text{?(}\text{(m ? 1)}\text{2}\text{)}{}^2\text{,0}$]; furthermore we show that when the subgroup is nonelementary and the fundamental domain has a cusp, then there is at least one eigenvalue in this interval.     

Eigenvalues of Euclidean random matrices

We study the spectral measure of large Euclidean random matrices. The entries of these matrices are determined by the relative position of n random points in a compact set Ω_n of ?^d. Under various assumptions, we establish the almost sure convergence of the limiting spectral measure as the number of points goes to infinity. The moments of the limiting distribution are computed, and we prove that the limit of this limiting distribution as the density of points goes to infinity has a nice expression. We apply our results to the adjacency matrix of the geometric graph. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The Euclidean distance construction of order homomorphisms

The Euclidean distance technique of Arrow and Hahn is used to construct an upper semicontinuous order homomorphism (partial utility function) from (X, ≻) to ($\text{R}$, >), where X is a closed, convex subset of $\text{R}$^N and ≻ is a continuous strict partial order on X. It is also shown that the order homomorphism is upper semicontinuous as a function on $\text{X×}\text{P}\text{(X)}$, where$\text{P}\text{(X)}$ is the set of continuous strict partial orders on X, taken with the topology of closed convergence.     

Submatrices of non-tree-realizable distance matrices

We deal with distance matrices of real (this means, not necessarily integer) numbers. It is known that a distance matrix D of order n is tree-realizable if and only if all its principal submatrices of order 4 are tree-realizable. We discuss bounds for the number, denoted Q_i(D), of non-tree-realizable principal submatrices of order i ? 4 of a non-tree-realizable distance matrix D of order n?i, and we construct some distance matrices which meet extremal conditions on Q_i(D). Our starting point is a proof that a non-tree-realizable distance matrix of order 5 has at least two non-tree-realizable principal submatrices of order 4. Optimal realizations (by graphs with circuits) of distance matrices which are not tree-realizable are not yet as well known as optimal realizations which are trees. Using as starting point the optimal realization of the (arbitrary) distance matrix of order 4, we investigate optimal realizations of non-tree-realizable distance matrices with the minimum number of non-tree-realizable principal submatrices of order 4.     

Eigenstructure of distance matrices with an equal distance subset

We characterize the distance matrices with an equal distance subset in terms of eigenstructure and determine EDMs in this class by examination of a lower dimensional matrix.     

Euclidean distance degree and limit points in a Morsification

Motivated by finding an effective way to compute the algebraic complexity of the nearest point problem for algebraic models, we introduce an efficient method for detecting the limit points of the stratified Morse trajectories in a small perturbation of any polynomial function on a complex affine variety. We compute the multiplicities of these limit points in terms of vanishing cycles. In the case of functions with only isolated stratified singularities, we express the local multiplicities in terms of polar intersection numbers.