Let $P = \{x\in\mathbb{R}^2\mid Ax\leq b\}$ be a bounded polyhedron. Let $L:\mathbb{R}^n \to\mathbb{R}^k$ be a linear map.

Exercise: Show that $L(P) = \{L(x)\mid x\in P\}$ is a bounded polyhedron.

I know this problem has been answered here, but I'm wondering whether there's a different approach thus uses the fact that a bounded polyhedron polytope is the convex hull of its vertices, because it would further increase my understanding of how convexity and bounded polyhedra relate to each other.

My approach:

We know that $P = \{x\in\mathbb{R}^n\mid Ax\leq b\}$ is a bounded polyhedron. This means that for $x\in P$, we have vectors $p_1,p_2,\ldots,p_{n+1}$ such that $x = p_1\lambda_1 + \cdots + p_{n+1}\lambda_{n+1}.$ For $x\in P$, we have $L(x) = L(p_1\lambda_1 + \cdots + p_{n+1}\lambda_{n+1}) = \lambda_1L(p_1) + \cdots + \lambda_{n+1}L(p_{n+1}).$ Now assume that $L(P)$ is not a bounded polyhedron. This would mean that $L(P)$ is not a convex hull and that there therefore would be a set of vectors $y_1,\ldots,y_n$ such that $L(x) = \lambda_1L(y_1) + \cdots + \lambda_n L(y_n),$ for some $n$. However I think this would imply that $P$ is not a bounded polyhedron either.

Question: How should I proceed? If incorrect; how so?

Thanks in advance!

  • $\begingroup$ You can follow your approach by showing that the set of extremal points of $L(P)$ is a subset of the image by $L$ of the extremal points of $P$. Then since $P$ is the convex hull of its finitely many extremal points, so is $L(P)$. It makes the proof not harder, but surely longer. $\endgroup$ – arts Nov 30 '17 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.