A note on the rank of a sparse random matrix

2019/11/21 by Cooper, Colin, Frieze, Alan, Pegden, Wesley
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1911.09597

Abstract

Let A_n,m;k be a random n × m matrix with entries from some field \mathbbF where there are exactly k non-zero entries in each column, whose locations are chosen independently and uniformly at random from the set of all n \choose k possibilities. In a previous paper (arXiv:1806.04988), we considered the rank of a random matrix in this model when the field is \mathbbF=GF(2). In this note, we point out that with minimal modifications, the arguments from that paper actually allow analogous results when the field \mathbbF is arbitrary. In particular, for any field \mathbbF and any fixed k≥ 3, we determine an asymptotically correct estimate for the rank of A_n,m;k in terms of c,n,k where m=cn/k, and c is a constant. This formula works even when the values of the nonzero elements are adversarially chosen. When \mathbbF is a finite field, we also determine the threshold for having full row rank, when the values of the nonzero elements are randomly chosen.

Related

• The rank of sparse random matrices
• On the rank of random matrices over finite fields
• The full rank condition for sparse random matrices
• Rank of Near Uniform Matrices
• On the rank of a random binary matrix