Probability a random Toeplitz matrix is singular Consider Toeplitz matrices where the entries in the first row and column (which define the whole matrix) are independently chosen to be either $1$ or $0$ with probability $1/2$. Define $p_n$ to be the probability that such a uniformly chosen $n$ by $n$ Toeplitz matrix is singular (over $\mathbb{R}$). Is it known that
$$\lim_{n\to \infty} p_n = 0 ?$$
The equivalent question for random Bernoulli matrices was resolved by Komlós (1963).
I see Probability of random (0,1) Toeplitz matrix being invertible where the exact value of $p_n$ was asked for (and with no answer to the part related to my question). 

For $n = 1,\dots,11$ the number of singular matrices is $1,4,13,50,153,522,1648,5173,15047,43892, 123417$.  Sadly this is not in OEIS. The following picture shows the probability that a random $0-1$ Toeplitz matrix  is singular for increasing values of $n$.

Feb 6 2014: Fixed some of the numbers of singular matrices where the determinant was very close to zero.


At the risk of asking a really trivial question, is it even obvious how to show that the probability is non-increasing?
 A: The determinant follows the base-time-height formula, i.e., it is the product of distances from projecting a row to the linear space spanned by its previous rows. This can be understood from the Gram-Schmidt orthogonalization. 
So if the matrix is singular, then one of the distance should be zero. Following this line, one can cast the attempts into the framework established by Terry Tao and Van Vu. For your reference, a link for this reasoning in Terry's blog is "https://terrytao.wordpress.com/2010/03/05/254a-notes-7-the-least-singular-value/".
However, the difference now is that because of the Toeplitz construction, the distances as random variables are dependent. Two bad consequences of this are that concentration inequalities for independent case can no longer be used, and that conditioning on the normal vector of a random hyperplance does not induce independence anymore. This is the key difference. However, if this is uccessfully dealt with, one can substantially advance Tao and Vu's framework and reasoning to dependent case, just as the Green function comparison technique of L. Erdos and HZ Yau has been extended to the dependent case (e.g., covariance/correlation matrix).
A second way can be to see if universality of smallest eigenvalue holds for your Toeplitz matrix and the matrix of Komlós (1963). If it does, then you are done. However, universality on the edge is usually different from that in the bulk, and your case is intrinsically different due to dependence among the entries of the matrix. (I am no expert in this.)
