Premium
On the rank of random matrices
Author(s) -
Cooper C.
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(200003)16:2<209::aid-rsa6>3.0.co;2-1
Subject(s) - struct , invertible matrix , combinatorics , mathematics , rank (graph theory) , circular law , matrix (chemical analysis) , independent and identically distributed random variables , random matrix , constant (computer programming) , random variable , physics , statistics , pure mathematics , computer science , chemistry , quantum mechanics , eigenvalues and eigenvectors , chromatography , sum of normally distributed random variables , programming language
Let M =( m ij ) be a random n × n matrix over GF (2). Each matrix entry m ij is independently and identically distributed, with Pr( m ij =0)=1− p ( n ) and Pr( m ij =1)= p ( n ). The probability that the matrix M is nonsingular tends to c 2 ≈0.28879 provided min( p , 1− p )≥(log n + d ( n ))/ n for any d ( n )→∞. Sharp thresholds are also obtained for constant d ( n ). This answers a question posed in a paper by J. Blömer, R. Karp, and E. Welzl (Random Struct Alg, 10(4) (1997)). ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 209–232, 2000