15
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 25, 2010 at 9:55
  • $\begingroup$ 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. $\endgroup$ Aug 25, 2010 at 13:00
  • 2
    $\begingroup$ You should investigate papers of A. Barvinok on contingency tables. $\endgroup$
    – Andy B
    Jan 27, 2011 at 6:23
  • $\begingroup$ In case of symmetric square matrices and equal row sum and column sum these matrices correspond to the adjacency matrices of regular graphs; admittedly a rather trivial remark. Another trivial remark is that hese matrices represent solutions to specific assignment problems. $\endgroup$ May 30, 2023 at 17:55

7 Answers 7

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Here is at least a Wayback Machine snapshot of the difference sets repository linked in the answer. I am not sure what would be good replacement for that dead link - it seems that D. Gordon has some database with this topic. $\endgroup$ Jul 12, 2022 at 15:38
  • $\begingroup$ @MartinSleziak If I'm not mistaken, the old La Jolla Difference Set Repository was also Dan Gordon's work. I would guess the database you link to is the successor of that one. It seems less browsable than the old version, although I must admit it's been years since I used it, so I may be misremembering. The slides here, starting on page 9, show how to enter search terms to generate various tables. $\endgroup$ Jul 12, 2022 at 15:52
9
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks, this is a nice alternative way to look at these matrices. $\endgroup$ Aug 25, 2010 at 12:56
  • $\begingroup$ "Magic points" -- I love it! $\endgroup$
    – JBL
    Aug 25, 2010 at 13:06
  • 3
    $\begingroup$ "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. $\endgroup$ Aug 25, 2010 at 19:07
  • $\begingroup$ Victor: you're absolutely right of course, I'll edit my so-called answer... $\endgroup$ Aug 27, 2010 at 9:10
  • $\begingroup$ @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". $\endgroup$ Aug 27, 2010 at 9:29
4
$\begingroup$

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.

$\endgroup$
2
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Aug 25, 2010 at 13:23
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ The 1st link leads to a page where we read, "The Canadian Mathematical Society (CMS) has entered into a publishing partnership with Cambridge University Press (Cambridge). The web site for CJM is now hosted on Cambridge Core." $\endgroup$ Jul 10, 2022 at 2:36
  • 1
    $\begingroup$ A currently active URL for the 1st paper is cambridge.org/core/journals/canadian-journal-of-mathematics/… The paper is Morris Newman, Combinatorial matrices with small determinants, and the DOI is doi.org/10.4153/CJM-1978-065-8 $\endgroup$ Jul 10, 2022 at 2:44
  • 2
    $\begingroup$ The 2nd link doesn't lead anywhere, and I can't decipher the URL to work out where it was supposed to go. If OP is still here, maybe he could help out by editing in the author, title, journal, volume, year, and pages. $\endgroup$ Jul 10, 2022 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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