The real positive semidefinite completion problem for series-parallel graphs Original Research Article

We consider the partial real symmetric matrices X whose diagonal entries are equal to 1 and whose off-diagonal entries are specified only on a subset of the positions. The question is to determine whether Xcan be completed to a positive semidefinite matrix. Extending a result of Barrett et al. [3], we give a set of necessary conditions for X to be completable and show that these conditions are also sufficient if and only if the graph corresponding to the positions of the specified entries is series-parallel (i.e., has no K4-minor).