On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field

We derive an explicit count for the number of singular n×n$n\times n$ Hankel (Toeplitz) matrices whose entries range over a finite field with q$q$ elements by observing the execution of the Berlekamp/Massey algorithm on its elements. Our method yields explicit counts also when some entries above or on the anti-diagonal (diagonal) are fixed. For example, the number of singular n×n$n\times n$ Toeplitz matrices with 0’s on the diagonal is q²ⁿ⁻³+qⁿ⁻¹−qⁿ⁻²$q^{2n-3}+q^{n-1}-q^{n-2}$.