On the rank of a random binary matrix

Abstract

We study the rank of the random $n\times m$ 0/1 matrix ${\mathbf{A}}_{n,m;k}$ where each column is chosen independently from the set $\hat{I}{\text{c◯}}_{n,k}$ of 0/1 vectors with exactly $k$ 1's. Here 0/1 are the elements of the field $G{F}_2$. We obtain an asymptotically correct estimate for the rank in terms of $c,n,k$, assuming that $m=cn$. In addition, we assign i.i.d. $U[0,1]$ weights $X_{\mathbf{c}},\mathbf{c}\in \hat{I}{\text{c◯}}_{n,k}$ and let the weight of a set of columns $C$ be $X(C)={\sum }_{\mathbf{c}\in C}{X}_{\mathbf{c}}$. Let a basis be a set of $n-1_{k\text{even}}$ linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight of a basis. This generalises the well-known result for $k=2$ viz. that the expected length of a minimum weight spanning tree tends to $\hat{I}\P (3)$.