0

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?

Michael Hardy
  • 1
good2know
  • 665
  • 1
    \text{} embeded in math mode embedded in \text{} embedded in math mode is new to me. And it's a purposeless complication. $\qquad$ – Michael Hardy Sep 06 '16 at 01:40

1 Answers1

1

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.

Christian Blatter
  • 226,825
  • Thanks for you answer! Just one question, is X still a polyhedron under the new bases? How can I prove that? – good2know Sep 07 '16 at 06:23
  • The polyhedron is $P$. I wrote $X$ and $Y$ for the spaces in order to make it clear that we can choose bases independently. – Whether some object $P$ is a polyhedron or not has nothing to do with bases. I don't know what is your primary definition: Convex hull of finitely many points or intersection of half spaces. – Christian Blatter Sep 07 '16 at 16:41
  • Hi, thanks for your explanation! However my confusion lies in how to prove that the change of bases does not affect the property of polyhedron, because what I am thinking is, the bases change itself is a linear mapping, which lead us to the original problem to be proved. – good2know Sep 11 '16 at 20:45