Kendrick Hampton

2022-07-01

Proving the image of a convex polyhedron under a linear map is a polyhedron
prove for $A\in {\mathbb{R}}^{m×n}$ and a convex polyhedron $Q\subseteq {\mathbb{R}}^{n}$ that the set
is also a convex polyhedron. However, I am asked to do so using the following statement about convex polyhedra (which is easy to prove):

This seems like it should be easy but I'm having trouble.
One approach is to write $Q$ as a set of linear inequalities
$Q=\left\{x\in {\mathbb{R}}^{n}\mid Bx\le b\right\}$
and then try to write $A\left(Q\right)$ as as system of linear inequalities
$A\left(Q\right)=\left\{y\in {\mathbb{R}}^{m}\mid B\phantom{\rule{thinmathspace}{0ex}}{A}^{-1}\phantom{\rule{thinmathspace}{0ex}}y\le b\right\}.$
This doesn't quite work since A may not be invertible. More importantly, it does not use the statement (#1) given above.

lilao8x

Expert

Statement (1) tells us the projection maps (over any variables) take polyhedral to polyhedral.
Now set

Clearly $P$ is polyhedral. Now observe that the projection map $\left(x,y\right)\to y$ takes $P$ to $A\left(Q\right)$. Therefore $A\left(Q\right)$ is a polyhedral.

Do you have a similar question?