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

What is the number of $n\times n$ 0/1-matrices with rank $k$? (The rank is taken over the rationals.)

share|improve this question

1 Answer 1

This sequence is OEIS A064230 Triangle T(n,k) = number of rational (0,1) matrices of rank k (n >= 0, 0 <= k <= n)

According to comments rows add to $2^{n^2}$.

There are some references and pari/gp code.

share|improve this answer
    
I think I can understand that the rows add up to $2^{n^2}$ without checking the numbers (every matrix has a rank). –  Marc van Leeuwen Sep 30 '13 at 14:04
    
On the other hand the other comment "... that almost all such matrices are invertible" seems out of place, since the cited article mentions matrices with entries $\pm1$ in its title. And indeed it appears that corank $1$ is more frequent than corank $0$, at least for the displayed numbers. –  Marc van Leeuwen Sep 30 '13 at 14:09
    
$\pm 1$ matrices and $(0,1)$ matrices are equivalent here. When counting $\pm 1$ matrices, we can assume without loss of generality that the first row and column are all $-1$. After subtracting the first row from each other row, the lower right $(n-1) \times (n-1)$ block has entries uniform and independent on $\{0,2\}$. So the probability an $n \times n$ $\pm 1$ matrix has corank $k$ is the same as that an $(n-1) \times (n-1)$ $(0,1)$ matrix has corank $k$. –  Kevin P. Costello Sep 30 '13 at 17:57

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.