Kendrick Hampton

Answered

2022-07-01

Proving the image of a convex polyhedron under a linear map is a polyhedron

prove for $A\in {\mathbb{R}}^{m\times 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):

$P\subseteq {\mathbb{R}}^{m+n}\text{is a polyhedron}\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\{x\in {\mathbb{R}}^{n}\mid (x,y)\in P\text{for some}y\in {\mathbb{R}}^{m}\}.\text{}\text{}\text{}\text{}(1)$

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=\{x\in {\mathbb{R}}^{n}\mid Bx\le b\}$

and then try to write $A(Q)$ as as system of linear inequalities

$A(Q)=\{y\in {\mathbb{R}}^{m}\mid B\phantom{\rule{thinmathspace}{0ex}}{A}^{-1}\phantom{\rule{thinmathspace}{0ex}}y\le b\}.$

This doesn't quite work since A may not be invertible. More importantly, it does not use the statement (#1) given above.

prove for $A\in {\mathbb{R}}^{m\times 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):

$P\subseteq {\mathbb{R}}^{m+n}\text{is a polyhedron}\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\{x\in {\mathbb{R}}^{n}\mid (x,y)\in P\text{for some}y\in {\mathbb{R}}^{m}\}.\text{}\text{}\text{}\text{}(1)$

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=\{x\in {\mathbb{R}}^{n}\mid Bx\le b\}$

and then try to write $A(Q)$ as as system of linear inequalities

$A(Q)=\{y\in {\mathbb{R}}^{m}\mid B\phantom{\rule{thinmathspace}{0ex}}{A}^{-1}\phantom{\rule{thinmathspace}{0ex}}y\le b\}.$

This doesn't quite work since A may not be invertible. More importantly, it does not use the statement (#1) given above.

Answer & Explanation

lilao8x

Expert

2022-07-02Added 22 answers

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

Now set

$P=\{(x,y):\text{}Bx\le b,\text{}y=Ax\}$

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

Now set

$P=\{(x,y):\text{}Bx\le b,\text{}y=Ax\}$

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

Most Popular Questions