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, 2017 at 18:55
  • $\begingroup$ Possible duplicate of Number rank-k 0-1 matrices (characteristic 0) $\endgroup$
    – Turbo
    Oct 10, 2017 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, 2017 at 22:17
  • $\begingroup$ @GerryMyerson mathoverflow.net/questions/195326/… $\endgroup$
    – Turbo
    Oct 10, 2017 at 22:58
  • 3
    $\begingroup$ Possible duplicate of Enumerating matrices function of ranks $\endgroup$
    – Chris Godsil
    Oct 10, 2017 at 23:10

0

Reset to default

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.