The rank of sparse random matrices over finite fields

From MaRDI portal





The \(n\times n\) random matrix \(M\) over \(GF[q]\) is considered. It is assumed that each entry \(M_{ij}\) takes zero value with probability \(1-p\), \(0<p<1\) and that for each element \(\alpha\) of \(\text{GF}[q]\), \[ \text{Prob}\{M_{ij}=\alpha\}={p\over q-1}. \] It is shown that if \(p\) is an arbitrary constant, then the random matrix \(M\) is nonsingular with some positive probability. More formally, it is proved that if \(p=(\log n-c)/n\), then the expected rank of \(M\) is of the order \(n-O(1)\). The probability of the event that the rank is less than \(n-k\) is computed. The asymptotic behaviour of the difference between \(n\) and the rank of \(M\) is studied in the limit \(n\to\infty\).




Cited in
(35)








This page was built for publication: The rank of sparse random matrices over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4345361)