On the rank of random sparse matrices

DOI10.1017/S0963548309990447MaRDI QIDQ3058294zbMATH OpenOpenAlexFDO

Authors Kevin P. Costello, Van Vu

Publication date 19 November 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.2696

zbMATH Keywords

Bernoulli random variablescomplex symmetric matrixmatrix co-rankrandom sparse matricesrank

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: We investigate the rank of random (symmetric) sparse matrices. Our main finding is that with high probability, any dependency that occurs in such a matrix is formed by a set of few rows that contains an overwhelming number of zeros. This allows us to obtain an exact estimate for the co-rank.

Recommendations

• scientific article; zbMATH DE number 1436005
• On the rank of a random binary matrix
• The rank of sparse random matrices over finite fields
• On the rank of a random binary matrix
• A theorem on the distribution of the rank of a sparse Boolean random matrix and some applications

Cites work

• Estimates for the concentration function of combinatorial number theory and probability
• On a lemma of Littlewood and Offord
• Random symmetric matrices are almost surely nonsingular.
• The rank of random graphs

Cited in

(24)

• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• Recent progress in combinatorial random matrix theory
• Rank deficiency of random matrices
• On sparse random combinatorial matrices
• On the rank of a random binary matrix
• Norms of random submatrices and sparse approximation
• On asymptotic properties of the rank of a special random adjacency matrix
• On the universality of the non-singularity of general Ginibre and Wigner random matrices
• scientific article; zbMATH DE number 5994989 (Why is no real title available?)
• Hitting Time Theorems for Random Matrices
• Properties of sparse random matrices over finite fields
• Componentwise Condition Numbers of Random Sparse Matrices
• The rank of random graphs
• The rank of sparse random matrices over finite fields
• On the rank of a random binary matrix
• Singularity of sparse random matrices: simple proofs
• Singularity of the \(k\)-core of a random graph
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• The rank of sparse random matrices
• On the rank, kernel, and core of sparse random graphs
• The full rank condition for sparse random matrices
• The rank of sparse symmetric matrices over arbitrary fields
• Resolution of the quadratic Littlewood-Offord problem
• Rank deficiency in sparse random \(\mathrm{GF}[2]\) matrices

This page was built for publication: On the rank of random sparse matrices

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