×

On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field. (English) Zbl 1242.65074

An explicit count for the number of singular \(n\times n\) Hankel(Toeplitz) matrices whose entries range over a finite field is presented by observing the execution of the Berlekamp/Massey algorithm on its elements.This method yields explicit counts when some entries above or on the anti-diagonal (diagonal) are fixed. Also the count for all \(n\times n\) Hankel matrices of rank \(r\) with generic rank profile is derived.

MSC:

65F30 Other matrix algorithms (MSC2010)
15B05 Toeplitz, Cauchy, and related matrices
15B33 Matrices over special rings (quaternions, finite fields, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Daykin, D. E., Distribution of bordered persymmetric matrices in a finite field, J. Reine Angew. Math., 203, 47-54 (1960) · Zbl 0104.01304
[2] Garcìa-Armas, M.; Ghorpade, S. R.; Ram, S., Relatively prime polynomials and nonsingular hankel matrices over finite fields, J. Combin. Theory Ser. A, 118, 819-828 (2011) · Zbl 1241.11134
[3] Kaltofen, E.; Lee, W.; Giusti, M.; Pardo, L. M., Early termination in sparse interpolation algorithms, Internat. Symp. Symbolic Algebraic Comput. (ISSAC 2002). Internat. Symp. Symbolic Algebraic Comput. (ISSAC 2002), J. Symbolic Comput., 36, 3-4, 365-400 (2003), (special issue) EKbib/03/KL03.pdf · Zbl 1074.68080
[4] Kaltofen, E.; Lobo, A., On rank properties of Toeplitz matrices over finite fields, (Lakshman, Y. N., Proc. 1996 Internat. Symp. Symbolic Algebraic Comput. Proc. 1996 Internat. Symp. Symbolic Algebraic Comput, ISSAC’96 (1996), ACM Press: ACM Press New York, NY), 241-249, URL: EKbib/96/KaLo96_issac.pdf · Zbl 0914.65039
[5] Kaltofen, E., Yuhasz, G., 2006 On the matrix Berlekamp-Massey algorithm. Manuscript, 29 pages (submitted for publication).; Kaltofen, E., Yuhasz, G., 2006 On the matrix Berlekamp-Massey algorithm. Manuscript, 29 pages (submitted for publication). · Zbl 1301.65030
[6] Massey, J. L., Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, it-15, 122-127 (1969) · Zbl 0167.18101
[7] Paturi, R.; Pudlák, P., (Schulman, L. J., On the complexity of circuit satisfiability. On the complexity of circuit satisfiability, STOC (2010), ACM), 241-250 · Zbl 1293.68173
[8] Sugiyama, Y.; Kasahara, M.; Hirasawa, S.; Namekawa, T., A method for solving key equation for decoding Goppa codes, Information & Control, 27, 87-99 (1975) · Zbl 0293.94007
[9] Yuhasz, G., May 2009 Berlekamp/Massey algorithms for linearly generated matrix sequences. Ph.D. Thesis, North Carolina State Univ., Raleigh, North Carolina.; Yuhasz, G., May 2009 Berlekamp/Massey algorithms for linearly generated matrix sequences. Ph.D. Thesis, North Carolina State Univ., Raleigh, North Carolina.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.