3
$\begingroup$

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

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I think I can understand that the rows add up to $2^{n^2}$ without checking the numbers (every matrix has a rank). $\endgroup$ Sep 30, 2013 at 14:04
  • $\begingroup$ 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. $\endgroup$ Sep 30, 2013 at 14:09
  • $\begingroup$ $\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$. $\endgroup$ Sep 30, 2013 at 17:57

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.