Balancing matrices with line shifts

József Beck; Joel Spencer

doi:10.1007/BF02579185

Balancing matrices with line shifts

József Beck, Joel Spencer

Research output: Contribution to journal › Article › peer-review

Abstract

We give a purely deterministic proof of the following theorem of J. Komlós and M. Sulyok. Let A=(a_ij ), a_ij =±1 be an n×n matrix. One can multiply some rows and columns by -1 such that the absolute value of the sum of the elements of the matrix is ≦2 if n is even and 1 if n is odd. Note that Komlós and Sulyok applied probabilistic ideas and so their method worked only for n>n₀.

Original language	English (US)
Pages (from-to)	299-304
Number of pages	6
Journal	Combinatorica
Volume	3
Issue number	3-4
DOIs	https://doi.org/10.1007/BF02579185
State	Published - Sep 1983

Keywords

AMS subject classification (1980): 05B20

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/BF02579185

Cite this

@article{46fbf54851c945aea917b2afde66b6f6,

title = "Balancing matrices with line shifts",

abstract = "We give a purely deterministic proof of the following theorem of J. Koml{\'o}s and M. Sulyok. Let A=(a ij ), a ij =±1 be an n×n matrix. One can multiply some rows and columns by -1 such that the absolute value of the sum of the elements of the matrix is ≦2 if n is even and 1 if n is odd. Note that Koml{\'o}s and Sulyok applied probabilistic ideas and so their method worked only for n>n 0.",

keywords = "AMS subject classification (1980): 05B20",

author = "J{\'o}zsef Beck and Joel Spencer",

year = "1983",

month = sep,

doi = "10.1007/BF02579185",

language = "English (US)",

volume = "3",

pages = "299--304",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3-4",

}

TY - JOUR

T1 - Balancing matrices with line shifts

AU - Beck, József

AU - Spencer, Joel

PY - 1983/9

Y1 - 1983/9

N2 - We give a purely deterministic proof of the following theorem of J. Komlós and M. Sulyok. Let A=(a ij ), a ij =±1 be an n×n matrix. One can multiply some rows and columns by -1 such that the absolute value of the sum of the elements of the matrix is ≦2 if n is even and 1 if n is odd. Note that Komlós and Sulyok applied probabilistic ideas and so their method worked only for n>n 0.

AB - We give a purely deterministic proof of the following theorem of J. Komlós and M. Sulyok. Let A=(a ij ), a ij =±1 be an n×n matrix. One can multiply some rows and columns by -1 such that the absolute value of the sum of the elements of the matrix is ≦2 if n is even and 1 if n is odd. Note that Komlós and Sulyok applied probabilistic ideas and so their method worked only for n>n 0.

KW - AMS subject classification (1980): 05B20

UR - http://www.scopus.com/inward/record.url?scp=51649161116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51649161116&partnerID=8YFLogxK

U2 - 10.1007/BF02579185

DO - 10.1007/BF02579185

M3 - Article

AN - SCOPUS:51649161116

SN - 0209-9683

VL - 3

SP - 299

EP - 304

JO - Combinatorica

JF - Combinatorica

IS - 3-4

ER -

Balancing matrices with line shifts

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this