How can I prove that all minimal faces have the same dimension?

Question

So, I want to prove that all minimal faces have the same dimension. I've been googling and reading random articles and books that all point towards some unexplained or assumed or otherwise foggy explanations; how can I derive the proof of this fact from the very basic properties of polyhedra and minimal faces?

Answer 1

For a matrix $M$, let $M_I$ denote the submatrix of $M$ obtained by taking rows of $M$ with indices in $I$.

Let $P=\{x\in\mathbb{R}^d\mid Ax\le b\}$, where $A\in\mathbb{R}^{n\times d}$, be a (full dimensional) polyhedron. Let $F$ be a minimal face of $P$, so there is some $I\subset [n]$ such that $F=\{x\in\mathbb{R}^d\mid A_Ix= b_I\}$. It suffices to show that $\text{rank}(A_I)=\text{rank}(A)$, since $\text{rank}(A_I)=\text{codim}(F)$. ($\text{rank}(A_I)\le \text{rank}(A)$ is clear.)

Suppose for contradiction that $\text{rank}(A_I)<\text{rank}(A)$. Then there is $j\in [n]\backslash I$ such that $A_j$ is linearly independent from the rows of $A_I$. Thus there is some $v\neq 0$ such that $A_I v=0$ and $A_j v>0$.

Fix $f\in F$ and consider $y=f+\lambda v$. Then: $$A_Iy=A_If+\lambda A_Iv=b_I+0=b_I$$ $$A_jy=A_jf+\lambda A_jv$$ Since $A_jv>0$, there is some sufficiently large $\lambda>0$ such that $A_jy>b_j$.

Let $f'\in F^\circ$ (relative interior of $F$) and let $c_\tau=\tau f'+(1-\tau)y$. Then by construction $$A_I c_\tau=\tau A_I f'+(1-\tau)A_Iy=\tau b_I+(1-\tau)b_I=b_I$$

Let $J=[n]\backslash I$. Then $A_J f'<b_J$ since we have equality only for $i\in I$ since $f'$ was an interior point of $F$. But $j\in J$ and $A_jy>b_j$, so there is some $\tau\in(0,1)$ such that $A_Jw_\tau\le b_J$, and there is some $j'\in J$ such that $A_{j'}c_\tau=b_{j'}$. But then $F'=\{x\in\mathbb{R}^n\mid A_{I\cup j'}x=b_{I\cup j'}\}$ is a face of $P$ strictly contained in $F$ (since $f'\notin F'$, but $f'\in F$), contradicting the minimality of $F$.