Invertibility and Condition Number of Sparse Random Matrices

Consider an n by n linear system Ax=b. If the right-hand side of the system is known up to a certain error, then in process of the solution, this error gets amplified by the condition number of the matrix A, i.e. by the ratio of its largest and smallest singular values. This observation led von Neumann and his collaborators to consider the condition number of a random matrix and conjecture that it should be of order n. This conjecture was established in full generality a few years ago. In this talk, we will discus whether von Neumann’s conjecture can be extended to sparse random matrices. We will also discus invertibility of the adjacency matrix of a directed Erdos-Renyi graph. Joint work with Anirban Basak.