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

A real symmetric matrix is doubly-nonnegative if it is positive semidefinite and has nonnegative entries; it is completely positive if it can be written in the form \(BB^T\) where \(B\) is a rectangular matrix with nonnegative entries. This paper extends earlier work by the first two authors [Linear Multilinear Algebra 44, No. 1, 85-92 (1998; Zbl 0911.15012)] on the same lines. Namely, it studies conditions under which the missing entries of a partial matrix can be completed to make a doubly-nonnegative or completely positive matrix. The partial matrix may be thought of as an adjacency matrix for a graph and the central case studied here is when this graph is a cycle. The main results use graph theoretic lemmas which may be of independent interest. A block graph (a name, incidentally, with different meaning(s) already associated with it) is defined to be one in which every block is a clique or a cycle. Several characterisations of block graphs are then given.