<p>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$.</p>

CC BY-SA 3.0
2016-09-23T23:31:03.583Z
This has a similar flavour of $ E[X] = \int P(X>x) $
Vivek Bagaria
CC BY-SA 3.0
2016-09-24T19:08:11.470Z
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
CC BY-SA 3.0
2016-09-23T21:51:42.517Z
2016-09-23T21:51:42.517Z
Andrew Morgan
<p><strong>Problem setting</strong></p>

<p>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$. </p>

<p>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'$.</p>

<p><strong>Question</strong></p>

<p>Does $M_{ij}$ lie in the polytope of <a href="https://en.wikipedia.org/wiki/Logical_matrix" rel="nofollow"><em>zero-one</em> matrices</a>? Paraphrasing the question - Can we express every $M_{ij}$ as a convex combination of <a href="https://en.wikipedia.org/wiki/Logical_matrix" rel="nofollow"><em>zero-one</em> matrices</a>?</p>

CC BY-SA 3.0
2016-09-23T21:07:21.397Z
It should be assumed that $n' \le k$, since otherwise the diagonal entries of $M$ are larger than one.
Andrew Morgan
CC BY-SA 3.0
2016-09-23T21:49:02.137Z
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
<reference-request><matrices><convex-optimization><submodularity><polytope>
Properties of convex polytope of 0-1 matrices
Vivek Bagaria
# Properties of convex polytope of 0-1 matrices

(Asked by: username_0 on 2016-09-23)

**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](https://en.wikipedia.org/wiki/Logical_matrix)? Paraphrasing the question - Can we express every $M\_{ij}$ as a convex combination of [*zero-one* matrices](https://en.wikipedia.org/wiki/Logical_matrix)?

**Tags:** reference-request, matrices, convex-optimization, submodularity, polytope

> **Comments:**
> **username_1**: It should be assumed that $n' \le k$, since otherwise the diagonal entries of $M$ are larger than one.  
> **username_2**: 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".  

---

## 1 answers

### Answer by username_1 on 2016-09-23. Score: 3 | Accepted answer

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$.

> **Comments:**
> **username_0**: This has a similar flavour of $ E[X] = \int P(X>x) $  
> **username_2**: 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}$).  

---

