# Properties of convex polytope of 0-1 matrices

Problem setting

Consider a set $S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$.

Consider a $k\times k$ matrix $M$ s.t $\;M_{ij} = \big|S_i\cap S_j\big|\big/n'$, size of the intersection of the $i^{th}, j^{th}$ subset divided by $n'$.

Question

Does $M_{ij}$ lie in the polytope of zero-one matrices? Paraphrasing the question - Can we express every $M_{ij}$ as a convex combination of zero-one matrices?

• It should be assumed that $n' \le k$, since otherwise the diagonal entries of $M$ are larger than one. – Andrew Morgan Sep 23 '16 at 21:07
• The convex hull of zero-one matrices consists exactly of the matrices whose entries are in $[0,1]$. So I think the answer to your question is "yes". – Sasho Nikolov Sep 23 '16 at 21:49

Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M = \sum_{\ell=1}^{n'} \frac{1}{n'} B_\ell$.
• This has a similar flavour of $E[X] = \int P(X>x)$ – Vivek Bagaria Sep 23 '16 at 23:31
• In case it wasn't obvious, let me add that the convex hull of zero-one vectors in $\mathbb{R}^d$ is $[0,1]^d$. So there is nothing specific in this answer about $k \times k$ matrices, which are the special case of $d=k^2$ (up to an obvious bijection between $k$ by $k$ matrices and $\mathbb{R}^{k^2}$). – Sasho Nikolov Sep 24 '16 at 19:08