Can $\text{conv} \{ e_1,e_2,e_3, (1/2, 1/2, 1) , (1/2, 1, 1/2) , (1, 1/2, 1/2) \}$ be reduced to a convex hull of a subset of these?

Question

How do I see whether $$\text{conv} \{ e_1,e_2,e_3, (1/2, 1/2, 1) , (1/2, 1, 1/2) , (1, 1/2, 1/2) \}$$

can be reduced to a convex hull of a subset of these vectors?

That is, if $D = \{ e_1,e_2,e_3, (1/2, 1/2, 1) , (1/2, 1, 1/2) , (1, 1/2, 1/2) \}$ does there exist a proper subset $S \subset D$ such that $\text{conv}(D) = \text{conv}(S)$ ?

By inspection it seems that I cannot write any of the vectors as a convex combination of the others, does this imply that $D$ is minimal ?

Answer 1

If a finite set of points satisfies a linear inequality, so does any convex combination of those points. Hence, given a finite set $S$ and a point $t$, if there is a linear inequality that is satisfied by $t$ but not by any member of $S$ then $t\notin \operatorname{conv}(S)$.

Let us now look at every point of $D$.

Point $e_1=(1,0,0)$ satisfies the linear inequality

$$-x+y+z\le -1$$

but none of the other points of $D$ do. [$e_2, e_3,(\frac 12,\frac 12,1),$ and $(\frac 12,1,\frac 12)$ make the left hand side yield $1$, and $(1,\frac 12,\frac 12)$ yields $0$]. Thus $e_1$ cannot be in the convex hull of any subset of $D$ that does not include $e_1$, and therefore $e_1$ must be in any subset $S$ of $D$ that has the same convex hull.

Point $e_2=(0,1,0)$ is the only point in $D$ that satisfies $x-y+z\le -1$.

Point $e_3=(0,0,1)$ is the only point in $D$ that satisfies $x+y-z\le -1$.

Point $(\frac 12,\frac 12,1)$ is the only point in $D$ that satisfies $x+y+2z\ge 3$.

Point $(\frac 12,1, \frac 12)$ is the only point in $D$ that satisfies $x+2y+z\ge 3$.

Point $(1,\frac 12,\frac 12)$ is the only point in $D$ that satisfies $2x+y+z\ge 3$.

We conclude that every point in $D$ must be in any subset of $D$ that has the same convex hull. Therefore, $D$ is minimal.

Answer 2

Any convex combination of positive numbers must be greather than 0, hence {e_1,e_2, e_3} must be in the hull.

Suppose that some of the last 3 vector doesn't exist in the hull, for example $(1/2, 1/2, 1)$. Let $\Delta := conv({e_1,e_2, e_3})$. It is known that vector $(1/2, 1/2, 1)$ can be written as convex combination of vector $v \in \Delta$ and vectors: $(1/2, 1, 1/2)$ , $(1, 1/2, 1/2)$. So there exists $\alpha_1,\alpha_2,\alpha_3 \geq 0$, $\alpha_1 + \alpha_2 +\alpha_3 =1$, $ v=(\alpha_1,\alpha_2,\alpha_3)$, $\beta_1, \beta_2, \beta_3 \geq 0$, $\beta_1 + \beta_2 + \beta_3 = 1$ such that $\beta_1 (\alpha_1,\alpha_2,\alpha_3) + \beta_2 (1/2, 1, 1/2) + \beta_3 (1, 1/2, 1/2) = (1/2, 1/2, 1)$.

We can write 3 equations: $$ \begin{cases} \beta_1 \alpha_1 +\beta_2 1/2 + \beta_3 = 1/2 \\ \beta_1 \alpha_2 +\beta_2 + \beta_3 1/2 = 1/2 \\ \beta_1 \alpha_3 +\beta_2 1/2 + \beta_3 1/2 = 1 \end{cases} $$ If $\beta_1 > 0$, after summing these 3 equations by sides, we get:

$\beta_1 (\alpha_1 + \alpha_2 +\alpha_3)+2(\beta_1+\beta_2) = 2 $

but $\beta_1 (\alpha_1 + \alpha_2 +\alpha_3)+2(\beta_1+\beta_2) = \beta_1 +2(\beta_1+\beta_2) < 2 \beta_1 +2(\beta_1+\beta_2) = 2$ - contraditon.

If $\beta_1 = 0$ we have: $$ \begin{cases} \beta_2 1/2 + \beta_3 = 1/2 \\ \beta_2 + \beta_3 1/2 = 1/2 \\ \beta_2 1/2 + \beta_3 1/2 = 1 \end{cases} $$ after adding 2 first equations by sides, we get: $$ \begin{cases} \beta_2 3/2 + \beta_3 3/2 = 1 \\ \beta_2 1/2 + \beta_3 1/2 = 1 \end{cases} $$ and these equations are contraty.