Resource title

Recognizing balanceable matrices

Resource image

image for OpenScout resource :: Recognizing balanceable matrices

Resource description

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, Cornu´ejols, Kapoor andVuˇskovi´c 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.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/31723/

Resource license