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.

enter image description here

At the risk of asking a really trivial question, is it even obvious how to show that the probability is non-increasing?

  • 1
    $\begingroup$ It seems that the smallest singular value $\sigma_n \sim 1/\sqrt{n}$... $\endgroup$
    – Suvrit
    Jan 25 '14 at 23:40
  • $\begingroup$ @Suvrit Can you give any more details? $\endgroup$
    – Anush
    Jan 26 '14 at 21:19
  • $\begingroup$ @Anush that is based on just simulations; might be off by logarithmic factors... $\endgroup$
    – Suvrit
    Feb 2 '14 at 17:38
  • $\begingroup$ 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. $\endgroup$ Feb 5 '14 at 8:43
  • $\begingroup$ @MarkMeckes Thank you. I have read your paper with great interest. $\endgroup$
    – Arnold
    Feb 5 '14 at 9:04

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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.