What is the number of $n\times n$ 0/1-matrices with rank $k$? (The rank is taken over the rationals.)
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\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