The Binary Rank of Circulant Block Matrices

DOI10.1016/J.LAA.2022.10.006MaRDI QIDQ6396898arXivFDO

Authors Ishay Haviv, Michal Parnas

Publication date 19 April 2022

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.LAA.2022.10.006

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Boolean and Hadamard matrices (15B34) Special matrices (15B99)

arXiv classification

cs.DMmath.CO

Abstract: The binary rank of a $0,1$ matrix is the smallest size of a partition of its ones into monochromatic combinatorial rectangles. A matrix $M$ is called $(k_1,ldots,k_m;n_1,ldots,n_m)$ circulant block diagonal if it is a block matrix with $m$ diagonal blocks, such that for each $iin[m]$, the $i$th diagonal block of $M$ is the circulant matrix whose first row has $k_i$ ones followed by $n_i-k_i$ zeros, and all of whose other entries are zeros. In this work, we study the binary rank of these matrices and of their complement. In particular, we compare the binary rank of these matrices to their rank over the reals, which forms a lower bound on the former. We present a general method for proving upper bounds on the binary rank of block matrices that have diagonal blocks of some specified structure and ones elsewhere. Using this method, we prove that the binary rank of the complement of a $(k_1,ldots,k_m;n_1,ldots,n_m)$ circulant block diagonal matrix for integers satisfying $n_i>k_i>0$ for each $iin[m]$ exceeds its real rank by no more than the maximum of $gcd(n_i,k_i)-1$ over all $iin[m]$. We further present several sufficient conditions for the binary rank of these matrices to strictly exceed their real rank. By combining the upper and lower bounds, we determine the exact binary rank of various families of matrices and, in addition, significantly generalize a result of Gregory. Motivated by a question of Pullman, we study the binary rank of $k$-regular $0,1$ matrices and of their complement. As an application of our results on circulant block diagonal matrices, we show that for every $kgeq2$, there exist $k$-regular $0,1$ matrices whose binary rank is strictly larger than that of their complement. Furthermore, we exactly determine for every integer $r$, the smallest possible binary rank of the complement of a $2$-regular $0,1$ matrix with binary rank $r$.

This page was built for publication: The Binary Rank of Circulant Block Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6396898)