Balanced matrices with row sum 3

✍ Scribed by Alan Tucker

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 257 KB
• Volume: 132
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)00578-f

✦ Synopsis

It is shown that a balanced matrix whose row sums are < 3 is totally unimodular. The proof is based on analyzing the effects of Gaussian elimination on such balanced matrices.

A Cl matrix is balanced if it contains no square submatrix of odd size in which each row and column contains exactly two 1's. We call such an excluded submatrix an odd cycle. Note that any submatrix of a balanced matrix is balanced. Balanced matrices were introduced by Berge in [l] where he showed that if A is a balanced matrix, then the linear programs max(1.x:

Ax<u, O<x<w} and min(1.