Binary matrices with constant row and column sums

Question

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.

Answer 1

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.

Answer 2

If you fix $m,n$ and the row and column values, and then consider the matrices as points in $\mathbb{R}^{mn}$, their convex hull forms a convex polytope known as a transportation polytope. In the particular case of permutation matrices one obtains the famous Birkhoff polytope for instance.

So I would advise you to look up references about those polytopes, since your matrices arise naturally as their vertices; hopefully you can find the names and particular constructions you asked for.

(Well this this should probably be a comment, since I do not really answer any of your questions; unfortunately I do not have enough magic points to write one)

Edit: As pointed out in a comment, what I wrote above is simply not true. In fact, the $\lbrace 0,1\rbrace$-matrices considered are more precisely the lattice points of the intersection of a transportation polytope with the hypercube $[0,1]^{mn}$; this forms another polytope which may actually be interesting in its own right.

Answer 3

About your first question: remark that when $m=n$ these matrices are sometimes called "semi-magic squares" (like "magic squares" but without the "sums along the diagonals" condition).

About the constructions of families of such matrices, there is another paper by Brualdi:

R.A. Brualdi, Algorithms for constructing (0, 1)-matrices with prescribed row and column sum vectors, Discrete Math. 306 (2006), no. 23, 3054-3062.

You can see also this paper by Fonseca and Mamede on the same subject:

http://www.mat.uc.pt/~cmf/papers/01matrix_fonseca_mamede.pdf

Here the construction is related to other combinatorial objects (pairs of semi-standard Young tableaux of conjugate shapes), as you wished.

Answer 4

See this paper by Canfield and McKay. As the title suggests it focuses on the asymptotic enumeration, but it has lots of useful references.

Added A simple arithmetic construction that realizes all possible constant line sums is as follows. Let $g=\gcd(m,n)$. Label rows and columns by elements of $\mathbb{Z}/m\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$ respectively. Fix $0\le s\ge g$. Put a $1$ in each position $(j+k,j)$ where $j$ runs through $\mathbb{Z}$ and $0\le k < s$, interpreting $j+k$ and $j$ as integers modulo $m$ and $n$ respectively.

Answer 5

build the matrix $H =(A-J)/2$ from your matrix $A.$ If this new matrix is hadamard and satisfy your condition $H$ it is called ``regular hadamard", ((google this)).

$J$ is the matrix with only $1$ everywhere.

luis $* * *$

Answer 6

An $m \times m$ matrix of this type is called a stochastic matrix if the sum of each of its rows is 1 (a right stochastic matrix) or if the sum of each of its columns is 1 (a left stochastic matrix). A doubly-stochastic matrix has the sums of rows and the sums of columns equal to one. A stochastic matrix is also called a transition matrix as it can represent the transition probabilities of a Markov chain over a finite state space $s$, where in this case $|s|=m$.

Each element of such a stochastic matrix is restricted to be $x_{i,j} \in \mathbb{R}, x_{i,j}>0$. Thus in the case of stochastic matrices, since you are asking about binary matrices, every matrix entry is either zero or one: $x_{i,j} \in \{0,1\}$. This restricts the sum to being $1$, and this type of stochastic binary matrix is also known as a permutation matrix as it represents the transitions in a permutation on a finite state space.

Answer 7

Read these articles about the topic:

Newman, M. (1978). Combinatorial Matrices with Small Determinants. Canadian Journal of Mathematics, 30(4), 756-762. doi:10.4153/CJM-1978-065-8

http://ac.els-cdn.com/0024379578900769/1-s2.0-0024379578900769-main.pdf?_tid=ad812dd8-df9d-11e2-9fa1-00000aab0f27&acdnat=1372388089_8c2c33dc0172c0033cf87e6eb57c54df