1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ It should be assumed that $n' \le k$, since otherwise the diagonal entries of $M$ are larger than one. $\endgroup$ Commented Sep 23, 2016 at 21:07
  • 2
    $\begingroup$ 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". $\endgroup$ Commented Sep 23, 2016 at 21:49

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ This has a similar flavour of $ E[X] = \int P(X>x) $ $\endgroup$ Commented Sep 23, 2016 at 23:31
  • 3
    $\begingroup$ 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}$). $\endgroup$ Commented Sep 24, 2016 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.