Singularity Probabilities for Random Matrices over Finite Fields

Jeff Kahn; János Komlós

doi:10.1017/S096354830100462X

Singularity Probabilities for Random Matrices over Finite Fields

Jeff Kahn, János Komlós

School of Arts and Sciences, Mathematics

Research output: Contribution to journal › Article › peer-review

16 Scopus citations

Abstract

Fix q and let M_n be an n x n matrix with entries drawn independently from the finite field F_q according to some distribution μ_n. It is shown that, except in certain pathological cases, the probability that M_n is nonsingular is asymptotically the same as for uniform entries; that is, Pr(M_n is nonsingular) Π_i≥1 (1 - q^-i) as n → ∞.

Original language	English (US)
Pages (from-to)	137-157
Number of pages	21
Journal	Combinatorics Probability and Computing
Volume	10
Issue number	2
DOIs	https://doi.org/10.1017/S096354830100462X
State	Published - 2001

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S096354830100462X

Cite this

@article{05d60115ca6d4291ad16f6b4b7eeed17,

title = "Singularity Probabilities for Random Matrices over Finite Fields",

abstract = "Fix q and let Mn be an n x n matrix with entries drawn independently from the finite field Fq according to some distribution μn. It is shown that, except in certain pathological cases, the probability that Mn is nonsingular is asymptotically the same as for uniform entries; that is, Pr(Mn is nonsingular) Πi≥1 (1 - q-i) as n → ∞.",

author = "Jeff Kahn and J{\'a}nos Koml{\'o}s",

year = "2001",

doi = "10.1017/S096354830100462X",

language = "English (US)",

volume = "10",

pages = "137--157",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "2",

}

TY - JOUR

T1 - Singularity Probabilities for Random Matrices over Finite Fields

AU - Kahn, Jeff

AU - Komlós, János

PY - 2001

Y1 - 2001

N2 - Fix q and let Mn be an n x n matrix with entries drawn independently from the finite field Fq according to some distribution μn. It is shown that, except in certain pathological cases, the probability that Mn is nonsingular is asymptotically the same as for uniform entries; that is, Pr(Mn is nonsingular) Πi≥1 (1 - q-i) as n → ∞.

AB - Fix q and let Mn be an n x n matrix with entries drawn independently from the finite field Fq according to some distribution μn. It is shown that, except in certain pathological cases, the probability that Mn is nonsingular is asymptotically the same as for uniform entries; that is, Pr(Mn is nonsingular) Πi≥1 (1 - q-i) as n → ∞.

UR - http://www.scopus.com/inward/record.url?scp=0035589436&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035589436&partnerID=8YFLogxK

U2 - 10.1017/S096354830100462X

DO - 10.1017/S096354830100462X

M3 - Article

AN - SCOPUS:0035589436

VL - 10

SP - 137

EP - 157

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

IS - 2

ER -

Singularity Probabilities for Random Matrices over Finite Fields

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this