0

Let $\mathcal{M}\subseteq\mathbb{R}^n$ a polyhedron, $D\in\mathbb{R}^{m\times n}, c\in\mathbb{R}^m$. How do I show that $\mathcal{R}=\{Dx+c:x\in\mathcal{M}\}$ is a polyhedron? I know that a polyhedron can be defined as the convex hull of a finite set of points, but I really don't know how to use that to answer this question. I would really appreciate it, if someone could explain this to me.
Thanks in advance!

user619755
  • 620

1 Answers1

2

The reason is the following: $\mathcal{R}$ is obtained via an affine transformation of $\mathcal{M}$. But affine transformations preserve affine combinations. That is, if $A,B\in\mathcal{M}$ and $C=\alpha A+\beta B$ with $\alpha+\beta=1$, then given any affine transformation $f$, $f(C)=\alpha f(A)+\beta f(B)$ (the proof of this fact is just a line). Therefore, if $C$ is in the segment joining $A$ and $B$, then $f(C)$ is in the segment between $f(A)$ and $f(B)$ (in this case $\alpha, \beta\ge 0$). This property extends to several points, so if $C$ is in the convex hull of a finite set of points, $f(C)$ is in the convex hull of their images. Finally, since $\mathcal{M}$ is a polyhedron, $f(\mathcal{M})$ will be a polyhedron as well, namely the convex hull of the images of the points that generate $\mathcal{M}$.

GReyes
  • 16,446
  • 11
  • 16
  • Thank you, this makes it very easy to understand. Last question, A and B are subsets of $\mathcal{M}$, are they also polyhedra? – user619755 Jan 19 '20 at 13:28
  • 1
    In my answer, I used $A$ and $B$ to represent points in the original polyhedron (not general subsets), and $C$ to denote a point that is is in the segment joining them. Technically, points are polyhedra. – GReyes Jan 19 '20 at 16:12