The No Long Odd Cycle Theorem for Completely Positive Matrices

摘要: We present a self-contained proof of the following fact. Let an undirected graph G be given. Every symmetric matrix A, with G, that is both entry-wise nonnegative and positive semidefinite can written as A = BBT B if only has no odd cycle length 5 or more. In process, we determine worst case for minimum number columns in representation such A. An n-by-n (aij) called completely may which n-by-m nonnegative. write E CP, C Pn it necessary to indicate dimension. Though they arise variety ways (H), there yet definitive test com­ pletely positive. Recent work also related CP matrices exchangeable probability distributions on finite sample spaces (D). straightforward ob­ servation definition complete positivity could equivalently stated