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

详细信息	查看全文 | 推荐本文 |

• 作者：Matthew T. Comer ^{mcomer@ncsu.edu} ; Erich L. Kaltofen ^{kaltofen@math.ncsu.edu}
• 关键词：Toeplitz matrix ; Hankel matrix ; Block matrix ; Finite field ; Singularity counts ; Fixed entry ; Berlekamp/Massey algorithm
• 刊名：Journal of Symbolic Computation
• 出版年：2012
• 期刊代码：140_07477171
• 类别：cp
• 出版时间：April, 2012
• 卷：47
• 期：4
• 页码：480-491
• 文件大小：288 K

摘要

We derive an explicit count for the number of singular Hankel (Toeplitz) matrices whose entries range over a finite field with 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 Toeplitz matrices with 0鈥檚 on the diagonal is .

We also derive the count for all Hankel matrices of rank with generic rank profile, i.e., whose first leading principal submatrices are non-singular and the rest are singular, namely in the case and in the case . This result generalizes to block-Hankel matrices as well.