The rank of sparse random matrices over finite fields
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\).
- The rank of sparse random matrices
- The rank of sparse random matrices
- On the rank of random sparse matrices
- scientific article; zbMATH DE number 3294050
- Properties of sparse random matrices over finite fields
- scientific article; zbMATH DE number 1545673
- Non-asymptotic bounds for probabilities of the rank of a random matrix over a finite field
- Determinants and ranks of random matrices over \({\mathbb{Z}}_ m\)
- Efficient matrix preconditioners for black box linear algebra
- Input locality and hardness amplification
- Rank of near uniform matrices
- Stein's method and the rank distribution of random matrices over finite fields
- The numerical rank of a matrix and its applications
- Elementary divisors and determinants of random matrices over a local field.
- Systems of random equations over finite algebraic structures
- Explicit representation of some coefficients in the expansion of the random matrix rank distribution in the field GF(2)
- A generalization of Komlós's theorem on random matrices
- Random matrix theory over finite fields
- On the distribution of permanents of matrices over finite fields
- On the rank of random sparse matrices
- Properties of sparse random matrices over finite fields
- Limit probabilities for coranks of matrices over GF(q)
- scientific article; zbMATH DE number 1254299 (Why is no real title available?)
- scientific article; zbMATH DE number 597601 (Why is no real title available?)
- Good random matrices over finite fields
- scientific article; zbMATH DE number 1545673 (Why is no real title available?)
- Low-complexity cryptographic hash functions
- scientific article; zbMATH DE number 1436005 (Why is no real title available?)
- Some new results in random matrices over finite fields
- The distribution of sandpile groups of random graphs
- The satisfiability threshold for k-XORSAT
- Non-asymptotic bounds for probabilities of the rank of a random matrix over a finite field
- scientific article; zbMATH DE number 2208904 (Why is no real title available?)
- The rank of sparse random matrices
- Probability theory for random groups arising in number theory
- Singular matrices with restricted rows in vector spaces over finite fields
- The full rank condition for sparse random matrices
- How to verify that a small device is quantum, unconditionally
- Sharp threshold for universality of cokernels of random matrices over finite fields
- Rank deficiency in sparse random \(\mathrm{GF}[2]\) matrices
- Random matrices and codes for the erasure channel
- The rank of a random matrix
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)