On the Rank of Random Sparse Matrices

DOI10.1017/S0963548309990447zbMATH Open1204.15042arXiv0711.2696OpenAlexW2117991835MaRDI QIDQ3058294FDOQ3058294

Van Vu, Kevin P. Costello

Publication date: 19 November 2010

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

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.

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

zbMATH Keywords

rankBernoulli random variablescomplex symmetric matrixrandom sparse matricesmatrix co-rank

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (17)

• Singularity of the \(k\)-core of a random graph
• Rank deficiency of random matrices
• Singularity of sparse random matrices: simple proofs
• Hitting Time Theorems for Random Matrices
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• On the universality of the non-singularity of general Ginibre and Wigner random matrices
• Title not available (Why is that?)
• Recent progress in combinatorial random matrix theory
• The rank of random graphs
• The rank of sparse random matrices over finite fields
• On sparse random combinatorial matrices
• On the rank, kernel, and core of sparse random graphs
• Norms of random submatrices and sparse approximation
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Properties of sparse random matrices over finite fields
• Componentwise Condition Numbers of Random Sparse Matrices
• The rank of sparse random 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)