Positive semidefinite matrix completion, universal rigidity and the Strong Arnold Property

Monique Laurent, A. Varvitsiotis

Research output: Contribution to journalArticleScientificpeer-review

22 Citations (Scopus)

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 of a graph G, a recently studied graph parameter related to the low rank 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 and the Colin de Verdière type graph parameter.
Original languageEnglish
Pages (from-to)292-317
JournalLinear Algebra and its Applications
Volume452
DOIs
Publication statusPublished - Jul 2014

Keywords

  • matrix completion
  • tensegrity framework
  • universal rigidity
  • semidefinite programming
  • Strong Arnold Property
  • nondegeneracy

Fingerprint

Dive into the research topics of 'Positive semidefinite matrix completion, universal rigidity and the Strong Arnold Property'. Together they form a unique fingerprint.

Cite this