On Rank Properties of Toeplitz Matrices over Finite Fields
Out of all the n×n Toeplitz matrices over a finite field of q elements, a fraction of exactly (1−1/q) is non-singular. Also a fraction of exactly (1/q)(1 − 1/q)(1 − (q − 1)/q) has generic rank 0 < r < n. These statements are proven with the extended Euclidean algorithm and the theory of subresultants. A matrix has generic rank r when all its leading principal minors up to dimension r are non-zero, and r is maximal. Our results have implications to the probability of success of the block Wiedemann linear system solver algorithm, which is an open question at the present time.