29
$\begingroup$

Recently a friend stumbled across this question:

Let $M$ be a random $n \times n$ matrix with entries in $\{0,1\}$ (both zero and one has probability $p = q = \frac{1}{2}$). What is its expected rank?

My intuition is that it would be something of order $\frac{n}{\log n}$, similarly to coupon collector's problem, but I could not produce anything more specific. Unfortunately my linear algebra skills are, to put it mildly, rusty. Is this a know problem? If the exact calculation is hard, are there any simple arguments regarding the order when $n$ tends to infinity?

I would greatly appreciate any hints, proofs, references, or any other help.

Edit: The original question was phrased in terms of field $\mathbb{F}_2$, however, the approach for $\mathbb{R}$ would be great as well, that is I would consider it a full answer (especially if simpler).

$\endgroup$
7
  • 4
    $\begingroup$ Just to clarify: the rank of $M$ seen as matrix over $\mathbb R$ or as matrix over $\mathbb F_2$ (the binary field)? $\endgroup$ Mar 7, 2013 at 23:43
  • 1
    $\begingroup$ The original question was phrased in terms of $\mathbb{F}_2$, however, the answer for $\mathbb{R}$ would be great as well. $\endgroup$
    – dtldarek
    Mar 8, 2013 at 0:02
  • $\begingroup$ @MatemáticosChibchas can you please give an example of a matrix that has different ranks in $\mathbb{F}_2$ and $\mathbb{R}$? I was unable to find one. I dont know how to prove there exist no such matrices, therefore I would be happy for an example ;) $\endgroup$
    – CBenni
    Mar 8, 2013 at 0:03
  • 6
    $\begingroup$ @CBenni, just take a $3\times3$ zero-one matrix with determinant $2$. It's invertible, thus rank $3$ in the reals, but has determinant zero in the finite field, thus rank strictly less than $3$. $\endgroup$ Mar 8, 2013 at 0:10
  • 1
    $\begingroup$ The sum of the ranks of all 0-1 $n\times n$ matrices is in OEIS with no closed form given: oeis.org/A086875 . $\endgroup$
    – Steve Kass
    Mar 8, 2013 at 1:43

1 Answer 1

26
$\begingroup$

The rank of a random $n$ by $n$ matrix with entries in ${\Bbb F}_2$ which are independently chosen and equally likely to be $0$ or $1$ is analyzed in Kolchin's book Random Graphs in $\S 3.2$. He concludes that the probability that the rank of a random $n$ by $n$ matrix is $n-s$ equals $$ P_{n,s}:=2^{-s^2}\left( \prod_{0\le i\le n-s-1} (1-2^{-(n-i)}) \right)\left(\sum_{0\le i_1\le \cdots \le i_s \le n-s} 2^{-i_1-\cdots-i_s}\right). \ \ (*) $$ This is obtained by building up the matrix row by row. If, after a given number of rows, the space spanned by these rows has dimension $k$, then the next row increases the rank with probability $1-2^{-(n-k)}$, and leaves it unchanged with probability $2^{-(n-k)}$. Assuming that the rank of the full matrix is $n-s$, there must be $n-s$ rows which increase the rank and $s$ which leave it unchanged. Which rows leave it unchanged can be specified by giving the partial ranks of the matrix at the times when these rows are added. If these ranks, in nondecreasing order, are $n-s-i_s$, $n-s-i_{s-1}$, $\dots$, $n-s-i_1$ ($0\le i_1\le\cdots\le i_s\le n-s$), then the probability of getting a rank $n-s$ matrix in this way can be written as the product \begin{eqnarray*} &&(1-2^{-n})(1-2^{-(n-1)})\cdots(1-2^{-(i_s+s+1)})2^{-(i_s+s)}\\ &&(1-2^{-(i_s+s)})(1-2^{-(i_s+s-1)})\cdots(1-2^{-(i_{s-1}+s+1)})2^{-(i_{s-1}+s)}\\ &&\vdots\\ &&(1-2^{-(i_2+s)})(1-2^{-(i_2+s-1)})\cdots(1-2^{-(i_1+s+1)})2^{-(i_1+s)}\\ &&(1-2^{-(i_1+s)})(1-2^{-(i_1+s-1)})\cdots(1-2^{-(s+1)}). \end{eqnarray*} Simplifying the product and summing over $i_1$, $\dots$, $i_s$ yields $(*)$.
If $s=0$, this is easy to see: the $j$th row must always increase the rank from $j-1$ to $j$, which it does with probability $1-2^{-(n-(j-1))}$, so the probability that the matrix is of full rank is $$ P_{n,0}=\prod_{1\le k\le n} (1-2^{-k}). $$ For fixed $s$, as $n$ becomes large, $P_{n,s}$ approaches the limiting value $$ Q_s:=2^{-s^2} \left( \prod_{i\ge s+1} (1-2^{-i}) \right)\left(\prod_{1\le i\le s} (1-2^{-i})^{-1}\right). $$ Numerically, \begin{eqnarray*} Q_0&\approx&0.2887880950866, \qquad \text{(OEIS A048651)}\\ Q_1&\approx&0.5775761901732,\\ Q_2&\approx&0.1283502644829,\\ Q_3&\approx&0.0052387863054,\\ Q_4&\approx&4.656698938156\cdot 10^{-5},\\ Q_5&\approx&9.691360953499\cdot 10^{-8},\\ Q_6&\approx&4.883527817334\cdot 10^{-11},\\ & & \text{and so on}: \end{eqnarray*} the random matrix is very likely to have rank only slightly less than $n$. The expected value of the rank of the matrix will equal $n-\sum_{0\le s\le n} s P_{n,s}$. As $n$ becomes large, this approaches $n-\eta$, where $$ \eta:=\sum_{s\ge 0} s Q_s\approx0.850179830874. $$

If the matrix is over $\Bbb Q$ instead of over ${\Bbb F}_2$, still with entries which are independently chosen and equally likely to be $0$ or $1$, then, when $n$ becomes large, the probability that the matrix has full rank approaches $1$. Bourgain, Vu, and Wood 2009 estimates it as at least $1-(2^{-1/2}+o(1))^n$. (The estimate is stated for random matrices with entries in $\{\pm 1\}$, but it can be transferred to matrices with entries in $\{0,1\}$.) Therefore, as $n$ becomes large, the expected rank approaches $n$. The number of singular rational matrices with a given size and entries in $\{0,1\}$ is OEIS A046747.

$\endgroup$
4
  • $\begingroup$ +1 Interesting. So, when $n$ is large, the rank is most likely $n-1$, not $n$. This is a bit surprising to me. $\endgroup$
    – user1551
    Mar 8, 2013 at 2:42
  • $\begingroup$ I can't believe that nobody found yet a closed formula for the probability that the $0,1$-matrix has full $\mathbb Q$-rank. $\endgroup$ Mar 8, 2013 at 3:44
  • 1
    $\begingroup$ @MatemáticosChibchas, we have to leave something for you to do! $\endgroup$ Mar 8, 2013 at 13:00
  • $\begingroup$ @GerryMyerson What I mean with my comment is that, at first sight, this seems a problem that can be solved via explicit calculations, or in the worst case, via recurrences. Since this problem was kind of a "hot potato" even for a Sith lord like Bourgain, I gracefully give back the task to you ;-) $\endgroup$ Mar 12, 2013 at 23:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .