×

Balanced \(0,\pm 1\) matrices. I: Decomposition. (English) Zbl 1026.05016

Summary: A \(0\), \(\pm 1\) matrix is balanced if, in every square submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This paper extends the decomposition of balanced \(0\), \(1\) matrices obtained by M. Conforti, G. Cornuéjols and M. R. Rao [J. Comb. Theory, Ser. B 77, 292-406 (1999; Zbl 1023.05025)] to the class of balanced \(0\), \(\pm 1\) matrices. As a consequence, we obtain a polynomial time algorithm for recognizing balanced \(0\), \(\pm 1\) matrices.

MSC:

05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., Sur certains hypergraphes généralisant les graphes bipartites, (Erdős, P.; Rényi, A.; Sós, V., Combinatorial Theory and its Applications, I. Combinatorial Theory and its Applications, I, Colloquium Math. Society János Bolyai, 4 (1970), North-Holland: North-Holland Amsterdam), 119-133 · Zbl 0205.54501
[2] Berge, C., Balanced matrices, Math. Programming, 2, 19-31 (1972) · Zbl 0247.05126
[3] Camion, P., Characterization of totally unimodular matrices, Proc. Am. Math. Soc., 16, 1068-1073 (1965) · Zbl 0134.25201
[4] Chandru, V.; Hooker, J. N., Extended Horn sets in propositional logic, J. Assoc. Comput. Mach., 38, 205-221 (1991) · Zbl 0942.68721
[5] Conforti, M.; Cornuéjols, G., A class of logic problems solvable by linear programming, J. Assoc. Comput. Mach., 42, 1107-1113 (1995) · Zbl 0900.03025
[6] Conforti, M.; Cornuéjols, G., Balanced 0, ±1 matrices, bicoloring and total dual integrality, Math. Programming, 71, 249-258 (1995) · Zbl 0849.90095
[7] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Rao, M. R.; Vušković, K., Balanced matrices, (Birge, J. R.; Murty, K. G., Mathematical Programming: State of the Art 1994 (1994), The University of Michigan Press: The University of Michigan Press Ann Arbor), 1-33
[8] Conforti, M.; Cornuéjols, G.; Rao, M. R., Decomposition of balanced matrices, J. Combin. Theory Ser. B, 77, 292-406 (1999) · Zbl 1023.05025
[9] Conforti, M.; Rao, M. R., Structural properties and recognition of restricted and strongly unimodular matrices, Math. Programming, 38, 17-27 (1987) · Zbl 0642.90104
[10] Cornuéjols, G.; Cunningham, W. H., Compositions for perfect graphs, Discrete Math., 55, 245-254 (1985) · Zbl 0562.05043
[11] Cunningham, W. H.; Edmonds, J., A combinatorial decomposition theory, Canad. J. Math., 32, 734-765 (1980) · Zbl 0442.05054
[12] Fulkerson, D. R.; Hoffman, A.; Oppenheim, R., On balanced matrices, Math. Programming Study, 1, 120-132 (1974) · Zbl 0357.90038
[13] Georgakopoulos, G.; Kavvadias, D.; Papadimitriou, C. H., Probabilistic satisfiability, J. Complexity, 4, 1-11 (1988) · Zbl 0647.68049
[14] Ghouila-Houri, A., Caractérisations des matrices totalement unimodulaires, C.R. Acad. Sci. Paris, 254, 1192-1193 (1962) · Zbl 0114.25102
[15] Seymour, P., Decomposition of regular matroids, J. Combin. Theory Ser. B, 28, 305-359 (1980) · Zbl 0443.05027
[16] Truemper, K., Alpha-balanced graphs and matrices and GF(3)-representability of matroids, J. Combin. Theory Ser. B, 32, 112-139 (1982) · Zbl 0478.05026
[17] Truemper, K., Polynomial theorem proving. I. Central matrices, Tech. Rep. (1990)
[18] Truemper, K., Matroid Decomposition (1992), Academic Press: Academic Press Boston · Zbl 0760.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.