Positive Semidefinite Matrix Completion, Universal Rigidity and the Strong Arnold Property

Understand

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.