4
$\begingroup$

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?

$\endgroup$
  • 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 Kallus Aug 11 '17 at 17:33
  • $\begingroup$ Sorry for that! I rewrote it and hopefully it is clear now. $\endgroup$ – SMD Aug 11 '17 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řábek Aug 11 '17 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 Kallus Aug 11 '17 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$ – SMD Aug 11 '17 at 18:26
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.