[Math] Binary matrices with constant row and column sums

co.combinatoricsterminology

My question is about $m \times n$ binary matrices (aka $\{0,1\}$-matrices), whose rows all sum to the same value, and whose columns all sum to the same value (but these two values may be different).

The first question is simply: is there a standard name for such matrices? They correspond to the biadjacency matrices of so-called "biregular bipartite graphs", but this terminology doesn't appear to be commonly used.

Second, are there any "interesting" constructions of families of such matrices, in particular that are connected to other combinatorial objects?

Two simple examples of constructions of these matrices are the $\binom{n}{k} \times n$ matrix whose rows consist of every $n$-bit string with Hamming weight $k$; and the $2^n \times 2^n$ Sylvester-Hadamard matrices with the first row and column removed.

I did find a paper by Brualdi titled "Matrices of Zeros and Ones with Fixed Row and Column Sum Vectors", but this seems to be more concerned with the question of existence of these matrices, rather than constructing them.

Best Answer

To answer your question about interesting combinatorial objects: Your Sylvester-Hadamard matrix example generalizes in at least two ways.

  1. The incidence matrix of any balanced incomplete block design or, more generally, $t$-design has constant row and column sums. Specifically, a BIBD$(v,b,r,k,\lambda)$ represented as a $v\times b$ incidence matrix has row sums $r$ and column sums $k$. Normalizing an $n\times n$ Hadamard matrix so that the first row and column consist entirely of 1s, and then removing this row and column while replacing $-1$s with 0s gives a design with parameters $v=b=n-1$, $r=k=n/2-1$, $\lambda=n/4-1$. So among Hadamard matrices, Sylvester-Hadamard matrices are not special in this regard. Finite projective planes are also designs, with parameters $v=b=q^2+q+1$, $r=k=q+1$, $\lambda=1$, where $q$ is the order of the plane.

  2. Sylvester-Hadamard matrices have the additional property that if the first row and column are removed, and the remaining rows and columns are suitably permuted, one obtains a circulant matrix. (Most Hadamard matrices do not have this property, but Paley-Hadamard matrices constructed using quadratic residues in $\mathbb{F}_p$, $p\equiv3\pmod{4}$ also do. More generally, Hadamard matrices constructed from difference sets do.) But any $n\times n$ circulant matrix whatsoever will have constant row and column sums (with row sums equal to column sums). (This is not combinatorially so interesting in general.)

Addendum: In answer to your first question, design theorists call an incidence structure whose incidence matrix has constant row and column sums a tactical configuration. This is a $t$-design with $t=1$. The balanced incomplete block designs in the first part of my answer are $t$-designs with $t=2$, but any $t$-design is also a $(t-1)$-design. The condition that any two points be incident with exactly $\lambda$ blocks gives BIBDs a lot of additional interesting structure that tactical configurations do not typically have. 3-, 4-, and 5-designs are more interesting still. See the PlanetMath page for more information.

Added 12 July 2022: I just updated the link above to the La Jolla Difference Set Repository, which is now the La Jolla Combinatorics Repository. Dan Gordon's slides here have examples showing how to query the database.

Related Question