Proving that a polyhedron has integer vertices

Question

Prove that the polyhedron $$ P = \left\{ (x_1, \ldots , x_m, y) \in \mathbb R_{+}^{m+1}: y \leq 1,x_i \leq y \text{ for } i = 1,\dots, m \right\} $$ has integer vertices.

It seems obvious to me but don't know how to prove it. Any thoughts ?

Answer 1

We would like to prove that the polyhedron

$$\mathcal P := \bigg\{ \begin{bmatrix} \mathrm x\\ y\end{bmatrix} \in \mathbb R^{n+1} : \begin{bmatrix} \mathrm x\\ y\end{bmatrix} \geq \begin{bmatrix} 0_n\\ 0\end{bmatrix}, \begin{bmatrix} \mathrm I_n & -1_n\\ 0_n^{\top} & 1\end{bmatrix} \begin{bmatrix} \mathrm x\\ y\end{bmatrix} \leq \begin{bmatrix} 0_n\\ 1\end{bmatrix} \bigg\}$$

is integral, i.e., it has integer vertices. Since the matrix is an upper triangular Frobenius matrix,

$$\begin{bmatrix} \mathrm I_n & -1_n\\ 0_n^{\top} & 1\end{bmatrix}^{-1} = \begin{bmatrix} \mathrm I_n & 1_n\\ 0_n^{\top} & 1\end{bmatrix}$$

which is also an integer matrix. Thus, the matrix is unimodular. Since it is also nonnegative,

$$\begin{bmatrix} \mathrm x\\ y\end{bmatrix} \leq \begin{bmatrix} \mathrm I_n & 1_n\\ 0_n^{\top} & 1\end{bmatrix} \begin{bmatrix} 0_n\\ 1\end{bmatrix} = \begin{bmatrix} 1_n\\ 1\end{bmatrix}$$

which allows us to conclude that $\mathcal P \subset [0,1]^{n+1}$, i.e., it is bounded. From Schrijver's book:

---

---

Thus, $\mathcal P$ is integral if and only if the $(n+1) \times (n+1)$ matrix

$$\begin{bmatrix} \mathrm I_n & -1_n\\ 0_n^{\top} & 1\end{bmatrix}$$

is totally unimodular. It is easy to prove by exhaustion that the matrix is indeed totally unimodular when $n \in \{1,2\}$. If we can prove that the matrix is totally unimodular also for $n \geq 3$, we then prove that $\mathcal P$ is integral. Chapters 19-21 of Schrijver's book should help.

---

• Alexander Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, July 1998.