5
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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
http://www.sciencedirect.com/science/article/pii/0097316586901135

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.

Improve this answer
$\endgroup$
2
  • $\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, 2013 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, 2013 at 3:23

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.