Prove that an edge of a polyhedron is a line segment

Preliminaries

Let us define $\mathbb{N}_n=[1,n]\cap\mathbb{N}^+$ for all $n\in\mathbb{N}^+$. $\$ A polyhedron is an intersection of halfspaces, i.e., a set of the form $\{x\in\mathbb{Q}^n\mid Ax\le b\}$ for some matrix $A\in\mathbb{Q}^{m\times n}$ and column vector $b\in\mathbb{Q}^m$. $\$ Let us say that a face of a polyhedron $P$ is a set of points of the form $\{x{\in}P\mid a^{\top}x=\beta\}$ for some $(a,\beta)\in\mathbb{Q}^n\times\mathbb{Q}$ such that $\forall\,y{\in}P\colon a^{\top}y\le \beta$. $\$ A vertex of a polyhedron $P$ is a point $x$ such that $\{x\}$ is a face of $P$. $\$ An edge is defined as a face of dimension 1. $\$ Hereby, the dimension of a face is defined as the dimension of its affine hull. $\$ Hereby, the dimension of an affine space $A$ is defined as $\dim A = \begin{cases}-1,&\text{if}\ A=\emptyset\,,\\\dim (A-A),&\text{if}\ A\neq\emptyset\,.\end{cases}$

A polytope is a bounded polyhedron. $\$ A line segment is a convex hull of a pair of points.

We would like to show:

Theorem

Every edge of a polytope $P\subseteq\mathbb{Q}^n$ is a line segment between two vertices of $P$. $\square$

Literature references and/or direct proofs are welcome.

Define a polyhedral cone to be a set of the form $\{x\in\mathbb Q^n\mid Ax\geq0\}$ for some matrix $A\in\mathbb Q^{m\times n}$. Note that any polyhedral cone $C$ is nonempty and closed under addition and multiplication by nonnegative scalars. Thus $C\cap(-C)$ is a vector subspace of $\mathbb Q^n$.

