Paper Info
Title
On the rank of a random binary matrix.
Abstract
We study the rank of a random n × m matrix An,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 (nk) 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 An,m;k forms the vertex-edge incidence matrix of a k-uniform random hypergraph H. The rank of An,m;k can be expressed as follows. Let |C2| be the number of vertices of the 2-core of H, and |E(C2)| the number of edges. Let m* be the value of m for which |C2| = |E(C2)|. Then w.h.p. for m < m* the rank of An,m;k is asymptotic to m, and for m ≥ m* the rank is asymptotic to m − |E(C2)| + |C2|. In addition, assign i.i.d. U[0, 1] weights Xi,i ∈ 1, 2, ... m to the columns, and define the weight of a set of columns S as X(S) = Σj∈SXj. Define a basis as a set of n − 1 (k 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 ζ(3) ~ 1.202.
Year
DOI
Venue
2019
10.5555/3310435.3310493
SODA '19: Symposium on Discrete Algorithms San Diego California January, 2019
Field
DocType
Citations 
Discrete mathematics,Combinatorics,Linear independence,Logical matrix,Matrix (mathematics),Omega,Minimum weight,Spanning tree,Mathematics
Conference
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Colin Cooper185791.88
Alan M. Frieze24837787.00
wesley pegden33011.07