Let $(\lambda_1 , \cdots , \lambda_d) \vdash k$ be a partition of $k$ of length $d$. Is there any way to decide if $0 \in \text{Conv}\{(\underbrace{\alpha_1, \cdots, \alpha_1}_{\lambda_1}, \cdots , \underbrace{\alpha_d , \cdots, \alpha_d}_{\lambda_d}) \in \mathbb{Z}^k: \, (\alpha_1, \cdots , \alpha_d) \in \mathbb{Z}^d,\, \sum_{i=1}^d \alpha_i = 0\}$, where not all $\alpha_i$s are zero?
8
-
1$\begingroup$ I don't understand what the set is of which you're taking the convex hull. The way it's written now it seems like the set is $\{\lambda_i\alpha_i:i=1,\ldots,d\}$ which is a set of integers, not a set of points in $\mathbb{Z}^d$. $\endgroup$– Yoav KallusAug 11, 2017 at 17:33
-
$\begingroup$ Sorry for that! I rewrote it and hopefully it is clear now. $\endgroup$– SMDAug 11, 2017 at 17:57
-
2$\begingroup$ Convex combination preserves the property that the first $\lambda_1$ coordinates are the same, etc. That is, if all the $\lambda_i$ are positive, the question is equivalent to simply if $0\in\mathrm{Conv}\{(\alpha_1,\dots,\alpha_d)\in\mathbb Z^d:\sum_{i=1}^d\alpha_i=0\}$. Either way, the answer is trivially yes, as $0$ (by which I assume you mean $(0,\dots,0)$) is already in the given set. Or am I missing something? $\endgroup$– Emil JeřábekAug 11, 2017 at 18:14
-
1$\begingroup$ OK, the new formulation parses, but also seems like it must be wrong. $0\in\mathbb{Z}^k$ is a point of the set, so obviously it is in its convex hull. $\endgroup$– Yoav KallusAug 11, 2017 at 18:14
-
$\begingroup$ I am sorry guys! Added one more edit. In fact, we know that $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_d$. $\endgroup$– SMDAug 11, 2017 at 18:26
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
Like Emil noted in the comments, the question is equivalent to whether $0\in\mathrm{Conv}(\{\alpha\in\mathbb{Z}^d: \sum_{i=1}^{d}\alpha_i=0\}\setminus\{0\})$. To see that it is, note that it is the average of $(d-1,-1,-1,\ldots,-1)$ and its permutations.
answered Aug 11, 2017 at 18:28
$\begingroup$
$\endgroup$
Given $n$ points $x_i \in \mathbb R^d$, $0$ is in their convex hull iff there is no $y \in \mathbb R^d$ such that $y \cdot x_i \ge 1$ for all $i$. You can use linear programming software to check this.
answered Aug 11, 2017 at 17:44