We present a self-contained proof of the following fact. Let an undirected graph G be given. Every symmetric matrix A, with graph G, that is both entry-wise nonnegative and positive semidefinite can be written as A = BB^T with B entry-wise nonnegative if and only if G has no odd cycle of length 5 or more. In the process, we determine the worst case for the minimum numberof columns in B in the representation of such an A.



Back to Random Discrete Structures Table of Contents