# 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?

• It seems that the smallest singular value $\sigma_n \sim 1/\sqrt{n}$... – Suvrit Jan 25 '14 at 23:40
• @Suvrit Can you give any more details? – Anush Jan 26 '14 at 21:19
• @Anush that is based on just simulations; might be off by logarithmic factors... – Suvrit Feb 2 '14 at 17:38
• I don't think you'll find this question answered in the literature. You might be interested in this paper:arxiv.org/abs/0902.2472 where I considered a related problem for circulant matrices. – Mark Meckes Feb 5 '14 at 8:43
• @MarkMeckes Thank you. I have read your paper with great interest. – Arnold Feb 5 '14 at 9:04