4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – stewbasic Aug 29 '16 at 23:59
  • $\begingroup$ 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. $\endgroup$ – stewbasic Aug 30 '16 at 0:27
  • $\begingroup$ @LeonMeier You are right, that case needs to be handled separately; I made a couple more edits. $\endgroup$ – stewbasic Sep 12 '16 at 0:03
  • $\begingroup$ I added some more detail for each of these points. $\endgroup$ – stewbasic Sep 12 '16 at 3:12
  • $\begingroup$ 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 $\endgroup$ – stewbasic Sep 13 '16 at 22:30

Your Answer

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