On the rank of a random binary matrix

Colin Cooper¹ ; Alan Frieze² ; Wesley Pegden²

¹Kings College, London
²Carnegie Mellon University

The electronic journal of combinatorics, Tome 26 (2019) no. 4

Résumé

We study the rank of a random $n \times m$ matrix $\mathbf{A}_{n,m;k}$ with entries from $GF(2)$, and exactly $k$ unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all ${n \choose k}$ such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns $m$ in terms of $c,n,k$, and where $m=cn/k$. The matrix $\mathbf{A}_{n,m;k}$ forms the vertex-edge incidence matrix of a $k$-uniform random hypergraph $H$. The rank of $\mathbf{A}_{n,m;k}$ can be expressed as follows. Let $|C_2|$ be the number of vertices of the 2-core of $H$, and $|E(C_2)|$ the number of edges. Let $m^*$ be the value of $m$ for which $|C_2|= |E(C_2)|$. Then w.h.p. for $m<m^*$ the rank of $\mathbf{A}_{n,m;k}$ is asymptotic to $m$, and for $m \ge m^*$ the rank is asymptotic to $m-|E(C_2)|+|C_2|$. In addition, assign i.i.d. $U[0,1]$ weights $X_i, i \in {1,2,...m}$ to the columns, and define the weight of a set of columns $S$ as $X(S)=\sum_{j \in S} X_j$. Define a basis as a set of $n-1 (k\text{ even})$ linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for $k=2$, the expected length of a minimum weight spanning tree tends to $\zeta(3)\sim 1.202$.

Détail

DOI : 10.37236/8092

Classification : 15B52, 05C50, 05C65, 05C80, 15A03, 60C05
Mots-clés : random matrix, trees