Bernoulli Correlations and Cut Polytopes

Given  n  symmetric Bernoulli variables, what can be said about their correlation matrix viewed as a vector? We show that the set of those vectors  R ( B n )  is a polytope and identify its vertices. Those extreme points correspond to correlation vectors associated to the discrete uniform distributions on diagonals of the cube  [0,1] n . We also show that the polytope is affinely isomorphic to a well-known cut polytope  CUT( n )  which is defined as a convex hull of the cut vectors in a complete graph with vertex set  {1,…, n } . The isomorphism is obtained explicitly as  R ( B n )= 1 −2 CUT( n ) . As a corollary of this work, it is straightforward using linear programming to determine if a particular correlation matrix is realizable or not. Furthermore, a sampling method for multivariate symmetric Bernoullis with given correlation is obtained. In some cases the method can also be used for general, not exclusively Bernoulli, marginals.