A [Toeplitz matrix](http://en.wikipedia.org/wiki/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.



Probability of random (0,1) Toeplitz matrix being invertible
See: E. Kaltofen and A. Lobo, [On rank properties of Toeplitz matrices over finite fields](http://www4.ncsu.edu/~kaltofen/bibliography/96/KaLo96_issac.pdf). 
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$.


