Let $A$ be an $m \times n$ integer matrix. Prove that $A$ is totally unimodular if and only if for every $b \in \mathbb{Z}^n, P=\{x\in \mathbb{R}^n : Ax \leq b, x\geq 0\}$ is integer.
Lemma 3.1. Let $A$ be a square, non-singular matrix with integral entries. Then the (unique) solution of $Ax=b$ is integral for all integral $b$ iff $|detA|=1$.
Proof)$(\Leftarrow)$ By the Cramer’s rule, $|x_i|= |det A_i|/|det A| = |detA_i|$ since $|detA|=1$.
Here $A_i$ is the matrix formed by replacing i-th column of $A$ with $b$.
Since $A$ and $b$ have all integral entries, the solution of $Ax=b$ has all integral entries.
$(\Rightarrow)$ $Ax=e_i$ is integral for all $i$, where $e_i$ is the i-th unit vector.
$A^{-1}$ is a solution of $Ax=[e_1 e_2…e_n]$ if $A$ is $n \times n $ square matrix.
Therefore $A^{-1}$ has all integral entries and $det(A^{-1}) \in \mathbb{Z}$.
Since $detA\in \mathbb{Z}$ and $det(I)=det(A)det(A^{-1})=1$, $|det(A^{-1})|=1$
Definition 3.2. A matrix $A$ of full row rank is called rank unimodular if, for every basis $B$ of columns $|det(A_B)|=1$. Here, $A_S$ is a submatrix of $A$ whose columns are exactly $S$.
Lemma 3.3. Let $A$ be an $m\times n$ matrix of full row rank. Then for any subset $S$ of $m$ columns $det(A_S) \in \{-1,0,1\}$ iff $A$ is rank unimodular.
Proof) ($\Leftarrow$) Let $B$ be the basis of $col(A)$ consisting of columns of $A$.
Since $A_B$ has full rank $m$, $det A_B\neq 0$, $|detA_B|=1$.
$A$ is rank unimodular.
($\Rightarrow$) Let $S$ be any subset of $m$ columns of $A$.
$rank(A_S) \leq m$.
If $rank(A_S)=m$, then $S$ is a basis therefore $|detA_S|=1$.
If $rank(A_S) <m$, then $S$ is a dependent therefore $detA_S=0$.
I present Lemma 3.4 without proof.
Lemma 3.4. Fix a matrix $A$ of full row rank. The polytope $\{x: Ax =b , x \geq 0 \}$ is integral for all integral $b$ iff $A$ is rank unimodular.
Lemma 3.5. The matrix $A$ is totally unimodular iff $[A|I]$ is rank unimodular.
Proof) ($\Rightarrow$) Suppose the $m \times n$ matrix $A$ is totally unimodular.
$[A|I]$ has full row rank.
Let $S$ be a subset of $m$ columns of $A$.
If $S$ is part of $A$, then $[A|I]$ is a submatrix of $A$.
So $det[A|I]_S \in \{-1,0,1\}$.
If $S$ contains part of $I$, $det[A|I]_S=detA^\prime$ for some a submatrix $A^\prime$ of $A$.
Since $A$ is totally unimodular $det[A|I]_S \in \{-1,0,1\}$.
By Lemma 3.3, $[A|I]$ is rank unimodular.
($\Leftarrow$) Suppose $[A|I]$ is rank unimodular.
Let $A^\prime$ be a square submatrix of $A$.
Collect $m$ columns $S$ of $[A|I]$ such that $det(A^\prime)=det([A|I]_S)$.
Since $[A |I]$ is rank unimodular, $det(A^\prime)\in \{-1,0,1\}$.
Proof of main problem.
Consider the equivalent linear programming $[A |I][x^T |z^T]^T=b, x,z \geq 0 $. Since $A$ and $b$ have all integral entries, the solution of $Ax \leq b, x\geq 0$ is integral iff the solution of $[A |I][x^T\mid z^T]^T=b, x,z\geq 0$ is integral.
Trivially $[A|I]$ has full row rank.
By Lemma 3.4 and Lemma 3.5, $[A|I][x^T|z^T]^T = b, x,z\geq 0$ is integral iff $[A|I]$ is integral iff $A$ is totally unimodular.