We have the following even over $\mathbb Q$ (without the second conclusion it is a consequence of Farkas' lemma):

Lemma 1: If $C\subsetneq\mathbb Q^n$ is a polyhedral cone then there exists nonzero $y\in\mathbb Q^n$ such that $y^Tx\geq0$ for $x\in C$ and $y^Tx>0$ for $x\in C\setminus(-C)$.

Indeed let $y$ be the sum of rows of $A$. We have $y^Tx\geq0$, and if equality holds then $x$ is orthogonal to each row of $A$, implying $x\in C\cap(-C)$. That is, $y^Tx>0$ for $x\in C\setminus(-C)$. This proves the lemma unless $y=0$. But in that case $C=-C$ is a proper subspace of $\mathbb Q^n$, so we can replace $y$ by any nonzero vector orthogonal to $C$.

I will use the following definitions as in my answer to your other question. For $x\in P$ let $$V_x^+=\{y\in\mathbb Q^n\mid x+ky\in P\text{ for some }k>0\}$$ and $V_x=V_x^+\cap(-V_x^+)$.

Lemma 2: $V_x^+$ is a polyhedral cone.

Let $I$ be the set of indices on which $Ax$ coincides with $b$. Let $A_1$ denote the submatrix of $A$ consisting of rows whose index is in $I$, and $A_2$ the other rows. Define $b_1,b_2$ similarly. Then $A_1x=b_1$, $A_2x<b_2$ and $$P=\{x\in\mathbb Q^n\mid A_1x\leq b_1\text{ and }A_2x\leq b_2\}.$$ If $y\in V_x^+$ then for some $k>0$ we have $$b_1\geq A_1(x+ky)=b_1+kA_1y,$$ so $(-A_1)y\geq0$. Conversely suppose $(-A_1)y\geq0$. Since $A_2x<b_2$, there exists $k>0$ such that $A_2x+kA_2y<b_2$. Also $A_1(x+ky)\leq A_1x=b_1$. Thus $x+ky\in P$, so $y\in V_x^+$. Hence $$V_x^+=\{y\in\mathbb Q^n\mid(-A_1)y\geq0\}$$ is a polyhedral cone.

If $F$ is a face of $P$ and $x\in F$, it can be shown that $V_x\subseteq\mathrm{span}(F-F)$. Conversely we have the following:

Lemma 3: If $x\in P$ and $V_x\neq\mathbb Q^n$ then there is a face $F$ with $x\in F$ and $V_x=\mathrm{span}(F-F)$.

Note that $V_x^+\neq\mathbb Q^n$ since $V_x\neq\mathbb Q^n$. By Lemmas 1 and 2, there exists nonzero $z\in\mathbb Q^n$ such that $z^Ty\geq0$ for $y\in V_x^+$ and $z^Ty>0$ for $y\in V_x^+\setminus V_x$. If $x_1\in P$ then $x_1-x\in V_x^+$, so $z^T(x_1-x)\geq0$. We therefore have a face $$F=\{x_1\in P\mid z^Tx_1=z^Tx\}$$ of $P$. Clearly $x\in F$, so $V_x\subseteq\mathrm{span}(F-F)$. If $x_1\in F$ then $x_1-x\in V_x^+$ and $z^T(x_1-x)=0$, so $x_1-x\in V_x$. Hence if $x_1,x_2\in F$ then $$x_1-x_2=(x_1-x)-(x_2-x)\in V_x,$$ so $\mathrm{span}(F-F)\subseteq V_x$ as required.

One more simple observation: If $F$ is a face of $P$ with affine hull $G$ then $F=P\cap G$. Indeed $F=P\cap H$ for some hyperplane $H$. We have $G\subseteq H$, so $$F\subseteq P\cap G\subseteq P\cap H=F.$$

Now suppose $F$ is an edge of $P$ with affine hull $G$. Pick $x\in F$ and $\{y\}$ a basis for $G-G$, so $$G=\{x+ty\mid t\in\mathbb Q\}.$$ Thus $$F=P\cap G=\{x+ty\mid tAy\leq b-Ax\}.$$ Let $T=\{t\in\mathbb Q\mid tAy\leq b-Ax\}$. Since $P$ is bounded, $T=[p,q]\cap\mathbb Q$ where $$p=\max\{(b-Ax)_i/(Ay)_i\mid (Ay)_i<0\}\in\mathbb Q,$$ $$q=\min\{(b-Ax)_i/(Ay)_i\mid (Ay)_i>0\}\in\mathbb Q.$$ Thus $F$ is the segment between $x_1=x+py$ and $x_2=x+qy$. If $k>0$ then $q+k\not\in T$, so $$x_2+ky=x+(q+k)y\notin F.$$ Hence $y\notin V_{x_2}$. But $V_{x_2}\subseteq\mathrm{span}\{y\}$ since $x_2\in F$. Hence $V_{x_2}=\{0\}$, so $x_2$ lies in a face of dimension $0$ by Lemma 3. That is, $x_2$ is a vertex, and similarly for $x_1$.

• @LeonMeier That is just what I found I needed later in the answer. Maybe I shouldn't call it a version of Farkas' lemma, though without the part about $C\setminus(-C)$ it is a simple consequence of Farkas' lemma. – stewbasic Aug 29 '16 at 23:59
• Yes that one. See "Moreover (in finite dimensions), any convex cone C that is not the whole space V must be contained in some closed half-space H of V; this is a special case of Farkas' lemma." on en.wikipedia.org/wiki/Convex_cone. But the statement I needed was slightly more specific, so it's not really Farkas' lemma. I edited my answer accordingly. – stewbasic Aug 30 '16 at 0:27
• @LeonMeier You are right, that case needs to be handled separately; I made a couple more edits. – stewbasic Sep 12 '16 at 0:03
• I added some more detail for each of these points. – stewbasic Sep 12 '16 at 3:12
• I don't know whether they have established names. The setup applies to higher dimensional faces too, so maybe for just edges there could be some simplification. For acknowledgement I think you can just link to math.stackexchange.com/questions/1904423 – stewbasic Sep 13 '16 at 22:30