# Show that the face of a face of a polyhedron $\mathcal P\subset\mathbb R^n$ is still a face of $\mathcal P$

Let $$\mathcal{P}$$ be a polyhedron in $$\mathbb{R}^n$$. I want to show that the face $$\mathcal{F}'$$ of a face $$\mathcal{F}$$ of $$\mathcal{P}$$ is still a face of $$\mathcal{P}$$.

There are various proofs of this fact for polytopes. For example in Ziegler's "Lectures on Polytopes" proposition $$2.3$$. I want to show that the same holds for polyhedra. My idea is that I can take a large enough polytope $$\mathcal{V}$$ that intersects both $$\mathcal{F}$$ and $$\mathcal{F}'$$ in some way. At this point I find that $$\mathcal{V} \cap \mathcal{F}'$$ is a face of $$\mathcal{V} \cap \mathcal{P}$$, since the latter is a polytope (by the so-called main theorem in Ziegeler's textbook). From this I would want to conclude that $$\mathcal{F}'$$ is a face of $$\mathcal{P}$$. Maybe this is a typical problem: if the proof is pointed out somewhere reference would be fine for me as an answer.

1. A polyhedron is the intersection of a finite number of closed halfspaces. This is a convex set.

2. A polytope is the convex hull of e finite number of points.

3. A face $$\mathcal{F}$$ of a convex set $$\mathcal{P}$$ is any set defined by $$\mathcal{F}=\mathcal{P}\cap\{ \mathbf{x}: \mathbf{a}\cdot \mathbf{x} - c = 0\},$$ where $$\mathbf{a}\cdot \mathbf{x} - c \ge 0$$ is an inequality valid for all $$\mathbf{x} \in \mathcal{P}$$

• This sounds like an elementary problem: could you expand your definitions of polytope, polyhedron and face so people without access to Ziegler can understand the exact question?
– HTFB
Commented Sep 23, 2015 at 13:07
• I added definitions. I have always the feeling that problems in convex geometry are trivial, but than again they might be not. I have found myself a proof of this fact. I will post it, since no other proof has appeared. Commented Sep 24, 2015 at 18:52
• Thanks. Other definitions of, e.g., polyhedra were certainly available. "Elementary" doesn't mean "trivial", not by a long chalk!
– HTFB
Commented Sep 25, 2015 at 13:48

Let us suppose that $\mathcal{F}$ is defined by $\mathcal{P} \cap \{ \mathbf{x}: f_1(\mathbf{x}) := \mathbf{a}\cdot \mathbf{x} - c = 0 \}$, where $f_1(\mathbf{x}) \geq 0$ is a valid inequality for $\mathcal{P}$. Let us take any face $\mathcal{F}' \subset \mathcal{F},$ given by $\mathcal{F} \cap \{ \mathbf{x}: f_2(\mathbf{x}):=\mathbf{b}\cdot \mathbf{x} - d = 0 \}$, where $f_2(x) \geq 0$ is a valid inequality for $\mathcal{F}$. From the main theorem about polyhedra we know that $\mathcal{P} = conv(\mathbf{Q}) + cone(\mathbf{V})$. Here we view matrices as sets of column vectors. Now we observe that if $f_1(\mathbf{x}) \geq 0$ is valid for $\mathcal{P}$ then $f_1(\mathbf{x}) = \mathbf{a} \cdot \mathbf{q}_i - c \geq 0$ and $\mathbf{a} \cdot \mathbf{v}_j \geq 0$. This last inequality must be valid because if there exists $j$ with $\mathbf{a} \cdot \mathbf{v}_j < 0,$ we could choose $R > 0$ big enough for $f_1(\mathbf{q_i + R \mathbf{v}_j}) < 0$ and this contradicts the fact that $f_1(\mathbf{x})$ is a valid inequality for $\mathcal{P}$. Now we can choose $\lambda$ big enough such that $\lambda f_1(\mathbf{x}) + f_2 (\mathbf{x}) \geq 0$ is valid for all $\mathbf{q}_i \not \in \mathcal{F}$. Furhter more, at the cost of augmenting again $\lambda$, we find $\lambda \mathbf{a} \cdot \mathbf{v}_j + \mathbf{b} \cdot \mathbf{v}_j \geq 0,$ for all $j$ for which $\mathbf{a} \cdot \mathbf{v}_j \neq 0$. Now we observe that $\mathcal{F}$ is a polyhedron aswell. So we find that $\mathcal{F} = conv(\mathbf{R}) + cone(\mathbf{W})$. if, for some $j,$ $\mathbf{a} \cdot \mathbf{v}_j = 0,$ we find that $\mathbf{v}_j \in cone(W)$. From this follows (because $f_2(\mathbf{x})$ is a valid inequality for $\mathcal{F}$) that $\mathbf{b} \cdot \mathbf{v}_j \geq 0$ and hence that $\lambda \mathbf{a} \cdot \mathbf{v}_j + \mathbf{b} \cdot \mathbf{v}_j \geq 0$ is immediatley respected (because it is respected by both terms). Now we can conclude the proof. Let us take $\mathbf{x} \in \mathcal{P}$. We know that $\mathbf{x} = \sum_i \mu_i \mathbf{q}_i + \sum_j \nu_j \mathbf{v}_j,$ hence $$\lambda f_1(\mathbf{x}) + f_2 (\mathbf{x}) =$$ $$= \sum_i \mu_i \left( \lambda \mathbf{a} \cdot \mathbf{q}_i + \mathbf{b} \cdot \mathbf{q}_i- \lambda c - d \right) + \sum_j \nu_j \left( \lambda \mathbf{a} \cdot \mathbf{v}_j + \mathbf{b} \mathbf{v}_j\right).$$ From what we have seen we can conclude that the terms in the right sum are positive, and so also those in the left sum. From this follows that $\lambda f_1(\mathbf{x}) + f_2 (\mathbf{x}) \geq 0$ is an inequality valid for the whole polyhedron $\mathcal{P}$.