Distance Matrix Completions

Charles Johnson, College of William and Mary

Workshop on Distance Geometry, Semidefinite Programming and Applications

Date and Time: Monday, May 10, 2021 - 10:30am to 11:30am

Abstract: A partial matrix is one in which some entries are specified, while the remaining, unspecified entries are free to be chosen. A completion of a partial matrix is a choice of values for the unspecified entries, resulting in a conventional matrix. Given a matricial property P ,the P-completion problem asks which partial matrices have a completion with property P. Recently, it has been noted that if P may be viewed as a semi-algebraic set, then for each given pattern or the specified entries of partial matrices, the P-completable ones also form a semi-algebraic set. (Thus, there are finitely many algebraic equalities and inequalities that determine whether a completion exists.) Because of the link with positive definite matrices, the (Euclidean) distance matrices form a semi-algebraic set. (As well as other notions of distance.) For certain patterns, the distance completable partial matrices are exactly those that are ""partial distance matrices"" (every fully specified principal submatrix is a distance matrix), an obvious necessary condition. We characterize these patterns. This has geometric implicationsand implications for other patterns. Distance matrices have special spectral properties. We also hope to comment on the Euclidean distance inverse eigenvalue problem.