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

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

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
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. –  P Vanchinathan Jun 29 '13 at 3:21
2  
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 :-) –  Mariano Suárez-Alvarez Jun 29 '13 at 3:23
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.