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.