7
$\begingroup$

What is the number $N$ of $n \times n$ $0$-$1$ matrices with rank $k$?

I read this sequence is "OEIS A064230 Triangle $T(n,k)$ = number of rational (0,1) matrices of rank $k$ ($n\ge 0$, $0\le k\le n$)".

I am interested in approximation results, i.e. finding upper and/or lower bound for $N$ when $k=\Theta(f(n))$ for some function $f$.

Thank you! PS: I would like to emphasize that, for this "counting problem" context, I am asking only for (even rough) estimates.

Improve this question
$\endgroup$
7
  • $\begingroup$ The Zivkovic reference there is the latest I know. Considering the large number of such matrices, I suspect you will not see an exact and useful enumeration any time soon. I suspect even approximations will be very rough. Gerhard "Doesn't Know The Rank Asymptotics" Paseman, 2017.10.10. $\endgroup$ – Gerhard Paseman Oct 10 '17 at 18:55
  • $\begingroup$ Possible duplicate of Number rank-k 0-1 matrices (characteristic 0) $\endgroup$ – 1.. Oct 10 '17 at 21:10
  • $\begingroup$ @777, this question asks for estimates, that one doesn't. Not quite a duplicate, I think. $\endgroup$ – Gerry Myerson Oct 10 '17 at 22:17
  • $\begingroup$ @GerryMyerson mathoverflow.net/questions/195326/… $\endgroup$ – 1.. Oct 10 '17 at 22:58
  • 3
    $\begingroup$ Possible duplicate of Enumerating matrices function of ranks $\endgroup$ – Chris Godsil Oct 10 '17 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.