[proofplan] We first combine the inequalities $Ax \leq b$ and $x \geq 0$ into one integer system by adding the negated identity rows that encode nonnegativity. The key structural point is that total unimodularity is preserved under adjoining identity rows and multiplying rows by $-1$, so every nonsingular square basis matrix selected from active constraints has determinant $\pm 1$. At a vertex, the active constraints contain $n$ linearly independent rows, and the corresponding integer square system has a unimodular coefficient matrix. [Cramer's rule](/theorems/3305) then forces every coordinate of the vertex to be an integer. [/proofplan] [step:Encode the nonnegativity constraints as rows of one totally unimodular matrix] Let $I_n \in \mathbb{Z}^{n \times n}$ denote the identity matrix. Define $M \in \mathbb{Z}^{(m+n) \times n}$ to be the matrix whose first $m$ rows are the rows of $A$ and whose last $n$ rows are the corresponding rows of $-I_n$. Define $h \in \mathbb{Z}^{m+n}$ by setting $h_r=b_r$ for $r \in \{1,\dots,m\}$ and $h_{m+i}=0$ for $i \in \{1,\dots,n\}$. Then \begin{align*} P = \{x \in \mathbb{R}^n : Mx \leq h\}. \end{align*} [claim:The matrix $M$ is totally unimodular] Every square submatrix of $M$ has determinant in $\{-1,0,1\}$. [/claim] [proof] First, stacking $I_n$ below $A$ preserves total unimodularity. Let $N \in \mathbb{Z}^{(m+n) \times n}$ denote the matrix whose first $m$ rows are the rows of $A$ and whose last $n$ rows are the corresponding rows of $I_n$. Let $C$ be a square submatrix of $N$. If $C$ uses no row from $I_n$, then $C$ is a square submatrix of $A$, so $\det C \in \{-1,0,1\}$ because $A$ is totally unimodular. Suppose $C$ uses at least one row from $I_n$. Choose such a row. In the selected columns of $C$, this row has either all entries equal to $0$, or exactly one entry equal to $1$ and all other entries equal to $0$. In the first case, $\det C=0$. In the second case, expanding $\det C$ along that row gives \begin{align*} \det C = \pm \det C', \end{align*} where $C'$ is the square submatrix obtained by deleting that identity row and the column in which the entry $1$ occurs. Repeating this expansion for every selected identity row reduces $\det C$ either to $0$ or to $\pm \det A'$, where $A'$ is a square submatrix of $A$. Since $A$ is totally unimodular, $\det A' \in \{-1,0,1\}$, hence $\det C \in \{-1,0,1\}$. Finally, $M$ is obtained from $N$ by multiplying the last $n$ rows by $-1$. Multiplying rows of a square submatrix by $-1$ changes its determinant only by a sign. Therefore every square submatrix of $M$ has determinant in $\{-1,0,1\}$, so $M$ is totally unimodular. [/proof] [guided] The nonnegativity condition $x_i \geq 0$ is more convenient in the same direction as the other inequalities. The inequality $x_i \geq 0$ is equivalent to $-x_i \leq 0$, so the full system is obtained by adding the rows of $-I_n$ below $A$. Thus, with $M \in \mathbb{Z}^{(m+n) \times n}$ defined as the matrix whose first $m$ rows are the rows of $A$ and whose last $n$ rows are the corresponding rows of $-I_n$, and with $h \in \mathbb{Z}^{m+n}$ defined by $h_r=b_r$ for $r \in \{1,\dots,m\}$ and $h_{m+i}=0$ for $i \in \{1,\dots,n\}$, the polyhedron is exactly \begin{align*} P = \{x \in \mathbb{R}^n : Mx \leq h\}. \end{align*} We must check that this new matrix is still totally unimodular. Let $N \in \mathbb{Z}^{(m+n) \times n}$ denote the matrix whose first $m$ rows are the rows of $A$ and whose last $n$ rows are the corresponding rows of $I_n$. Take any square submatrix $C$ of $N$. If all rows of $C$ come from $A$, then $C$ is a square submatrix of $A$, and its determinant is in $\{-1,0,1\}$ by total unimodularity of $A$. If $C$ contains a row from $I_n$, look at that row after restricting to the selected columns. Since a row of $I_n$ has a single $1$ in the full matrix and zeros elsewhere, its restricted row has either no nonzero entries or exactly one nonzero entry. If it has no nonzero entries, then $C$ has a zero row and $\det C=0$. If it has exactly one nonzero entry, expanding the determinant along that row gives \begin{align*} \det C = \pm \det C', \end{align*} where $C'$ is obtained by deleting that identity row and the column containing the entry $1$. This removes one identity row from the determinant calculation. Repeating the same argument for the remaining identity rows reduces the determinant either to $0$ or to $\pm \det A'$, where $A'$ is a square submatrix of $A$. Hence $\det C \in \{-1,0,1\}$. The actual matrix $M$ is obtained from $N$ by replacing the identity rows with their negatives. This only multiplies some selected rows by $-1$, and multiplying rows by $-1$ only changes the sign of the determinant. Therefore every square submatrix of $M$ still has determinant in $\{-1,0,1\}$. [/guided] [/step] [step:Choose a nonsingular active constraint system at an arbitrary vertex] Let $v \in P$ be a vertex. Define the active index set at $v$ by \begin{align*} J(v) := \{r \in \{1,\dots,m+n\} : M_{r\cdot}v = h_r\}, \end{align*} where $M_{r\cdot} \in \mathbb{Z}^{1 \times n}$ denotes the $r$-th row of $M$ and $h_r \in \mathbb{Z}$ denotes the $r$-th component of $h$. The rows $\{M_{r\cdot} : r \in J(v)\}$ span $\mathbb{R}^n$. Indeed, if their span were a proper subspace, there would exist a nonzero vector $w \in \mathbb{R}^n$ such that \begin{align*} M_{r\cdot}w = 0 \qquad \text{for every } r \in J(v). \end{align*} For every inactive index $r \notin J(v)$, we have $M_{r\cdot}v < h_r$, so for sufficiently small $\varepsilon > 0$ both $v+\varepsilon w$ and $v-\varepsilon w$ satisfy $M_{r\cdot}x \leq h_r$. The active constraints remain equalities because $M_{r\cdot}w=0$. Hence $v+\varepsilon w, v-\varepsilon w \in P$, and \begin{align*} v = \frac{1}{2}(v+\varepsilon w) + \frac{1}{2}(v-\varepsilon w), \end{align*} with $v+\varepsilon w \neq v-\varepsilon w$, contradicting that $v$ is a vertex. Therefore there exist indices $r_1,\dots,r_n \in J(v)$ such that the rows $M_{r_1\cdot},\dots,M_{r_n\cdot}$ are linearly independent. Define $B \in \mathbb{Z}^{n \times n}$ by declaring its $k$-th row to be $M_{r_k\cdot}$ for each $k \in \{1,\dots,n\}$. Define $d \in \mathbb{Z}^n$ by $d_k=h_{r_k}$ for each $k \in \{1,\dots,n\}$. Then $B$ is nonsingular and $Bv=d$. [/step] [step:Use total unimodularity and Cramer's rule to prove the vertex is integral] Since $B$ is a square submatrix of the totally unimodular matrix $M$, we have \begin{align*} \det B \in \{-1,0,1\}. \end{align*} Because $B$ is nonsingular, $\det B \neq 0$, hence \begin{align*} \det B \in \{-1,1\}. \end{align*} For each $i \in \{1,\dots,n\}$, let $B_i(d) \in \mathbb{Z}^{n \times n}$ denote the matrix obtained from $B$ by replacing its $i$-th column by $d$. Since $B$ and $d$ have integer entries, $\det B_i(d) \in \mathbb{Z}$. By [Cramer's Rule](/theorems/???) applied to the nonsingular system $Bx=d$, the $i$-th coordinate of $v$ is \begin{align*} v_i = \frac{\det B_i(d)}{\det B}. \end{align*} Since $\det B=\pm 1$, this gives $v_i \in \mathbb{Z}$ for every $i \in \{1,\dots,n\}$. Thus $v \in \mathbb{Z}^n$. [/step] [step:Conclude that the polyhedron is integral] The vertex $v \in P$ was arbitrary. We have proved that every vertex of $P$ lies in $\mathbb{Z}^n$. Therefore $P$ is integral in the stated sense. [/step]