✦ LIBER ✦

The rank of sparse random matrices over finite fields

✍ Scribed by Johannes Blömer; Richard Karp; Emo Welzl

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 182 KB
Volume: 10
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199707)10:4<407::aid-rsa1>3.0.co;2-y

No coin nor oath required. For personal study only.

✦ Synopsis

Let M be a random n = n -matrix over GF q such that for each entry M in i j w

x Ž . M and for each nonzero field element ␣ the probability Pr M s ␣ is pr q y 1 , where i j

Ž

. p slog n y c rn and c is an arbitrary but fixed positive constant. The probability for a Ž . matrix entry to be zero is 1 y p. It is shown that the expected rank of M is n y O O 1 . Furthermore, there is a constant A such that the probability that the rank is less than n y k is less than Arq 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.

📜 SIMILAR VOLUMES

On the distribution of rank of a random

On the distribution of rank of a random matrix over a finite field

✍ C. Cooper 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB 👁 2 views

On the rank of random matrices

✍ C. Cooper 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 2 views

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