On the rank of a random binary matrix
Summary: 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 \(\binom{n}{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,\ldots 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-\mathbb{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 \textit{A. M. Frieze} [Discrete Appl. Math. 10, 47--56 (1985; Zbl 0578.05015)] that, for \(k=2\), the expected length of a minimum weight spanning tree tends to \(\zeta(3)\sim 1.202\).
- Cores in random hypergraphs and Boolean formulas
- Exact expectation and variance of minimal basis of random matroids
- scientific article; zbMATH DE number 1436005 (Why is no real title available?)
- Inclusion of forbidden minors in random representable matroids
- On properties of almost all matroids
- On Random Representable Matroids
- On the cover time of dense graphs
- On the number of matroids
- On the value of a random minimum spanning tree problem
- Probability Inequalities for Sums of Bounded Random Variables
- Random minimum length spanning trees in regular graphs
- The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
- The satisfiability threshold for k-XORSAT
- Sandpile groups of random bipartite graphs
- On the rank of random sparse matrices
- scientific article; zbMATH DE number 5968943 (Why is no real title available?)
- On the rank of random binary matrix with fixed weights of independent rows
- On the rank of a random binary matrix
- Biwhitening Reveals the Rank of a Count Matrix
- The rank of sparse random matrices
- On the rank of a random binary matrix
- On the rank, kernel, and core of sparse random graphs
- The full rank condition for sparse random matrices
- The k-XORSAT threshold revisited (extended abstract)
- The rank of sparse symmetric matrices over arbitrary fields
- Rank deficiency in sparse random \(\mathrm{GF}[2]\) matrices
This page was built for publication: On the rank of a random binary matrix
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2327226)
