2

By "preservation of extreme points under linear transformation" (answer from @mathcounterexamples.net), the following statement holds:

Suppose $\mathcal{C}\subset\mathbb{R}^n$ is a compact convex set and $L:\mathbb{R}^n\to\mathbb{R}^m$ is a linear surjective (but not injective) map. Let $\text{ext}(\mathcal{C})$ denote the set of all extreme points of $\mathcal{C}$ and $L(\mathcal{S})=\{L\mathbf{x} \,|\, \mathbf{x}\in\mathcal{S}\}$ for any $\mathcal{S}\subset\mathbb{R}^n$. Then $\text{ext}(L(\mathcal{C}))\subset L(\text{ext}(\mathcal{C}))$.

How can one prove this statement? Or, alternatively, is there any reference that shows this claim? I am also wondering if it is necessary that $L$ is surjective, i.e., is it for example enough that $L$ is just linear?

I looked at the following example: Let $\mathcal{C}=\text{convexHull}(\mathcal{A})$, where $\mathcal{A}=\{(1,0), (2, 0), (1, 1), (2, 1)\}$, and $L(\mathbf{x})=[1\; 0]\,\mathbf{x}$. Then $\text{ext}(\mathcal{C})=\mathcal{A}$, $L(\mathcal{C})=\{x\in\mathbb{R} \,|\, 1\le x \le2\}$ and $\text{ext}(L(\mathcal{C}))=\{1,2\}$. As $L(\text{ext}(\mathcal{C}))=\{1,2\}$, the statement holds in this example, but does it in general?

Beton
  • 33

1 Answers1

3

This is true and $L$ is not required to be surjective. A convex compact subset of $\mathbb{R}^n$ is the convex hull of its extreme points. Now suppose $y$ is an extreme point of $L(C)$. Take any $x\in C$ such that $L(x)=y$. We can write $x$ as a convex combination of extreme points of $C$, so $x=\alpha_1 e_1+\cdots+\alpha_m e_m.$ Since $L$ is linear, $y=\alpha_1 L(e_1)+\cdots+\alpha_m L(e_m)$. Since $y$ is an extreme point, we must have $L(e_1)=\cdots=L(e_m)$. Consequently, $y=L(e_1)$.

Michael Greinecker
  • 32,841
  • 6
  • 80
  • 137