Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming

Let G = (V, E) be a graph. In matrix completion theory, it is known that the following two conditions are equivalent: (i) G is a chordal graph; (ii) Every G-partial positive semidefinite matrix has a positive semidefinite matrix completion. In this paper, we relate these two conditions to constraint nondegeneracy condition in semidefinite programming and prove that they are each equivalent to; (iii) For any G-partial positive definite matrix that has a positive semidefinite completion, constraint nondegeneracy is satisfied at each of its positive semidefinite matrix completions. (c) 2008 Elsevier Inc. All rights reserved.