On the rank of a random binary matrix

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 ${\mathrm{\Omega }}_{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_{{\bf c}},{\bf c}\in\Omega_{n,k}$andlettheweightofasetofcolumns$C$be$X©=\sum_{{\bf c}\in C}X_{{\bf c}}$\mathrm{.}Letabasisbeasetof$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 $\zeta (3)$.