Rational and integral k-regular matrices
Rational and integral k-regular matrices
复制标题
有理积分 k-正则矩阵
DOI：
10.1016/s0012-365x(03)00095-5
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
B. Kotnyek
中科院分区：
文献类型：
--
作者：
Gautam M. Appa;B. Kotnyek
在本文中，我们研究了两种可能的推广全幺模，即，全k-模性和k-正则性。全k-模性将整矩阵的子行列式的允许值扩展到k次幂，而k-正则性则对有理矩阵的非奇异子矩阵的逆矩阵提出了要求。证明了全幺模矩阵关于整多面体的优越性质可以推广到有理k-正则矩阵，即证明了矩阵A是k-正则的当且仅当多面体P（A，B）={x：x 0，Ax B}对所有分量有公因子k的整向量B是整的.进一步证明了整矩阵A的k-正则性等价于对任意整向量B，P（A，B）的所有秩1 Chvátal-Gomory割都被mod-k割支配.给出了全k-模矩阵和k-正则矩阵的一些结果，并给出了1-正则矩阵和2-正则矩阵的非平凡例子。特别是，我们定义了binet矩阵，一个概括的网络矩阵的双向图。
In this paper we examine two possible generalisations of total unimodularity, viz., total k-modularity and k-regularity. Total k-modularity extends the permitted values for the subdeterminants of an integral matrix to the powers of k, while k-regularity sets requirements on the inverses of non-singular submatrices of a rational matrix. It is shown that the advantageous properties of totally unimodular matrices with respect to integral polyhedra can be carried over to rational k-regular matrices, namely we prove that a matrix A is k-regular if and only if the polyhedron P(A,b)={x:x⩾0, Ax⩽b} is integral for all integral vectors b the components of which have a common divisor k. Furthermore, we show that the k-regularity of an integral matrix A is equivalent to the fact that for any integral vector b all the rank-1 Chvátal-Gomory cuts for P(A,b) are dominated by mod-k cuts. We present some results on totally k-modular and k-regular matrices, as well as give non-trivial examples of 1- and 2-regular matrices. In particular, we define binet matrices, a generalisation of network matrices for bidirected graphs.