Polyhedron question

117 Views Asked by At

Below is a property of polyhedron, which refers to when shrinking the dimension of a polyhedron down, it is still a polyhedron: \begin{equation} \label{eq:poly_proj} P \subseteq \mathbb{R}^{m+n} \text{ is a polyhedron} \; \Rightarrow \; \{x\in \mathbb{R}^n : (x,y)\in P \text{ for some } y\in\mathbb{R}^m\} \text{ is a polyhedron}. \end{equation}

Now my question is, can I use the property above to prove that if $A\in \mathbb{R}^{m\times n}$ and $P\subseteq \mathbb{R}^n$ is a polyhedron then $A(P) = \{ Ax : x \in P \}$ (the image) is a polyhedron as well?

1

There are 1 best solutions below

3
On

The matrix $A$ describes a linear map from $X:={\mathbb R}^n$ to $Y:={\mathbb R}^m$. If $A$ has rank $r$ you can choose bases in $X$ and $Y$ independently such that the resulting matrix $\tilde A$ has $r$ ones in the main diagonal, and the rest zeros. This $\tilde A$ then describes a projection of the kind described in the quoted principle.