The real positive definite completion problem for a 4-cycle

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 C4, a 4-cycle, with x and y the two unspecified entries corresponding to the two missing edges of C4. 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 detA(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 detA(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 detA(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 detA(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.