Suppose $K$ is a field of characteristic $0$. Let $M \in K^{n \times m}$ be a matrix such that every entry of $M$ is either $0$ or $1$. About this matrix, I know further that each sum over a column and a row is a constant number, i.e.

$$\sum_{i=1}^n M_{ij} = c_{\text{column}} ~~ \forall j=1,...,m$$


$$\sum_{j=1}^m M_{ij} = c_{\text{row}} ~~ \forall i=1,...,n$$

for some $c_{\text{column}}, c_{\text{row}}$ both lying in $\{1,2,3,...\}$.

Question: Are there criteria that enables us to say something about the rank of $M$? I.e. are there theorems of the form

'' If some condition is satisfied, then $$\text{rank}(M) \geq f(n,m,c_{\text{column}}, c_{\text{row}})$$

for some (hopefully not too complicated) function $f$''?

I have found a paper of Odlyzko from '79 in which he shows that a $0$-$1$-matrix with constant row-sums is of full rank if the number of distinct row vectors exceeds a certain number. Unfortunately, in my case I do not have sufficiently many row-vectors but I have some additional information, for example, I know that the column-sum is also constant.




Even in the special case $K = \mathbb R$, $n=m$ and $c_{\rm row} = c_{\rm column}$, this is not an easy problem!

A good place to start looking would likely be the following paper.

On the minimum rank of regular classes of matrices of zeros and ones
by Brualdi, Manber and Ross

You may also want to see Section 3.10 of Brualdi's 2006 "Combinatorial Matrix Classes" book. I suspect you will find it contains just about all of what is known.

  • $\begingroup$ The permutation matrices are all non-singular. On the other hand a matrix in which all the entries are the same has rank 1 (or zero if the entries are 0). Take two permutation which do not agree anywhere. Then the sum of the corresponding permutation matrices can be interesting case study. Now look at matrices where all the one's are placed in a single diagonal parallel to the main diagonal. This will give every possible rank. So it is not going to be an easy function. $\endgroup$ – P Vanchinathan Jun 29 '13 at 3:21
  • 4
    $\begingroup$ Given that the field is to be of characteristic zero, it is actually enough to do this for $\mathbb Q$ (or $\mathbb R$, if one prefers) because the entries are integers. The special case is therefore all one needs to do :-) $\endgroup$ – Mariano Suárez-Álvarez Jun 29 '13 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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