The annihilators of form an ideal of .
To find the minimal polynomial, we need to be given an upper bound on its degree; having done so, the minimal polynomial is uniquely determined by the first elements of (since we need to get equations to solve for the unknowns ).
There is another way to determine the minimal polynomial, originally presented by Dornstetter, which uses the Euclidean Algorithm. It can be shown that the characteristic polynomial of a sequence is the unique monic polynomial of least degree for which the infinite product
has finitely many nonzero terms. (In fact, the nonzero terms will have coefficients up to where is the degree of ).
We can rewrite this as
This is where the Euclidean Algorithm comes in; if we take the GCD of and , keeping track of remainders, we get two sequences such that
forms a series of polynomials whose degree is decreasing; as soon as this degree is less than , we have the needed polynomials with .
There is more info about the Extended Euclidean Algorithm in “Modern Computer Algebra” by von zur Gathen and Gerhard.
(Berlekamp’s algorithm proper to come)
The original algorithm is from Algebraic Coding Theory by Elwyn R. Berlekamp, McGraw-Hill, 1968. Its application to linearly recurrent sequences was noted by J.L.Massey, in “Shift-register synthesis and BCH decoding”, 1969.
|Date of creation||2013-03-22 14:28:55|
|Last modified on||2013-03-22 14:28:55|
|Last modified by||mathcam (2727)|
|Defines||linear recurrent sequence|
|Defines||minimal polynomial of a sequence|