CMI Silver Jubilee Lecture Manjunath Krishnapur, IISc, Bangalore How likely is a random matrix to be singular? Monday, March 23, 2015 Abstract: Let A be a random n×n matrix chosen uniformly from the set of all 2^{n2} matrices whose entries are 0 or 1. Let p_{n} be the probability that A is singular. It is an open question to find the asymptotics of p_{n}, although it is believed to asymptotically behave as 2^{-n}. In this lecture I mention this problem, and give a proof due to Komlos that p_{n}→0. This leads us to a very interesting type of problem in probability/additive combinatorics called the Littlewood-Offord problem, and I shall talk about that too. This is an expository lecture for undergraduates. It should be accessible to anyone who knows/can learn what independent Bernoulli random variables are. |