Decomposition of balanced matrices

A 0, 1 matrix is balanced if it does not contain a square submatrix of odd order with two ones per row and per column. We show that a balanced 0, 1 ma trix is either totally unimodular or its bipartite representation has a cut set consisting of two adjacent nodes and some of their neighbors. This resu lt yields a polytime recognition algorithm for balancedness. To prove the r esult, we first prove a decomposition theorem for balanced 0, 1 matrices th at are not strongly balanced. (C) 1999 Academic Press.