Home
Resource
On the probability that a discrete complex random matrix is singular
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(581.21 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Wood, Philip J.. On the probability that a discrete complex random matrix is singular. Retrieved from https://doi.org/doi:10.7282/T3CC10WB

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleOn the probability that a discrete complex random matrix is singular
NameWood, Philip J. (author); Vu, Van (chair); Kahn, Jeff (internal member); Komlos, Janos (internal member); Frieze, Alan (outside member); Rutgers University; Graduate School - New Brunswick
Date Created
Other Date2009-05 (degree)
SubjectMathematics, Matrices, Combinatorial analysis
Extentviii, 84 p. : ill.
DescriptionLet n be a large integer and M_n be an n by n complex matrix whose entries are independent (but not necessarily identically distributed) discrete random variables. The main goal of this thesis is to prove a general upper bound for the probability that M_n is singular.
For a constant 0 < p < 1 and a constant positive integer r, we will define a property p-bounded of exponent r. Our main result shows that if the entries of M_n satisfy this
property, then the probability that M_n is singular is at most (p^(1/r) + o(1) )^n. All of the results in this thesis hold for any characteristic zero integral domain replacing the complex numbers.
In the special case where the entries of M_n are "fair coin flips" (taking the values +1, -1 each with probability 1/2), our general bound implies that the probability that
Mn is singular is at most (1/[square root]2 + o(1))^n, improving on the previous best upper bound of (3/4 + o(1))^n, proved by Tao and Vu in 2007.
In the special case where the entries of M_n are "lazy coin flips" (taking values +1, -1 each with probability 1/4 and value 0 with probability 1/2), our general bound implies that the probability that M_n is singular is at most (1/2 + o(1))^n, which is asymptotically sharp.
Our method is a refinement of those from Kahn, Komlos, and Szemeredi in 1995 and Tao and Vu in 2007. In particular, we make a critical use of the Structure Theorem from Tao and Vu in 2007, which was obtained using tools from additive combinatorics.
One key lemma for extending our results to the complex numbers follows from a more general result about characteristic zero integral domains. We show that any
finite system S in a characteristic zero integral domain can be mapped to Z/QZ, for infinitely many primes Q, preserving all algebraic incidences in S . This can be seen as a generalization of the well-known Freiman isomorphism lemma, which asserts that any finite subset of a torsion-free group can be mapped into Z/QZ, preserving all linear incidences.
As applications, we derive several combinatorial results (such as sum-product estimates) for a finite set in a characteristic zero integral domain. As C is a characteristic zero integral domain, this allows us to obtain new proofs for some recent results concerning finite sets of complex numbers, without relying on the topology of the plane.
NotePh.D.
NoteIncludes bibliographical references (p. 80-82)
Noteby Philip J. Wood
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3CC10WB
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameNjNbRU
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024