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 x n Hankel (Toeplitz) matrices whose entries range over a finite field with 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 x n Toeplitz matrices with O's on the diagonal is q(2n-3) + q(n-1) - q(n-2) We also derive the count for all n x n Hankel matrices of rank r with generic rank profile, i.e., whose first r leading principal submatrices are non-singular and the rest are singular, namely q(r) (q-1)(r) in the case r < n and q(r-1) (q-1)(r) in the case r = n. This result generalizes to block-Hankel matrices as well. (C) 2011 Elsevier Ltd. All rights reserved.
berlekamp/massey algorithm finite field toeplitz matrix hankel matrix block matrix singularity counts fixed entry