Proof of Hoffman & Kruskal's theorem on Unimodularity and Integrality.

393 Views Asked by At

I'm reading the following proof.

Thm. (Unimodularity and Integrality, Hoffman & Kruskal [1956]):
Let $A \in \mathbb{R}^{m \times n}, \operatorname{rank} A=n .$ The following are equivalent:
a) $A$ is unimodular
b) $\operatorname{vert}(P(A, b)) \subseteq \mathbb{Z}^{n}, \forall b \in \mathbb{Z}^{n}$, where $P(A,b)$ is the polyhedron associated with the system $Ax \leq b$.
c) $A_{I.}^{-1} \in \mathbb{Z}^{n \times n}, \forall$ regular $A_{I} . \in \mathbb{R}^{n \times n}$ (The notation $A_{I.}$ denotes the submatrix of $A$, comprised of the rows $I$ of $A$, for a set of indices $I$.)

Proof:
b) $\Rightarrow$ c):
Let $A_{I}$. be regular, w.l.o.g. $I=[n], J=[m] \backslash[n]$.
Let $x^{i}:=\left(A_{I}^{-1}\right)_{\cdot i}$ be the $i$-th column of $A_{I}^{-1}$, and $b^{i}:=A x^{i}=\left(\begin{array}{c} e_{i} \\ A_{J} \cdot x^{i} \end{array}\right), i \in I \\$
$\Rightarrow x^{i} \in \operatorname{vert} P(A, b), i \in I \\ \Rightarrow x^{i} \text { integer, } i \in I \\ \Rightarrow A_{I.}^{-1} \text{ integer. }$

I assume in "$x^{i} \in \operatorname{vert} P(A, b), i \in I$", the author means the $b^i$ as defined in the previously, instead of just some general $b$? But if so, how do we make sure that the lower entries of $b^i$ are also integer, so that we can apply the second condition in the theorem?