I am working on the following exercise:
Find the extremal points of $K_1 := \{x \in \mathbb{R}^n \mid \sum_{i=1}^n \lvert x_i \rvert \le 1\}$
I have shown that $K_1$ is convex and that the following set is extremal:
$$M_{K_1} := \biggl\{ \pm e_i \mid e_i := (\underbrace{0, \cdots, 0}_{i-1},1, 0, \cdots) \in \mathbb{R}^n \biggr\}.$$
But I do not see how I could formally show that these are indeed ALL extremal points. Could you help me?
(Instead of denoting $x_i$ to be the $i$th entry of $x$, I will write $x \cdot e_i$, since the notation $e_i$ makes this confusing.)
First, note that if $x \in K_1$ does not take this form, and $|x \cdot e_i| = 1$ for some $i$, then $x \cdot e_j = 0$ for all $j \neq i$, and hence $x \in M_{K_1}$. To see this, suppose $|x \cdot e_i| = 1$. Then, $$\sum_{j \neq i} |x \cdot e_j| = \sum_{j \ge 1} |x \cdot e_j| - |x \cdot e_i| = 1 - 1 = 0.$$ If $|x \cdot e_j| > 0$ for any $j \neq i$, then we would have the left side be strictly positive, and hence the claim holds.
So, suppose $x \notin M_{K_1}$, and let $i$ be such that $x \cdot e_i \neq 0$, and note that $|x \cdot e_i| < 1$. Let $$N = \sum_{j \neq i} |x \cdot e_j| = 1 - |x \cdot e_i| \in (0, 1).$$ Define $$y = \frac{x - (x \cdot e_i) e_i}{N}.$$ Then $$y \cdot e_j = \begin{cases} \dfrac{x \cdot e_j}{N} & \text{if }j \neq i \\ 0 & \text{if }j = i. \end{cases}$$ Hence, $$\sum_{j \ge 1} |y \cdot e_j| = \sum_{j \neq i} \frac{|x \cdot e_j|}{N} = \frac{N}{N} = 1,$$ and so $y \in K_1$. I claim that $$x = Ny + (1 - N)\operatorname{sgn}(x \cdot e_i)e_i.$$ Note that $\operatorname{sgn}(x \cdot e_i)e_i \in M_{K_1} \subseteq K_1$, so we will have $y$ as a strict convex combination of two distinct elements of $K_1$, proving $x$ is not extreme.
We have, \begin{align*} x &= x - (x \cdot e_i)e_i + (x \cdot e_i)e_i \\ &= Ny + |x \cdot e_i|\operatorname{sgn}(x \cdot e_i)e_i \\ &= Ny + (1 - N)\operatorname{sgn}(x \cdot e_i)e_i, \end{align*} completing the proof. Thus, if $x \notin M_{K_1}$, then $x$ is not extreme.
