HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
Random Processes of the Form Xn + 1 = anXn + bn (mod p)
Where bn Takes On a Single Value
Summary

MARTIN HILDEBRAND

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 = BBT 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

Go