Box-total dual integrality, box-integrality, and equimodular matrices (Q2039243)

A polyhedron \(P = \{x: Ax\le b\}\) of \(\mathbb{R}^n\) is integer if each of its faces contains an integer point and box-integer if \(P\cap\{l\le x\le u\}\) is integer for all \(l,u\in\mathbb{Z}^n\). We say that \(P\) is principally box-integer if \(kP=\{x: Ax\le kb\}\) is box-integer for all \(k\in\mathbb{Z}_{>0}\) such that \(k\)P is integer. A rational \(r\times n\) matrix is equimodular if it has full row rank and its nonzero \(r\times r\) determinants all have the same absolute value. A linear system given by \(P\) is totally dual integral (TDI) if the minimum in the linear programming duality equation \(\max\{w^\top x: Ax\le b\} = \min\{b^\top y: A^\top y = w,\, y\ge 0\}\) has an integer optimal solution for all integer vectors \(w\) for which the optimum is finite. The results of this paper provide a framework within which the notions of equimodularity, principal box-integrality, and box-TDIness are all connected by proving that the following statements are all equivalent: \begin{itemize} \item The polyhedron \(P\) is box-TDI. \item The polyhedron \(P\) is principally box-integer. \item Every face-defining matrix of \(P\) is equimodular. \item Every face of \(P\) has an equimodular face-defining matrix. \item Every face of \(P\) has a totally unimodular face-defining matrix. \item For every face \(F\) of \(P\), \(\mathrm{lin}(F)\) has a totally unimodular basis. \end{itemize}