10
$\begingroup$

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?

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

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .