Rational and integral \(k\)-regular matrices. (Q1420582): Difference between revisions

Two possible generalisations of total unimodularity, i. e. total \(k\)-modularity and \(k\)-regularity, are investigated. A matrix is called totally \(k\)-modular if for all its square submatrices \(R\), \(\det R \in \{0, \pm k^r\), \(r\) is positive integer\} and a rational matrix is called \(k\)-regular if for each of its non-singular square submatrices \(R\), \(kR^{-1}\) is integral. It is shown that although both total \(k\)-modularity and \(k\)-regularity are legitimate generalisations of total unimodularity, \(k\)-regularity is the one which maintains the properties that make total modularity a key concept in integer programming. It is proved that a rational matrix \(A\) is \(k\)-regular if and only if the polyhedron \(P(A,b)= \{x: x \geq 0, Ax \leq b \}\) is integral for any integral vector \(b\) the components of which have a common divisor \(k\). This is a stronger result than the one in a previous work [\textit{G. M. Appa}, Oper. Res. Lett. 13, 159--163 (1993; Zbl 0792.90049)], where only integral matrices \(A\) were considered. It is also shown that in case of an integral matrix \(A\), half-integral Chvátal-Gomory (CG) cuts for \(P(A,b)\) imply all other rank-1 CG-cuts for any integral \(b\) if and only if \(A\) is \(2\)-regular. Some properties of \(k\)-regular matrices that hold only if it is assumed that the \(k\)-regular matrix is integral are given. In a special case of \(2\)-regular matrices, namely for Binet matrices, it is shown that some of these results remain valid. A non-trivial class of non-integral \(1\)-regular matrices is also introduced.