# zbMATH — the first resource for mathematics

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.)
##### Keywords:
recognition algorithm; extended star cutset
Full Text:
##### References:
 [1] Berge, C., Sur certains hypergraphes généralisant LES graphes bipartites, (), 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, (), 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 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.