The asymptotic probability that a random biased matrix is invertible

✍ Scribed by Leonard S. Charlap; Howard D. Rees; David P. Robbins

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 589 KB
• Volume: 82
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(90)90322-9

✦ Synopsis

Let q =pe be a power of a prime. Suppose we are given a probability distribution on GF(q) not concentrated on any proper affine subspace of GF(q) regarded as a vector space over its prime subfield GF(p).

Let M be a random n by n matrix whose entries are chosen independently from the given distribution and let A, be the probability that M is invertible. We show that

1. Introduction

Let F = GF(q) be a finite field where q =pe is a power of a prime p. Fix a probability distribution on F. By a random n by IZ matrix we mean a matrix whose entries are chosen independently according to our distribution. Let A,, be the probability that a random IZ by n matrix is invertible. If this distribution is the uniform distribution, so that every field element is chosen with the same probability l/q, then it is known that A, is given by the product

l+(I-f)(l--$)...(l-$)

and that P, converges to the limit P= fi (l--$).

k=l

In this paper we will show that, with mild restrictions on the probability distribution on F, we have lim A, = P.

IZ--

Thus, for large matrices, the probability that a matrix is invertible is approximately independent of the distribution on F.