9512.net
甜梦文库
当前位置:首页 >> >>

On Padberg’s conjecture about almost totally unimodular matrices

On Padberg’s conjecture about almost totally unimodular matrices
G? erard Cornu? ejols? Luis F. Zuluaga? July 6, 2000

Abstract We consider Padberg’s conjecture about almost totally unimodular matrices proposed in 1988 in Operations Research Letters. We show that it is not correct as stated and give a modi?ed version of the conjecture.

1

Padberg’s Conjecture

A matrix C is totally unimodular if det(C ) ∈ {0, ±1} for every square submatrix C of C . In particular, every entry of a totally unimodular matrix is 0, ±1. A matrix C is almost totally unimodular if it is not totally unimodular but every proper submatrix of C is totally unimodular. Clearly, almost totally unimodular matrices are square and Gomory showed (cited in [1]) that if C ∈ {0, ±1}n×n is almost totally unimodular then det(C ) = ±2. A 0, ±1 matrix with exactly two nonzero entries in each row and column, such that no proper submatrix has this property is called a hole matrix. It is an unbalanced hole matrix if the sum of the entries is 2(mod 4). One can easily verify that unbalanced hole matrices are almost totally unimodular. A matrix R such that RP is totally unimodular for every totally unimodular matrix P is called a transformation that preserves total unimodularity. Padberg’s conjecture (p. 175 in [3]) on almost totally unimodular matrices is the following. Conjecture 1 Given any almost totally unimodular matrix A, there exists a transformation R that preserves total unimodularity such that RA is an unbalanced hole matrix.
? Graduate School of Industrial Administration, Carnegie Mellon University, Schenley Park Pittsburgh, PA 15213 (gc0v@andrew.cmu.edu). Research supported by NSF grant DMI9802773 and ONR grant N00014-97-1-0196 ? Graduate School of Industrial Administration, Carnegie Mellon University, Schenley Park Pittsburgh, PA 15213 (lzuluaga@andrew.cmu.edu). Research supported by the William Larimer Mellon Fellowship.

1

2

2

Counterexample and a New Conjecture

We ?rst show that Conjecture 1 is not correct as stated. Suppose A, R and an unbalanced hole matrix H satisfy Conjecture 1, i.e. RA = H . Since both A and H are square nonsingular matrices, then R is nonsingular. Also R is totally unimodular since R preserves total unimodularity. Now, R has at most one nonzero entry per row and column; as otherwise, if Rij = 0 and Rik = 0 for some row i and j = k , let P be the matrix containing only two nonzero entries Pj 1 = Rij and Pk1 = Rik . Then P is totally unimodular and [RP ]i1 = 2. So we can assume (w.l.o.g.) that R is a permutation matrix. It follows that RA is obtained from A by permuting its rows. Therefore any almost totally unimodular matrix A containing a row with more than two nonzero entries contradicts Conjecture 1. For example, take the following almost totally unimodular matrix [2] ? ? 1 1 0 0 0 ? 1 0 1 0 0 ? ? ? ? (1) A=? ? 1 1 1 1 0 ?? ? 1 1 0 1 1 ? 0 1 0 0 1 Now we state the following modi?ed conjecture. Conjecture 2 Given any almost totally unimodular matrix A, there exists a totally unimodular matrix R such that RA is an unbalanced hole matrix. For example, a totally unimodular matrix R for the almost totally unimodular matrix A in (1) is ? ? ? ? 1 0 0 0 0 1 1 0 0 0 ? ?1 1 0 0 0 ? ? 0 ?1 1 0 0 ? ? ? ? ? ? ? 0 1 1 0 ? R = ? ?1 0 1 0 0 ? where RA = ? ? 0 ?. ? ?1 0 0 1 0 ? ? 0 0 0 1 1 ? ?1 0 0 0 1 ?1 0 0 0 1 Another example where Conjecture 2 tion. ?? ? 1 1 1 ?1 0 0 ?1 0 ?? 1 0 ? 1 0 0 0 ? 1 0 ?? ? ? ? 0 0 0 1 0 ?1 ? ?? 1 1 ? ? ? 0 ?1 0 1 0 0 ?? ? 1 0 ? ? 1 0 ?1 0 0 0 ?? 1 0 1 0 0 1 0 ?1 1 0 holds is given by the following equa1 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 0 ? ? ?1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 ? ? ? ? ?, ? ? ?

