How many points are required to represent the unit ball in the $\ell_{\infty}$-norm as a convex hull?

Question

Given the unit ball in the $\ell_{\infty}$-norm:

$$C = \{ x : |x_i | \le 1,\ i = 1, \dots, n\}$$

how many points are needed to describe $C$ in the convex hull form of:

$$\{\theta_1v_1 + \cdots + \theta_kv_k \mid \theta_1 + \cdots + \theta_m = 1, \theta_i\ge 0,\ i = 1, \cdots , k\}$$

According to my textbook, the answer is $2^{n}$, but I'm not sure how to show this.

Answer 1

$C$ is a polyhedral since it can be written as

$$C=\{x: -1 \le x_i \le 1, i = 1, \ldots, n \}$$

To be a vertex, $n$ linearly binding constraints are required. For each variable, we choose $x_i \in \{-1,1\}$, that is we have two choices. Hence, the solution is $2^n$.