A 0/ +/- 1 matrix is balanced if it does not contain a square submatrix with exactly two nonzero entries per row and per column in which the sum of all entries is 2 modulo 4. A 0/1 matrix is balanceable if its nonzero entries can be signed +/- 1 so that the resulting matrix is balanced. A signing algorithm due to Camion shows that the problems of recognizing balanced 0/ +/- 1 matrices and balanceable 0/1 matrices are equivalent. Conforti, Cornuejols, Kapoor and Vuikovic gave an algorithm to test if a 0/ +/- 1 matrix is balanced. Truemper has characterized balanceable 0/1 matrices in terms of forbidden submatrices. In this paper we give an algorithm that explicitly finds one of these forbidden submatrices or shows that none exists.
Recognizing balanceable matrices
CONFORTI, MICHELANGELO;ZAMBELLI, GIACOMO
2006
Abstract
A 0/ +/- 1 matrix is balanced if it does not contain a square submatrix with exactly two nonzero entries per row and per column in which the sum of all entries is 2 modulo 4. A 0/1 matrix is balanceable if its nonzero entries can be signed +/- 1 so that the resulting matrix is balanced. A signing algorithm due to Camion shows that the problems of recognizing balanced 0/ +/- 1 matrices and balanceable 0/1 matrices are equivalent. Conforti, Cornuejols, Kapoor and Vuikovic gave an algorithm to test if a 0/ +/- 1 matrix is balanced. Truemper has characterized balanceable 0/1 matrices in terms of forbidden submatrices. In this paper we give an algorithm that explicitly finds one of these forbidden submatrices or shows that none exists.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
