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?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ It should be assumed that $n' \le k$, since otherwise the diagonal entries of $M$ are larger than one. $\endgroup$ – Andrew Morgan Sep 23 '16 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$ – Sasho Nikolov Sep 23 '16 at 21:49
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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This has a similar flavour of $ E[X] = \int P(X>x) $ $\endgroup$ – Vivek Bagaria Sep 23 '16 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$ – Sasho Nikolov Sep 24 '16 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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