Positive semidefinite matrix completion, universal rigidity and the strong Arnold property

DOI10.1016/J.LAA.2014.03.015MaRDI QIDQ2451678zbMATH OpenOpenAlexFDO

Authors Monique Laurent, A. Varvitsiotis

Publication date 4 June 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.6616

zbMATH Keywords

matrix completionnondegeneracysemidefinite programmingStrong Arnold Propertytensegrity frameworkuniversal rigidity

Mathematics Subject Classification ID

Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Semidefinite programming (90C22)

Abstract: This paper addresses the following three topics: positive semidefinite (psd) matrix completions, universal rigidity of frameworks, and the Strong Arnold Property (SAP). We show some strong connections among these topics, using semidefinite programming as unifying theme. Our main contribution is a sufficient condition for constructing partial psd matrices which admit a unique completion to a full psd matrix. Such partial matrices are an essential tool in the study of the Gram dimension $gd(G)$ of a graph $G$, a recently studied graph parameter related to the low psd matrix completion problem. Additionally, we derive an elementary proof of Connelly's sufficient condition for universal rigidity of tensegrity frameworks and we investigate the links between these two sufficient conditions. We also give a geometric characterization of psd matrices satisfying the Strong Arnold Property in terms of nondegeneracy of an associated semidefinite program, which we use to establish some links between the Gram dimension $gd(cdot)$ and the Colin de Verdi`ere type graph parameter $u^{=}(cdot)$.

Recommendations

• Positive semidefinite completions of partial Hermitian matrices
• Complexity of the positive semidefinite matrix completion problem with a rank constraint
• Positive definite completions and determinant maximization
• Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming
• A new algorithm for positive semidefinite matrix completion
• On (conditional) positive semidefiniteness in a matrix-valued context
• Strictly semi-positive tensors and the boundedness of tensor complementarity problems
• Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
• A connection between positive semidefinite and Euclidean distance matrix completion problems
• Positive semidefinite matrices, exponential convexity for majorization, and related Cauchy means

Cites work

• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• A Note on Extreme Correlation Matrices
• Characterizing the universal rigidity of generic frameworks
• Complementarity and nondegeneracy in semidefinite programming
• Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
• Generic global rigidity
• Global rigidity: The effect of coning
• Graphs with magnetic Schrödinger operators of low corank
• scientific article; zbMATH DE number 1303522 (Why is no real title available?)
• scientific article; zbMATH DE number 1534289 (Why is no real title available?)
• Multiplicities of eigenvalues and tree-width of graphs
• On bar frameworks, stress matrices and semidefinite programming
• On dimensional rigidity of bar-and-joint frameworks
• On the null space of a Colin de Verdière matrix
• On the universal rigidity of generic bar frameworks
• Polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems
• Positive definite completions of partial Hermitian matrices
• Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming
• Rigidity and energy
• Semidefinite Optimization and Convex Algebraic Geometry
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• The Gram dimension of a graph
• The real positive definite completion problem for a simple cycle
• The real positive semidefinite completion problem for series-parallel graphs
• Two tree-width-like graph invariants
• Uniqueness of low-rank matrix completion by rigidity theory

Cited in

(22)

• Partial identification in the statistical matching problem
• Typical ranks in symmetric matrix completion
• Vector coloring the categorical product of graphs
• Symmetric matrices whose entries are linear functions
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• Universal completability, least eigenvalue frameworks, and vector colorings
• Global rigidity of triangulations with braces
• Graph homomorphisms via vector colorings
• On affine motions and universal rigidity of tensegrity frameworks
• Graph cores via universal completability
• Global completability with applications to self-consistent quantum tomography
• Matrices with high completely positive semidefinite rank
• Nullspace embeddings for outerplanar graphs
• Universal rigidity of bar frameworks via the geometry of spectrahedra
• Constrained best Euclidean distance embedding on a sphere: a matrix optimization approach
• Singularity degree of the positive semidefinite matrix completion problem
• Super stable tensegrities and the Colin de Verdière number
• Realizable dimension of periodic frameworks
• The Lovász theta function for recovering planted clique covers and graph colorings
• The algebraic frustration dimension of a graph
• Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
• Half thresholding eigenvalue algorithm for semidefinite matrix completion

This page was built for publication: Positive semidefinite matrix completion, universal rigidity and the strong Arnold property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2451678)