Problems of distance geometry and convex properties of quadratic maps

A weighted graph is calledd-realizable if its vertices can be chosen ind-dimensional Euclidean space so that the Euclidean distance between every pair of adjacent vertices is equal to the prescribed weight. We prove that if a weighted graph withk edges isd-realizable for somed, then it isd-realizable for (this bound is sharp in the worst case). We prove that for a graphG withn vertices andk edges and for a dimensiond the image of the so-called rigidity map ℝ ^dn →ℝ ^k is a convex set in ℝ ^k provided . These results are obtained as corollaries of a general convexity theorem for quadratic maps which also extends the Toeplitz-Hausdorff theorem. The main ingredients of the proof are the duality for linear programming in the space of quadratic forms and the “corank formula” for the strata of singular quadratic forms. This research was supported by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C0027.