Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
2 of 2
added tag
Ricardo Andrade
  • 6.3k
  • 5
  • 43
  • 69

Rank of a 0-1-matrix

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

and

$$\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.

Regards,

FW