For a subset $S$ of $\{1,\ldots,n\}$, let $\mathbf{1}_S\in\{0,1\}^n$ denote the indicator vector of $S$, with a $1$ on the $i$th coordinate iff $i\in S$. Let $\mathcal{X}$ denote the convex-hull of all matrices of the form $\mathbf{1}_S \mathbf{1}_S^T$:

$$\mathcal{X}=\operatorname{conv}\left(\big\{\mathbf{1}_S \mathbf{1}_S^T|\, S\in 2^{\{1,\ldots,n\}}\big\}\right).$$

Given a $n \times n$ symmetric matrix $X$, does someone know an algorithm that can either return the message "$X\notin \mathcal{X}$", or returns a decomposition of the form

$$X = \sum_{S\in\mathcal{S}} x_S \mathbf{1}_S \mathbf{1}_S^T$$

with $x_S\geq 0, \sum_{S\in\mathcal{S}} x_S = 1$ ? Or is the problem of determining wheter $X \in \mathcal{X}$ NP-hard? Any reference is welcome!

  • $\begingroup$ I found that this paper of Berman & Xu is handling a very similar problem.[sciencedirect.com/science/article/pii/S0024379504002137]. However, the authors study many special cases, but do not talk about the complexity of the general case (which lets think this is a hard problem...) $\endgroup$
    – guigux
    Jan 8, 2016 at 10:21


Your Answer

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