Journal Title, Volume, Page:

Linear Algebra and its Applications Volume 336, Issues 1–3 , Pages 131–166
Year of Publication:

2001
Preferred Abstract (Original):

The positive semidefinite (PSD) completion problem is concerned
with determining the set of PSD completions of a partial matrix.
Previous work has focused on determining whether or not a given partial
PSD matrix has a PSD completion, by examining characteristics of the
graph of the matrix. Our aim is to move beyond the existence question to
that of describing the set of all PSD completions of a given partial
matrix. To this end, we consider the most fundamental nontrivial
instance of the problem. Let *A*(*x*,*y*) be a real PSD matrix of order 4 whose graph is *C*_{4}, a 4-cycle, with *x* and *y* the two unspecified entries corresponding to the two missing edges of *C*_{4}. We investigate the problem of giving a precise description of the convex region *R* inside the square |*x*|⩽1,|*y*|⩽1 for which *A*(*x*,*y*) is PSD. The boundary curve ∂*R* is determined by the quartic polynomial equation det*A*(*x*,*y*)=0; an important feature of our description is the set of singular points on ∂*R*. We find necessary and sufficient conditions on the specified entries of *A*(*x*,*y*) so that det*A*(*x*,*y*) factors with 1, 2, 3 or 4 singular points on ∂*R* corresponding to the points of intersection of the curves of all factors of det*A*(*x*,*y*). We then find necessary and sufficient conditions on the specified entries of *A*(*x*,*y*) so that *A*(*x*,*y*) has rank 2 PSD completions. We show that this can occur in three ways: either there is a unique PSD completion (*R* is a single point), or det*A*(*x*,*y*) factors (with the occurrence of singular points), or the PSD completion region *R* contains a unique rank 2 PSD completion which is a singular point, but *R* is not a single point. We also show that the results mentioned above can be generalized for any partial PSD matrix of order *n*>4 whose graph is missing two nonadjacent edges.