Balancing matrices with line shifts

József Beck, Joel Spencer

Research output: Contribution to journalArticle

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 0.

Original languageEnglish (US)
Pages (from-to)299-304
Number of pages6
JournalCombinatorica
Volume3
Issue number3-4
DOIs
StatePublished - Sep 1983

Keywords

  • AMS subject classification (1980): 05B20

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Balancing matrices with line shifts'. Together they form a unique fingerprint.

  • Cite this