I am reading this book on linear programming, and the authors give an excellent exposition of the topic by the interplay between the underlying algebra and geometry. Their main approach is to motivate the main results by geometry and then carry out the mechanics by algebra. In this avenue, they have given some examples of visualizing a standard two dimensional polyhedron $P$, which is a subset of a six dimensional Euclidean space $\mathbb{R}^6$ as shown in the figure below.
$\qquad\qquad\quad\qquad$
To make things more precise and concrete, let me give some definitions and an example to work with.
Definition. Let $A\in\mathbb{R}^{m,\,n}$ be a matrix with $m$ rows and $n$ columns where $\text{rank} A = m$. The set of points $P=\{\mathbb{x}\in\mathbb{R}^n | A\mathbb{x}=\mathbb{b}, \, \mathbb{x} \ge \mathbb{0} \}$ is said to be a standard polyhedron in $\mathbb{R}^n$. The dimension of $P$ is defined to be the dimension of the smallest affine subspace of $\mathbb{R}^n$ that contains $P$.
It is also straight forward to conclude that
Lemma. Let $S=\{\mathbb{x}\in\mathbb{R}^n | A\mathbb{x}=\mathbb{b}\}$. Then $S$ is the smallest affine subspace that contains $P$. Furthermore, we have $\dim P = \dim S = \dim \text{null} A = n – m$.
Example. Let us consider the following polyhedron $P\subset\mathbb{R}^4$
\begin{align}
P = \Big\{ &\mathbf{x} =
\begin{bmatrix}
x_1, & x_2, & x_3, & x_4
\end{bmatrix}^\top \in \mathbb{R}^4 \Big| \\
&1 x_1 – 2 x_2 + 1 x_3 + 2 x_4 = 2, \\
&2 x_1 + 1 x_2 + 0 x_3 – 1 x_4 = 2, \\
& x_1, \, x_2, \, x_3, \, x_4 \ge 0
\Big\}
\end{align}
It is easy to check that $\dim P = 4 – 2 = 2$. So, it is a two dimensional object and it may be suggesting that there is a way to visualize it in $\mathbb{R}^2$. I am wondering that if we can obtain the algebraic equations that describe $P$ in $\mathbb{R}^2$ and helps us to visualize it. The first thing that comes to my mind is to project $P$ on $\mathbb{R}^2$. How can we do this effectively, so that we can get something like the above figure?
Question 1. Given the algebraic equations of a standard polyhedron (as in the example), I am wondering if there is a way to obtain such a visualization?
Question 2. Given that the projection idea works, it seems natural to ask that is the projection of a polyhedron a polyhedron too?
Best Answer
Answer 1. In the example we have $m=2$, $n=4$ and $n-m=2$. The pertinent matrices and vectors can be defined as follows
\begin{align} A &= \begin{bmatrix} 1 & -2 & 1 & 2 \\ 2 & 1 & 0 & -1 \end{bmatrix} \\ \mathbf{x} &= \begin{bmatrix} x_1 & x_2 & x_3 & x_4 \end{bmatrix}^\top \\ \mathbf{b} &= \begin{bmatrix} 2 & 2 \end{bmatrix}^\top. \end{align}
It easy to check that $ \mathbf{u} = \begin{bmatrix} 1 & 0 & 1 & 0 \end{bmatrix}^\top $ is a basic feasible solution or equivalently a vertex of $P$. This means that $A\mathbf{u} = \mathbf{b}$, and for the list of basic indices $ \mathbf{\beta} = \begin{pmatrix} 1 & 3 \end{pmatrix} $, the basis matrix
\begin{equation} B = \begin{bmatrix} a_{\beta_1} & a_{\beta_2} \end{bmatrix} = \begin{bmatrix} a_{1} & a_{3} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 2 & 0 \end{bmatrix} \end{equation}
is invertible and for every $i \notin \beta$ we have $u_i = 0$. Define the nonbasic list of indices as $ \mathbf{\nu} = \begin{pmatrix} 2 & 4 \end{pmatrix} $ and let the nonbasic matrix be
\begin{equation} N = \begin{bmatrix} a_{\nu_1} & a_{\nu_2} \end{bmatrix} = \begin{bmatrix} a_{2} & a_{4} \end{bmatrix} = \begin{bmatrix} 2 & 2 \\ 1 & 1 \end{bmatrix}. \end{equation}
Introducing the following basic and nonbasic variables as
\begin{align} \mathbf{x}_\beta = \begin{bmatrix} x_1 & x_3 \end{bmatrix}^\top, \qquad \mathbf{x}_\nu = \begin{bmatrix} x_2 & x_4 \end{bmatrix}^\top, \end{align}
we can rewrite the $A\mathbf{x}=\mathbf{b}$ as $B\mathbf{x}_\beta + N \mathbf{x}_\nu=\mathbf{b}$ and solving for $\mathbf{x}_\beta$ results in
\begin{equation} \mathbf{x}_\beta = B^{-1}\mathbf{b} - B^{-1}N\mathbf{x}_\nu = \mathbf{u}_\beta - B^{-1}N\mathbf{x}_\nu, \end{equation}
which in component form reads as
\begin{align} x_1 &= 1 - \frac{1}{2} x_2 + \frac{1}{2} x_4, \\ x_3 &= 1 + \frac{5}{2} x_2 - \frac{5}{2} x_4. \end{align}
Now, we can rewrite $P$ by eliminating the basic variables from its representation as below
\begin{align} P = \Big\{ &\mathbf{x} = \begin{bmatrix} 1 - \frac{1}{2} x_2 + \frac{1}{2} x_4, & x_2, & 1 + \frac{5}{2} x_2 - \frac{5}{2} x_4, & x_4 \end{bmatrix}^\top \in \mathbb{R}^4 \Big| \\ & 1 - \frac{1}{2} x_2 + \frac{1}{2} x_4 \ge 0, \\ & 1 + \frac{5}{2} x_2 - \frac{5}{2} x_4 \ge 0, \\ & x_2 \ge 0, \, x_4 \ge 0 \Big\}. \end{align}
Next, to make a visualization of $P$, it is suggesting to visualize the following
\begin{align} Q = \Big\{ &\mathbf{x} = \begin{bmatrix} x_2, & x_4 \end{bmatrix}^\top \in \mathbb{R}^2 \Big| \\ & x_2 - x_4 \le 2, \\[0.3em] -& x_2 + x_4 \le \frac{2}{5}, \\ & x_2 \ge 0, \, x_4 \ge 0 \Big\}. \end{align}
To make some mathematical justification for this, we can define an bijective affine function $f:Q\to P$ with $Q\subset\mathbb{R}^2$ such that $f(Q) = P \subset \mathbb{R}^4$ and in particular
\begin{align} f(\mathbf{x}_\nu) = f\big( \begin{bmatrix} x_2, & x_4 \end{bmatrix}^\top \big) &= \begin{bmatrix} 1 - \frac{1}{2} x_2 + \frac{1}{2} x_4, & x_2, & 1 + \frac{5}{2} x_2 - \frac{5}{2} x_4, & x_4 \end{bmatrix}^\top \\ &= \begin{bmatrix} 1 & 0 & 1 & 0 \end{bmatrix}^\top + \begin{bmatrix} - \frac{1}{2} x_2 + \frac{1}{2} x_4, & x_2, & \frac{5}{2} x_2 - \frac{5}{2} x_4, & x_4 \end{bmatrix}^\top \\ &= \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} + \begin{bmatrix} -\frac{1}{2} & \frac{1}{2} \\ 1 & 0 \\ \frac{5}{2} & -\frac{5}{2} \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x_2 \\ x_4 \end{bmatrix} \\ &= \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} + \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{1}{2} & -\frac{1}{2} \\ -\frac{5}{2} & \frac{5}{2} \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x_2 \\ x_4 \end{bmatrix} \\ &= \mathbf{u} + \Pi \begin{bmatrix} -B^{-1} N \\ I_2 \end{bmatrix} \mathbf{x}_\nu \end{align}
Due to the existence of such an bijective affine function, we prefer to visualize $Q$ rather than having no picture of $P$ in mind! It is noteworthy to mention that lines and parallelism are persevered under affine transformations. Furthermore, since both $P$ and $Q$ are convex, it can be shown that there is a one-to-one correspondence between their vertices under $f:Q\to P$. In conclusion, $Q$ seems to be a good candidate for visualizing $P$.
Remark. This is indeed similar to what we do in the implicit function theorem.
Answer 2. Yes, the projection of a polyhedron is a polyhedron. One approach to prove this is by Fourier-Motzkin elimination. See Corollary 2.5 of Chapter 2 of this book.