Consider a 0-1 integer $n \times n$ matrix with coefficients chosen uniformly over $\{0,1\}$. The probability that it is singular is exponentially small, and so we expect that it has a well-defined [condition number](http://en.wikipedia.org/wiki/Condition_number).


What is the *expected* condition number — or better yet, what probabilistic upper bounds are there on the condition number (for constant or better probability) — for such a matrix? Equivalently: given that we might naively expect $n/2$ to be close to being an eigenvalue (with the all-1s vector being the eigenvector), what sort of behaviour do we expect of the smallest singular value of a random 0-1 matrix?



Condition number of a random 0-1 matrix
For matrices with i.i.d. cenetered normal entries the condition number was studied by Alan Edelman in [his thesis.](http://math.mit.edu/~edelman/thesis/thesis.pdf) For general subgaussian entries the state of the art is the work of Rudelson and Vershynin, as described in Vershynin's [excellent lecture notes](http://www-personal.umich.edu/~romanv/teaching/2006-07/280/course.html) (I couldn't find a specific result on condition number, but he talks at length of minimal and maximal singular values).


