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.

- Conference matrices and unimodular lattices
- Almost everyone is worried about the problem of overpopulation
- It's almost here!(mainly about iPhone 4S)英语课演讲稿 介绍苹果第五代手机4S
- KJMS A NOTE ON VIZING’S CONJECTURE ABOUT THE BONDAGE NUMBER
- On Cusick-Cheon's Conjecture About Balanced Boolean Functions in the Cosets of the Binary R
- Complex Hadamard matrices and the Spectral Set Conjecture
- Note Unimodular Matrices and Parsons Numbers 1
- PRELIMINARY VERSION ON THE ORDER OF UNIMODULAR MATRICES MODULO INTEGERS
- PRELIMINARY VERSION ON THE ORDER OF UNIMODULAR MATRICES MODULO INTEGERS P

更多相关文章：
**
...***conjecture* *about* *almost* *totally* *unimodular* matri....pdf

*On* *Padberg*’s *conjecture* *about* *almost* *totally* *unimodular* *matrices* - We consider *Padberg*’s conjectu...**
Bicoloring***s* and Equitable Bicoloring*s* of *Matrices*.pdf

dedicated to Manfred*Padberg* Abstract Two classical theorems of Ghouila-Houri...sub*matrices* 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* ...

dedicated to Manfred

ORDER OF