Abstract | ||
---|---|---|
Let M = (m(ij)) be a random n x 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(mi, 1)= p(n). The probability that the matrix M is nonsingular tends to c(2) approximate to 0.28879 provided min(p. 1 - p) 1 (log n + d(n))ln for any d(n) --> infinity. Sharp thresholds are also obtained for constant d(n. This answers a question posed in a paper by J. Blamer, R. I(arp, and E. Welzl (Random Struct Alg, 10(4) (1997)). (C) 2000 John Wiley & Sons, Inc. |
Year | DOI | Venue |
---|---|---|
2000 | 3.0.CO;2-1" target="_self" class="small-link-text"10.1002/(SICI)1098-2418(200003)16:23.0.CO;2-1 | Random Struct. Algorithms |
Keywords | Field | DocType |
independent and identically distributed,finite field,random matrices | Discrete mathematics,Combinatorics,Matrix (mathematics),struct,Independent and identically distributed random variables,Invertible matrix,Circular law,Mathematics,Random matrix | Journal |
Volume | Issue | ISSN |
16 | 2 | 1042-9832 |
Citations | PageRank | References |
30 | 2.94 | 2 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Colin Cooper | 1 | 287 | 30.73 |