Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2018 | Book

Mathematical Preliminaries Read chapter Read first chapter

Euclidean Distance Matrices and Their Applications in Rigidity Theory

Author: Abdo Y. Alfakih

Publisher: Springer International Publishing

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book offers a comprehensive and accessible exposition of Euclidean Distance Matrices (EDMs) and rigidity theory of bar-and-joint frameworks. It is based on the one-to-one correspondence between EDMs and projected Gram matrices. Accordingly the machinery of semidefinite programming is a common thread that runs throughout the book. As a result, two parallel approaches to rigidity theory are presented. The first is traditional and more intuitive approach that is based on a vector representation of point configuration. The second is based on a Gram matrix representation of point configuration.
Euclidean Distance Matrices and Their Applications in Rigidity Theory begins by establishing the necessary background needed for the rest of the book. The focus of Chapter 1 is on pertinent results from matrix theory, graph theory and convexity theory, while Chapter 2 is devoted to positive semidefinite (PSD) matrices due to the key role these matrices play in our approach. Chapters 3 to 7 provide detailed studies of EDMs, and in particular their various characterizations, classes, eigenvalues and geometry. Chapter 8 serves as a transitional chapter between EDMs and rigidity theory. Chapters 9 and 10 cover local and universal rigidities of bar-and-joint frameworks. This book is self-contained and should be accessible to a wide audience including students and researchers in statistics, operations research, computational biochemistry, engineering, computer science and mathematics.

Table of Contents

Frontmatter
Chapter 1. Mathematical Preliminaries
Abstract
In this chapter, we briefly review some of the mathematical preliminaries that will be needed throughout the monograph. These include a brief review of the most pertinent concepts and results in the theories of vector spaces, matrices, convexity, and graphs. Proofs of several of these results are included to make this chapter as self-contained as possible.
Abdo Y. Alfakih
Chapter 2. Positive Semidefinite Matrices
Abstract
Positive semidefinite (PSD) and positive definite (PD) matrices are closely connected with Euclidean distance matrices. Accordingly, they play a central role in this monograph. This chapter reviews some of the basic results concerning these matrices. Among the topics discussed are various characterizations of PSD and PD matrices, theorems of the alternative for the semidefinite cone, the facial structures of the semidefinite cone and spectrahedra, as well as the Borwein–Wolkowicz facial reduction scheme.
Abdo Y. Alfakih
Chapter 3. Euclidean Distance Matrices (EDMs)
Abstract
This chapter provides an introduction to Euclidean distance matrices (EDMs). Our primary focus is on various characterizations and basic properties of EDMs. The chapter also discusses methods to construct new EDMs from old ones, and presents some EDM necessary and sufficient inequalities. It also provides a discussion of the Cayley–Menger matrix and Schoenberg Transformations.
Abdo Y. Alfakih
Chapter 4. Classes of EDMs
Abstract
Euclidean Distance Matrices fall into two classes: spherical and nonspherical. The first part of this chapter discusses various characterizations and several subclasses of spherical EDMs. Among the examples of spherical EDMs discussed are: regular EDMs, cell matrices, Manhattan distance matrices, Hamming distance matrices on the hypercube, distance matrices of trees and resistance distance matrices of electrical networks. The second part focuses on nonspherical EDMs and their characterization. As an interesting example of nonspherical EDMs, we discuss multispherical EDMs.
Abdo Y. Alfakih
Chapter 5. The Geometry of EDMs
Abstract
The geometric properties of EDMs are inherited from those of PSD matrices. Let \(\mathcal{D}^{n}\) denote the set of EDMs of order n. This chapter focuses on the geometry of \(\mathcal{D}^{n}\). In particular, we study the facial structure of \(\mathcal{D}^{n}\) and its polar, and we highlight the similarities between \(\mathcal{D}^{n}\) and the positive semidefinite cone \(\mathcal{S}_{+}^{n}\).
Abdo Y. Alfakih
Chapter 6. The Eigenvalues of EDMs
Abstract
The focus of this chapter is on the eigenvalues of EDMs. In the first part, we present a characterization of the column space of an EDM D. This characterization is then used to express the eigenvalues of D in terms of the eigenvalues of its Gram matrix \(B =\mathcal{ T}(D) = -JDJ/2\). In case of regular and nonspherical centrally symmetric EDMs, the same result can also be obtained by using the notion of equitable partition. In the second part, we discuss some other topics related to eigenvalues such as: a method for constructing nonisomorphic cospectral EDMs; the connection between EDMs, graphs, and combinatorial designs; EDMs with exactly two or three distinct eigenvalues and the EDM inverse eigenvalue problem.
Abdo Y. Alfakih
Chapter 7. The Entries of EDMs
Abstract
This chapter focuses on two problems concerning the individual entries of an EDM. The first problem is how to determine a missing or an unknown entry of an EDM. We present two methods for solving this problem, the second of which yields a complete closed-form solution. The second problem is how far an entry of an EDM can deviate from its current value, assuming all other entries are kept unchanged, before the matrix stops being an EDM. We present explicit formulas for the intervals, within which, entries can vary, one at a time, if the matrix is to remain an EDM. Moreover, we present a characterization of those entries whose intervals have zero length; i.e., those entries where any deviation from their current values renders the matrix non-EDM.
Abdo Y. Alfakih
Chapter 8. EDM Completions and Bar Frameworks
Abstract
This chapter has three parts. Part one addresses the problem of EDM completions. Part two is an introduction to the theory of bar-and-joint frameworks. Such frameworks, which are interesting in their own right, are particularly useful in the study of various uniqueness notions of EDM completions. In the third part, we discuss stress matrices, which play a pivotal role in the theory of bar-and-joint frameworks. The chapter concludes with the classic Maxwell–Cremona theorem. We begin first with EDM completions.
Abdo Y. Alfakih
Chapter 9. Local and Infinitesimal Rigidities
Abstract
This chapter focuses on the problems of local rigidity and infinitesimal rigidity of bar frameworks. These problems have a long and rich history going back at least as far as Cauchy [51]. The main tools in tackling these problems are the rigidity matrix R and the dual rigidity matrix \(\bar{R}\). While R is defined in terms of the underlying graph G and configuration p, \(\bar{R}\) is defined in terms of the complement graph \(\bar{G}\) and Gale matrix Z. Nonetheless, both matrices R and \(\bar{R}\) carry the same information. The chapter concludes with a discussion of generic local rigidity in dimension 2, where the local rigidity problem reduces to a purely combinatorial one depending only on graph G. The literature on the theory of local and infinitesimal rigidities is vast [59, 57, 66, 97, 194]. However, in this chapter, we confine ourselves to discussing only the basic results and the results pertaining to EDMs.
Abdo Y. Alfakih
Chapter 10. Universal and Dimensional Rigidities
Abstract
In this chapter, we study the universal rigidity problem of bar frameworks and the related problem of dimensional rigidity. The main tools in tackling these two problems are the Cayley configuration spectrahedron \(\mathcal{F}\), defined in (8.​10), and Ω, the stress matrix, defined in (8.​13). The more general problem of universally linked pair of nonadjacent nodes is also studied and the results are interpreted in terms of the Strong Arnold Property and the notion of nondegeneracy in semidefinite programming.
Abdo Y. Alfakih
Backmatter
Metadata
Title
Euclidean Distance Matrices and Their Applications in Rigidity Theory
Author
Abdo Y. Alfakih
Copyright Year
2018
Electronic ISBN
978-3-319-97846-8
Print ISBN
978-3-319-97845-1
DOI
https://doi.org/10.1007/978-3-319-97846-8

Premium Partner

    Image Credits