Rational and integral \(k\)-regular matrices.
type: Item
instance of: scholarly article
title: Rational and integral \(k\)-regular matrices.
zbMATH Open document ID: 1043.15011
DOI: 10.1016/S0012-365X(03)00095-5
author: Balázs Kotnyek
author: G. Appa
published in: Discrete Mathematics
publication date: 2004-02-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 2035861
zbMATH Keywords: total unimodularity
zbMATH Keywords: integral polyhedron
zbMATH Keywords: network matrices
zbMATH Keywords: Chvátal-Gomory cuts
zbMATH Keywords: matrices of integers
zbMATH Keywords: rational matrix
zbMATH Keywords: integer programming
zbMATH Keywords: integral matrices
zbMATH Keywords: Binet matrices
MaRDI profile type: Publication
cites work: \(k\)-integrality, an extension of total unimodularity
cites work: Characterization of Totally Unimodular Matrices
cites work: Modules unimodulaires
cites work: \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
cites work: On the separation of maximally violated mod-\(k\) cuts
cites work: Total Unimodularity of Matrices
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Q5675543
cites work: Matching, Euler tours and the Chinese postman
cites work: Matrices with the Edmonds-Johnson property
cites work: Outline of an algorithm for integer solutions to linear programs
cites work: Q3236253
cites work: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
cites work: Q3236252
cites work: Subspaces with well-scaled frames
cites work: Q3818127
cites work: Integral Extreme Points
cites work: A characterisation of the matroids representable over GF(3) and the rationals
description: scientific article; zbMATH DE number 2035861