On the singularity of random combinatorial matrices

DOI10.1137/110853157MaRDI QIDQ5300505zbMATH OpenOpenAlexFDO

Authors Hoi Nguyen

Publication date 27 June 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Bernoulli random variablesLittlewood-Offord estimatenon-singular matrixrandom combinatorial matrixsingularity probability

Mathematics Subject Classification ID

Arithmetic combinatorics; higher degree uniformity (11B30) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: It is shown that a random $(0,1)$ matrix whose rows are independent random vectors of exactly $n/2$ zero components is non-singular with probability $1-O(n^{-C})$ for any $C>0$. The proof uses a non-standard inverse-type Littlewood-Offord result.

Recommendations

• On the singularity of random matrices with independent entries
• On the singularity of random \((0,1,\dots,K)\)-matrices
• Singularity of sparse random matrices: simple proofs
• Singularity of random Bernoulli matrices
• scientific article; zbMATH DE number 1436005

Cited in

(28)

• On the singularity probability of discrete random matrices
• On the nonsingularity of principal submatrices of a random orthogonal matrix
• Recent progress in combinatorial random matrix theory
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Singularity of discrete random matrices
• On sparse random combinatorial matrices
• Adjacency matrices of random digraphs: singularity and anti-concentration
• Quantitative invertibility of random matrices: a combinatorial perspective
• On the singularity probability of random Bernoulli matrices
• On the singularity of random matrices with independent entries
• Efficient generation of random nonsingular matrices
• On the Probability That a Random ± 1-Matrix Is Singular
• scientific article; zbMATH DE number 1436005 (Why is no real title available?)
• Surjectivity of near-square random matrices
• On the counting problem in inverse Littlewood-Offord theory
• Polynomial threshold functions, hyperplane arrangements, and random tensors
• A random matrix approach to the Peterson-Thom conjecture
• On the singularity of adjacency matrices for random regular digraphs
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• On the singularity of random \((0,1,\dots,K)\)-matrices
• Singular 0/1-Matrices, and the Hyperplanes Spanned by Random 0/1-Vectors
• Singularity of sparse random matrices: simple proofs
• Row coincidences in nonsingular binary matrices
• Singularity of the \(k\)-core of a random graph
• A note on the singularity probability of random directed \(d\)-regular graphs
• The singularity probability of a random symmetric matrix is exponentially small
• The rank of random regular digraphs of constant degree
• An upper bound on the smallest singular value of dense random combinatorial matrices

This page was built for publication: On the singularity of random combinatorial matrices

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