# Can extreme points always be projected to be extreme points?

Consider a bounded polyhedron $P$, and a dimension reducing projection $\Omega$ (ie a linear operator $\Omega$ such that $\Omega^2 = \Omega$), claim: if $u$ is an extreme point of $P$ then $\exists \Omega$ such that $\Omega u$ is an extreme point of $\Omega P$

## Intuition:

Intuitively this feels obvious, I can take any polytope, consider any vertex, and there always seems to be a "right way" to look at the shape, so that if I were to squash the shape along an axis perpendicular to the axis-of-sight I end up with a lower dimensional shape that ALSO has an extreme point induced by original extreme point.

Perhaps some more formal intuition: we have that every vertex in the projection $\Omega P$ is the projection of a vertex in $P$, not immediately helpful but it gives us an idea to work with.

## So my attempt at a proof:

Consider such a point $u$. There will be a collection of inequalities (at least $n$ if we are in $\mathbb{R}^n$ ) that are tight for this point. That is

$$a_1^T u = b_1 \\ a_2^T u = b_2 \\ \vdots \\ a_n ^T u = b_n$$

Of course this can be rephrased as

$$A^T u = B$$

Now Suppose the general polyhedron of which $u$ is an extreme point is:

$$Cx \le d$$

Now what I want to do, but don't know how to express mathematically, is that I want to compute an abstract projection of this polyhedron $\Omega(Cx \le d)$ , then I want to compute the same abstract projection of $A^T$, reason that none of the inequalities of the $\Omega A^T$ subset of $\Omega C$ is redundant, and then show that $\Omega u$ is tight for them, letting me conclude that that $\Omega u$ is an extreme point of projected polyhedra.

But formally, I don't know how to express that. And it may not even be the best way.

• Is your polyhedron convex? – Hagen von Eitzen Aug 10 '16 at 5:57
• Yes, it is convex – frogeyedpeas Aug 10 '16 at 6:11

Take a vector $n \in \mathbb{R}^n$ such that $$n^\top u > n^\top p \qquad\forall p \in P\setminus\{u\}.$$ Such an $n$ exists since every extreme point of a polytope is exposed.
Then, you use $$\Omega(x) := (n^\top x) \, n.$$