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?

  • $\begingroup$ Minimal faces are points. $\endgroup$ – Mariano Suárez-Álvarez Oct 17 '16 at 2:25
  • 2
    $\begingroup$ @MarianoSuárez-Álvarez No, they are not. That is true only if we are talking about polytopes, which are bounded and can't have any unbounded minimal faces. However if we are talking about _un_bounded polyhedra, that is not generally true. Consider two intersecting planes. The polyhedron they define has one minimal face, and that face is a one-dimensional line, not a point. $\endgroup$ – Akiiino Oct 17 '16 at 2:28

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.