? ? ? ? ? ? ?=? ? ? ? ? ? ?

where the almost totally unimodular matrix is taken from [2]. In the examples above we have transformed an almost totally unimodular matrix into an

3

unbalanced hole matrix of the form ? α1 α2 0 ? 0 α α 3 4 ? ? . . .. ? . ? . ? 0 ··· 0 α2n 0 · · ·

··· ··· .. . α2n?3 0

0 0 . . . α2n?2 α2n?1
2n

? ? ? ? ? ? ? (2)

where αi ∈ {+1, ?1} for i = 1, . . . , 2n and i=1 αi = 2(mod 4). It is worth noticing that for the almost totally unimodular matrix ? ? 1 1 0 0 0 0 0 0 ? 1 1 1 0 1 1 0 1 ? ? ? ? 1 0 0 1 1 1 0 0 ? ? ? ? 1 1 1 1 1 1 0 0 ? ? ? A =? (3) ? ? 1 1 0 0 1 1 0 0 ? ? 1 1 0 0 1 1 1 1 ? ? ? ? 1 1 0 0 1 0 1 0 ? 1 0 0 0 0 1 0 0 there is no totally unimodular matrix R such that matrix of the form (2). However, ? ? ? 1 1 1 0 0 0 0 0 0 0 ? 0 1 ? ? 0 0 ? 1 1 0 0 0 0 ? ? ? ? 0 0 ? 0 0 0 1 ?1 0 0 0 ? ? ? ? ? 0 0 ? ? 0 ?1 0 1 0 0 0 0 ? ? A =? ? 0 0 ? ? 0 0 0 0 ?1 1 0 0 ? ? ? ? 0 0 ? ? ?1 0 0 0 0 0 1 0 ? ? ? ? 0 0 ? ?1 0 0 0 1 0 0 0 ? 1 0 0 0 0 0 0 0 0 1 RA is an unbalanced hole 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 ? 0 0 0 0 0 0 ? ? 0 0 0 ? ? 0 ?1 0 ? ?, 0 1 1 ? ? 1 0 1 ? ? 1 0 0 ? 0 0 0

which shows that Conjecture 2 holds for the almost totally unimodular matrix in (3).We have veri?ed Conjecture 2 on several other examples including in?nite classes of almost totally unimodular matrices.

References
[1] P. Camion, Characterization of totally unimodular matrices, Proceedings of the American Mathematical Society, 16 (1965), pp. 1068–1073. [2] G. Cornu? ejols, Combinatorial Optimization: Packing and Covering, SIAM monograph, to be published. [3] M. Padberg, Total unimodularity and the Euler-subgraph problem, Operations Research Letters, 7 (1988), pp. 173–179.



更多相关文章:
...conjecture about almost totally unimodular matri....pdf
On Padberg’s conjecture about almost totally unimodular matrices - We consider Padberg’s conjectu...
Bicolorings and Equitable Bicolorings of Matrices.pdf
dedicated to Manfred Padberg Abstract Two classical theorems of Ghouila-Houri...submatrices are all totally unimodular is said almost totally unimodular. Camion...
...VERSION ON THE ORDER OF UNIMODULAR MATRICES MODU....pdf
ORDER OF UNIMODULAR MATRICES MODULO INTEGERS_专业...N “for almost all N ≤ x” we mean that ...A quadratic analogue of Artin’s conjecture on ...

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图