✦ LIBER ✦

Balanced 0, ±1 Matrices I. Decomposition

✍ Scribed by Michele Conforti; Gérard Cornuéjols; Ajai Kapoor; Kristina Vušković

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 287 KB
Volume: 81
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.2010

No coin nor oath required. For personal study only.

✦ Synopsis

A 0, \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 Conforti, Cornue jols, and Rao (1999, J. Combin. Theory Ser. B 77, 292 406) to the class of balanced 0, \1 matrices. As a consequence, we obtain a polynomial time algorithm for recognizing balanced 0, \1 matrices.

📜 SIMILAR VOLUMES

Balanced 0, ±1 Matrices II. Recognition

Balanced 0, ±1 Matrices II. Recognition Algorithm

✍ Michele Conforti; Gérard Cornuéjols; Ajai Kapoor; Kristina Vušković 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 232 KB

In this paper we give a polynomial time recognition algorithm for balanced 0, \1 matrices. This algorithm is based on a decomposition theorem proved in a companion paper.

Singular value decomposition of design m

Singular value decomposition of design matrices in ANOVA with balanced data

✍ Tom Wansbeek 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 40 KB

Singular value decomposition of design m

Singular value decomposition of design matrices in ANOVA with balanced data

✍ Tom Wansbeek 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 244 KB

Ideal 0, 1 Matrices

✍ G. Cornuejols; B. Novick 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 533 KB

We define a 0,1 matrix \(M\) to be ideal if all vertices of the polyhedron \(\{x: M x \geqslant 1\), \(x \geqslant 0\}\) have only 0,1 components. We expand the list of known minor minimal nonideal matrices by several thousand. Many of these examples are obtained polyhedrally, by constructing new mi

Classification de certaines matrices 0–1

✍ J.D. MacAllister; M. Sakarovitch 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 723 KB

This paper is a survey of the main propertics of special O-1 matrices. All thcsc prcrpertles are presented in a unified bmework (in terms of matrices and not in terms of hypergraphs). The paper contains no original result and no proof. NuI doute que I'une des idles de Bcrge quand il a introduit le c

Permanents of 0,1-matrices

✍ B Gordon; T.S Motzkin; L Welch 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 500 KB