Premium
The rank of sparse random matrices over finite fields
Author(s) -
Blömer Johannes,
Karp Richard,
Welzl Emo
Publication year - 1997
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(199707)10:4<407::aid-rsa1>3.0.co;2-y
Subject(s) - mathematics , combinatorics , rank (graph theory) , finite field , zero (linguistics) , matrix (chemical analysis) , constant (computer programming) , random matrix , circular law , discrete mathematics , random variable , statistics , physics , multivariate random variable , computer science , eigenvalues and eigenvectors , philosophy , linguistics , materials science , quantum mechanics , composite material , programming language , sum of normally distributed random variables
Let M be a random ( n × n )‐matrix over GF[ q ] such that for each entry M ij in M and for each nonzero field element α the probability Pr[ M ij =α] is p /( q −1), where p =(log n − c )/ n and c is an arbitrary but fixed positive constant. The probability for a matrix entry to be zero is 1− p . It is shown that the expected rank of M is n −(1). Furthermore, there is a constant A such that the probability that the rank is less than n − k is less than A / q k . It is also shown that if c grows depending on n and is unbounded as n goes to infinity, then the expected difference between the rank of M and n is unbounded. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 407–419, 1997