Let $x_1,...,x_k \in \mathbb{R}^n$. Assume $0 \not\in conv\{x_1,...,x_k\}$. Show there is a $c\in \mathbb{R}^n$ s.t. $c^Tx_i \geq1$ for all $i\in[k]$.

Question

Let $x_1,...,x_k \in \mathbb{R}^n$ and assume $0 \not\in conv\{x_1,...,x_k\}$. Prove that there must be some $c\in \mathbb{R}^n$ such that $c^Tx_i \geq1$ for all $i\in[k]$.

Relevant Theorem: Hyperplane Separation Theorem

Let $P,Q$ be closed, convex, bounded, and disjoint in $\mathbb{R}^n$. Then there exists a $c\in\mathbb{R}^n$ and a $b$ such that $c^Tx<b<c^Ty$ for all $x\in P,\;y\in Q$.

We can look at an example in $\mathbb{R}^2$

Let the origin $\{0\}$ be $P$ and the $conv(x_1,x_2,x_3,x_4)$ be $Q$. The hyperplane separation theorem gives is the green line $H$ where $H=\{z\in\mathbb{R}^2\;|\;c^Tz=b\}$ and $c^T$ is the normal vector (drawn in light blue). Then maybe we can make $b$ be the vector representing $1$? I'm not sure where to continue from here.

Answer 1

From hyperplane separation theorem, we know there exists a $b$ and $\hat{c}$ such that

$$0<b< \hat{c}^Ty ,\forall y \in conv(x_1, \ldots, x_k)$$

Let $c = \frac1b \hat{c}$, then we have

$$c^Tx_i > 1, \forall i \in [k]$$