Chennai Mathematical Institute

Silver Jubilee Events

CMI Silver Jubilee Lecture

Manjunath Krishnapur, IISc, Bangalore

How likely is a random matrix to be singular?

Monday, March 23, 2015


Let A be a random n×n matrix chosen uniformly from the set of all 2n2 matrices whose entries are 0 or 1. Let pn be the probability that A is singular. It is an open question to find the asymptotics of pn, 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 pn→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.