dimension of proper face of a polyhedron

Question

Let $\mathcal{P} = \mathcal{P}(A,b) = \{x \in \mathbb{R}^{n} \mid Ax \leq b\}$ be a polyhedron with $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^{m}$. Let $\mathcal{F} \subset \mathcal{P}$ be a proper face of $\mathcal{P}$, i.e. $\mathcal{F} \neq \mathcal{P}$. How can I show that $\dim(\mathcal{F}) \leq \dim(\mathcal{P}) - 1$?

Answer 1

Subsume $\mathcal{F}$ is a true facet of $\mathcal{P}$ and $\,dim(\mathcal{P})=n\,$ is full dimensional, then $span(\mathcal{F})$ is described by a single row of the matrix equation $\,Ax=b$. In fact $\mathcal{F}$ is described by that very row plane (for support) and by the intersections of all the other row inequalities with that plane (for its boundaries), i.e. $\,dim(\mathcal{F})=n-1=dim(\mathcal{P})-1$, as required.

This is the main ingredient here. The remainder then is simply to fiddle around with all the here omitted subdimensional cases.

--- rk