The cycle completable graphs for the completely positive and doubly nonnegative completion problems

A partial matrix is a rectangular array, only some of whose entries are spe cified. The titled completion problem asks if there is a choice of values f or the unspecified entries of a partial matrix resulting in a conventional matrix that is either doubly nonnegative (DN) or completely positive (CP). Since membership in the class of CP (resp. DN) matrces is inherited by prin cipal submatricies, a square partial matrix is called partial CP (DN) if al l of its fully specified principal submatrices are CP (DN). It has been sho wn [J.H. Drew, C.R. Johnson, Linear and Multilinear Algebra 44 (1998) 85-92 ] that all partial CP (DN) matrices with a given undirected graph G have a CP (DN) completion if and only if G is chordal and the maximum number of ve rticies common to two distinct cliques is 1. Because induced cycles prevent a graph from being chordal, we ask land answer) the next most natural ques tion in CP (DN) completion theory: in order to guarantee the existence of a CP (DN) completion, what additional conditions are required on the specifi ed entries of the partial CP (DN) matrix whose graph is a cycle? Moreover, how does one characterize the graphs for which these conditions guarantee t hat a partial CP (DN) matrix has a CP (DN) completion? Surprisingly, the an swer to this last question is the same for both cases, despite the differen ces between CP and DN. (C) 2000 Elsevier Science Inc. All rights reserved.