@article{comer_kaltofen_2012, title={On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field}, volume={47}, ISSN={["0747-7171"]}, DOI={10.1016/j.jsc.2011.09.008}, abstractNote={We derive an explicit count for the number of singular n × 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 × n Toeplitz matrices with 0’s on the diagonal is q 2 n − 3 + q n − 1 − q n − 2 . We also derive the count for all n × 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. ► We count singular square Hankel matrices over a finite field with some entries fixed. Entries may be fixed above or on, or equivalently below or on, the anti-diagonal. ► We count by executing the Berlekamp/Massey algorithm on the matrix entries. ► We also count singular square block-Hankel matrices with generic rank profile.}, number={4}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Comer, Matthew T. and Kaltofen, Erich L.}, year={2012}, month={Apr}, pages={480–491} }