On the Existence of Heavy Columns in Binary Matrices with Distinct Rows

2026

Read On the Existence of Heavy Columns in Binary Matrices with Distinct Rows (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18450.txt.

Introduction

Jamolidin Abdurakhmanov, of Andijan State University in Uzbekistan, studies when a grid of ones and zeros must hold a heavy column. Each row of the grid is unlike each other row. A column counts as heavy when at least half of its cells hold a one. The ask is plain to state but hard to settle for all grid sizes.

He checks for which widths and heights such a column must show up. Grids like these show up in codes, in tests, and in plans for trials. A heavy column marks a trait that shows in at least half the rows. Proofs about when such a column is forced help teams know what a data set must hold, sight unseen. The work adds one more stone to that base of pure maths.

Catalog record

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-18450

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Existence of Heavy Columns in Binary Matrices with Distinct Rows Abstract Jamolidin K. Abdurakhmanov Associate Professor, PhD Department of Software Engineering Andijan State University Andijan, Uzbekistan [email protected], [email protected] ORCID: 0009-0008-0067-0553 Abstract. We investigate the existence of heavy columns in binary matrices with distinct rows. A column of an m\times n binary matrix is called heavy if the number of ones in it is at least \lceil m/2\rceil . We introduce two recursive algorithms, A_{1} and A_{2} , that examine properties of submatrices obtained by row filtering and column deletion. We prove that if algorithm A_{1} returns \True for a binary matrix with distinct rows, then the matrix contains at least one heavy column (Theorem 1). Furthermore, we prove that if algorithm A_{2} returns \True for a binary matrix with distinct rows, distinct columns, and no all-zero columns, then the matrix also contains at least one heavy column (Theorem 2). The key innovation in A_{2} is an early termination condition: if exactly one row has a zero in some column, that column is immediately identified as heavy. The proofs employ a novel argument based on the existence of unpaired rows with respect to specific columns, combined with careful analysis of the recursive structure of the algorithms. 2020 Mathematics Subject Classification. Primary 05B20; Secondary 05D99, 68R05. Key words and phrases. Binary matrix, heavy column, recursive algorithm, combinatorics, majority, voting theory. 1. Introduction Binary matrices arise naturally in numerous areas of discrete mathematics and computer science, including coding theory, combinatorial optimization, database theory, and social choice theory. The study of structural properties of binary matrices, particularly those with distinctness constraints on rows or columns, has a rich history dating back to the classical work of Ryser [ 12 , 13 ] and Gale [ 7 ] , and continues to yield interesting results [ 4 , 3 ] . In this paper, we investigate a natural question: under what conditions does a binary matrix with distinct rows contain a heavy column , that is, a column in which the number of ones is at least as large as the number of zeros? This question has direct connections to problems in voting theory, where heavy columns correspond to candidates approved by a majority of voters [ 2 ] , to covering problems in combinatorics, and to the analysis of Boolean functions in cryptography [ 5 ] . We approach this problem algorithmically by introducing two recursive algorithms that systematically examine submatrices obtained through row filtering and column deletion. Our main results establish that the return value of these algorithms provides a sufficient condition for the existence of heavy columns. The proof technique—based on the identification of unpaired rows and the construction of specific paths through the recursion trees—appears to be novel in the context of binary matrix theory. The paper is organized as follows. In Section 2 , we discuss related work and the novelty of our results. In Section 3 , we describe potential applications. In Section 4 , we introduce the basic definitions and notation. In Section 5 , we present algorithm A_{1} and prove Theorem 1 . In Section 6 , we present algorithm A_{2} and prove Theorem 2 . Section 7 contains concluding remarks and open problems. 2. Related Work and Novelty 2.1. Classical Results on Binary Matrices The combinatorial theory of binary matrices has a rich history. The foundational Gale-Ryser theorem [ 7 , 12 ] characterizes when a pair of sequences can be realized as the row sums and column sums of a binary matrix. Specifically, sequences (r_{1},\ldots,r_{m}) and (c_{1},\ldots,c_{n}) are realizable if and only if certain majorization conditions are satisfied. This theorem has been extended in numerous directions, including asymptotic counting results by Barvinok [ 3 ] . The Sauer-Shelah-Perles lemma [ 14 , 15 ] provides bounds on families of binary vectors based on VC dimension: if a family \mathcal{F}\subseteq\{0,1\}^{n} does not shatter any set of size d+1 , then |\mathcal{F}|\leq\sum_{i=0}^{d}\binom{n}{i} . While this lemma concerns subset relationships rather than column weights, it represents another classical constraint on binary matrix structure. Brualdi’s comprehensive treatise [ 4 ] covers combinatorial matrix classes including (0,1) -matrices, permanents, and Latin squares, establishing much of the modern vocabulary for the field. Ryser’s earlier monograph [ 13 ] remains influential for its treatment of combinatorial properties of matrices. 2.2. Tournament Matrices and Score Sequences Tournament matrices—where entry (i,j)=1 indicates that player i defeated player j —provide another classical context for binary matrix theory. Landau’s theorem [ 9 ] characterizes realizable score sequences: a sequence (s_{1},\ldots,s_{n}) with s_{1}\leq\cdots\leq s_{n} is the score sequence of some tournament if and only if \sum_{i=1}^{k}s_{i}\geq\binom{k}{2} for all k . Recent work by Kolesnik [ 8 ] has determined the asymptotic number of score sequences. 2.3. Novelty of Our Results Despite this rich literature, we have not found any existing theorem that establishes conditions guaranteeing the existence of heavy columns in binary matrices based on row distinctness. The Gale-Ryser theorem addresses existence of matrices with prescribed sums but does not consider conditions under which matrices must possess columns exceeding a weight threshold. The Sauer-Shelah lemma constrains family sizes but does not directly address column weights. The closest existing work involves pigeonhole arguments on binary matrices—for example, proving that a 14\times 14 matrix with 58 ones must contain an all-ones 2\times 2 submatrix. These use related double-counting techniques but address fundamentally different structural questions. Our contribution fills a gap by establishing that row distinctness, combined with specific algorithmic conditions, guarantees the existence of heavy columns. Moreover, the recursive proof technique—filtering rows by column values and analyzing the resulting submatrices—appears to be methodologically novel for establishing column weight properties. 3. Applications The concept of heavy columns has natural interpretations across several domains. 3.1. Voting Theory and Social Choice In approval voting, voters (rows) indicate which candidates (columns) they approve by placing a 1 in the corresponding entry. A heavy column corresponds to a candidate approved by at least half of the voters—a natural notion of majority support. The justified representation criterion in committee selection [ 2 ] requires that sufficiently large groups of voters with common approved candidates receive representation. This is essentially a local column-weight condition. Our results provide sufficient conditions under which at least one candidate must have majority approval when voters have distinct preference profiles. 3.2. Coding Theory In coding theory, the columns of a parity-check matrix determine error-detection and error-correction capabilities. Reed’s majority-logic decoding for Reed-Muller codes [ 11 ] recovers each message symbol by taking majority votes across independent recovery sets. The covering radius theorem connects column properties of parity-check matrices directly to error-correcting capability. Recent work by Ly and Soljanin [ 10 ] has shown that one-step majority-logic decoders can correct at most d_{\min}/4 errors for Reed-Muller codes, highlighting the continued relevance of majority-based analysis in coding theory. 3.3. Cryptography Cryptographic security often requires balanced Boolean functions —those with an equal number of ones and zeros in their truth tables. Unbalanced functions are vulnerable to correlation attacks. The study of k -th order correlation immunity relates to orthogonal array structures [ 5 ] . Our results on heavy columns provide conditions under which imbalance (in the direction of more ones) must

Read the complete text