# Proving a set is a convex hull of another set

I need to prove that the convex hull of the finite set: $$S= \{x\in\{0,1\}^d|\left\Vert x \right\Vert_0\leq k\}$$ is the set: $$T=\{x\in\left[ 0,1\right]^d|\left\Vert x \right\Vert_1\leq k\}$$

Where $$\left\Vert x \right\Vert_0$$ is the L0 "norm" (not really a norm), meaning the number of non-zero elements of $$x$$, and $$k$$ is an integer.

I already know how to show that $$conv S\subseteq T$$, but have trouble with the opposite direction. I tried to describe a vector $$x\in T$$ as a convex combination of those of $$S$$ but it seemed a little complicated to me. I would appreciate your assistance.

• If $k<1$ then $S$ is just the origin whereas $T$ has an interior. Apr 27 '20 at 8:03
• $k$ is an integer, added to the question description, thanks. Apr 27 '20 at 8:05

If $$x \in \{0,1\}^d$$ then $$\|x\|_0 = \|x\|_1$$. Hence $$S \subset T$$ and since $$T$$ is convex, $$\operatorname{co} S \subset T$$.
Suppose $$x$$ is an extreme point of $$T$$, then $$x \in \{0,1\}^d$$ (and $$\|x\|_1 \le k$$, of course). To see this, suppose $$x_i \in (0,1)$$ for some $$i$$.
If $$\|x\|_1 = k$$, then there is some $$j \neq i$$ such that $$x_j \in (0,1)$$ and hence $$\|x+t (e_i-e_j)\|_1 = k$$ for $$t$$ in some open interval containing zero and $$x_i+t,x_j-t \in [0,1]$$. Hence $$x$$ cannot be an extreme point.
If $$\|x\|_1 < k$$ then $$x+t e_i \in T$$ for $$t$$ in some open interval containing zero and hence $$x$$ cannot be extreme.
Hence if $$x$$ is extreme, then $$x\in\{0,1\}^d$$ and hence $$\|x\|_0 = \|x\|_1 \le k$$ and so $$x \in S$$.
Since $$T$$ is the convex hull of its extreme points, we see that $$T \subset \operatorname{co} S$$.