# Probability of random (0,1) Toeplitz matrix being invertible

A Toeplitz matrix or diagonal-constant matrix is a matrix in which each descending diagonal from left to right is constant.

What is the probability that a random $n \times n$ binary Toeplitz matrix is invertible over $\mathbb{R}$ and what is the probability that it is invertible over $F_2$?

I would be happy with a reference if this turns out to be well known.

-
maybe you should add the "random matrices" tag also – Newbie Apr 28 '13 at 1:18
You probably would like to be more specific about "random". There is no canonical way to choose random elements from R. – Per Alexandersson Apr 30 '13 at 6:46
The matrix is binary (that is it contains only $1$s and $0$s) and is chosen uniformly from the space of all possible $n \times n$ binary Toeplitz matrices. It's the inverse that may contain non-integer values. Do you think I should rephrase the question to make this clearer? – user32786 Apr 30 '13 at 7:22
I added "(0,1)" to the title. Hope you don't mind! – Felix Goldberg Apr 30 '13 at 8:16
marshall: I think it is ok, I read the question too quickly. – Per Alexandersson Apr 30 '13 at 8:18

See: E. Kaltofen and A. Lobo, On rank properties of Toeplitz matrices over finite fields. In Proc. 1996 Internat. Symp. Symbolic Algebraic Comput. (ISSAC'96)

The probability of a random Toeplitz matrix over a finite field of order $q$ being non-singular is $(1-1/q)$. So the answer to your second question is $1/2$.

-
Thanks! I see this result originally came from D. E. Daykin. "Distribution of bordered persymmetric matrices in a finite field". In: Journal fur die reine und angewandte Mathematik 203 (1960), pp. 47–54. – user32786 Apr 28 '13 at 10:17
It does not depend on size n? Hmmm... – Alexander Chervov Apr 28 '13 at 14:05

This is just a partial answer:

Let $A$ be a $N \times N$ Toeplitz matrix, and consider the sequence of matrices $A_n$ for $n>N$ where we increase the size of $A$ to $n\times n$ and the new diagonals are filled with 0. Then the sequence of determinants $|A_n|$ will satisfy a linear recurrence. The zeros in a linear recurrence appears either in arithmetic progressions, or are sporadic. There is an upper bound on the number of sporadic zeros in linear recurrences, and these are "quite rare" in some sense. To have an infinite number of zeros in this sequence of determinants, we require that the symbol of the matrix have roots of unity, (this is sort of the same as the characteristic equation for the linear recurrence). Now, since the matrix is binary, the coefficients of the symbol (a polynomial) are also either 0 or 1.

So, in some sense, the question is related to the probability that a polynomial with coefficients either 0 or 1 has a root of unity.

-