Friday, October 16, 2020 12:30 PM
Yuval Wigderson (Stanford)

Abstract:  What is the probability that a random square matrix is invertible? If the matrix is drawn from one of the "usual" ensembles, then this probability is 1, since these ensembles have a continuous distribution and the space of singular matrices has Lebesgue measure 0. However, this question gets interesting if we draw our matrix from some discrete ensemble, such as having every entry be +1 or −1 with probability 1/2 independently. This question has a long and storied history, including being (essentially) completely solved by Tikhomirov about two years ago. In this talk, I'll prove a theorem of Komlós, saying that such matrices are invertible with probability 1−o(1). Along the way, we'll encounter the theory of anticoncentration, tools from which are still integral in the study of this and related problems.