10
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ maybe you should add the "random matrices" tag also $\endgroup$
    – Newbie
    Apr 28, 2013 at 1:18
  • 3
    $\begingroup$ You probably would like to be more specific about "random". There is no canonical way to choose random elements from R. $\endgroup$ Apr 30, 2013 at 6:46
  • 2
    $\begingroup$ 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? $\endgroup$
    – user32786
    Apr 30, 2013 at 7:22
  • $\begingroup$ I added "(0,1)" to the title. Hope you don't mind! $\endgroup$ Apr 30, 2013 at 8:16
  • 2
    $\begingroup$ marshall: I think it is ok, I read the question too quickly. $\endgroup$ Apr 30, 2013 at 8:18

2 Answers 2

7
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – user32786
    Apr 28, 2013 at 10:17
  • 2
    $\begingroup$ It does not depend on size n? Hmmm... $\endgroup$ Apr 28, 2013 at 14:05
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.