I came across the following problem asking me to prove for $A\in \mathbb{R}^{m \times n}$ and a convex polyhedron $Q \subseteq \mathbb{R}^n$ that the set $$ A(Q) = \{ y = Ax \mid x \in Q \} $$ is also a convex polyhedron. However, I am asked to do so using the following statement about convex polyhedra (which is easy to prove): \begin{equation} P \subseteq \mathbb{R}^{m+n} \text{ is a polyhedron } \implies \{ x \in \mathbb{R}^n \mid (x,y) \in P \text{ for some } y \in \mathbb{R}^m \}. ~~~~(1) \end{equation} 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\,A^{-1}\, 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. Any useful suggestions are appreciated.
Statement $(1)$ tells us the projection maps (over any variables) take polyhedral to polyhedral.
Now set $$P=\{(x,y) :~ Bx \leq b , ~ 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.