Positive semidefinite matrix completion, universal rigidity and the Strong Arnold Property
| Autor: | Monique Laurent, Antonios Varvitsiotis |
|---|---|
| Přispěvatelé: | Networks and Optimization, Econometrics and Operations Research, Research Group: Operations Research |
| Rok vydání: | 2014 |
| Předmět: |
universal rigidity
Semidefinite programming Numerical Analysis Algebra and Number Theory Matrix completion graph rigidity Positive-definite matrix tensegrity framework semidefinite programming Type graph Strong Arnold Property Combinatorics nondegeneracy Matrix (mathematics) Rigidity (electromagnetism) Optimization and Control (math.OC) Tensegrity Elementary proof FOS: Mathematics Discrete Mathematics and Combinatorics Geometry and Topology matrix completion Mathematics - Optimization and Control Mathematics |
| Zdroj: | Linear Algebra and its Applications, to appear Linear Algebra and its Applications, 452, 292-317. Elsevier Inc. |
| ISSN: | 0024-3795 |
| DOI: | 10.1016/j.laa.2014.03.015 |
| Popis: | 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 $\nu^=(\cdot)$. Comment: 28 pages, 3 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect