Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
As to the name, a Google search, and a glance to the references in the papers, confirm that the long but self-explicatory combination that you used in the title is very popular. –  Pietro Majer Aug 25 '10 at 9:55
    
Indeed, the columns ${\bf must}$ sum to a different value than the rows, unless $m=n$ (or the common sum is zero). There is some discussion of these matrices in Ryser's little book on Combinatorial Mathematics. –  Gerry Myerson Aug 25 '10 at 13:00
    
You should investigate papers of A. Barvinok on contingency tables. –  Andy B Jan 27 '11 at 6:23
add comment

7 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
Thanks very much - that's very helpful. –  Ashley Montanaro Aug 25 '10 at 21:09
add comment

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.

share|improve this answer
    
Thanks, this is a nice alternative way to look at these matrices. –  Ashley Montanaro Aug 25 '10 at 12:56
    
"Magic points" -- I love it! –  JBL Aug 25 '10 at 13:06
3  
"your matrices arise naturally as their vertices": this isn't true due to the restriction to (0,1) matrices. For example, let $$A=\begin{pmatrix}2 & 0 \\ 0 & 2\end{pmatrix}, B=\begin{pmatrix}0 & 2\\ 2 & 0\\ \end{pmatrix}, C=\begin{pmatrix}1 & 1\\ 1 & 1\end{pmatrix},$$ then the row and column sums of $A,B,C$ are equal to 2, but $C=1/2(A+B),$ so $C$ is not a vertex of the corresponding transportation polytope. You can impose (0,1) restriction by force, but I think that the resulting polytopes would be quite different from the standard transportation polytopes. –  Victor Protsak Aug 25 '10 at 19:07
    
Victor: you're absolutely right of course, I'll edit my so-called answer... –  Philippe Nadeau Aug 27 '10 at 9:10
    
@Phillipe, Philippe, could you expound a little on "transportation polytopes"? Wikipedia has nothing, and the google search led to papers about the "20 year history of ..." etc. Are they akin or similar to stochastic matrices describing the probabilistic evolution of a Markov chain? When limited to zeros and ones, are they just a permutation matrix? Please forgive me if my question seems stupid. I am familiar with stochastic matrices, but not "transportation polytopes". –  sleepless in beantown Aug 27 '10 at 9:29
show 1 more comment

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.

share|improve this answer
    
Thanks; this connection to other types of object is indeed the sort of thing I was looking for. –  Ashley Montanaro Aug 25 '10 at 12:59
add comment

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.

share|improve this answer
    
Thanks for the link; some of those references were useful. In particular, the term "semi-regular bipartite graph" seems to be yet another way of describing these matrices. –  Ashley Montanaro Aug 25 '10 at 13:23
add comment

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 permuation on a finite state space.

share|improve this answer
add comment

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 $* * *$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.