Определение 21.15:
Характерестический многочлен минимальной степени называют минимальным многочленом лиейной рекуррентной последовательности,
а его степень рангом этой последовательности.
Ранг линейной рекуррентной последовательности u обозначают ranku.
Пример 21.10:
Минимальный многочлен может быть не единственен. Например, пусть R=Z4, для любого i∈N0 u(i)=2,
тогда x−1 и x−3 являются минимальными многочленами ЛРП u.
Определение 21.16:
Аннулятором линейной рекуррентной последовательности u∈αR∞ называется множество многочленов An(u)⊂R[x]
аннулирующих последовательность u, то есть
An(u):={F(x)∈R[x]∣F(x)u=0}.
Замечание 21.3:
Теорема 21.6:
Линейная рекуррентная последовательность над полем имеет единственный минимальный многочлен и любой характеристический многочлен делится на минимальный.
Доказательство:
Пусть P - поле, u∈αP∞. Так как An(u)⊲P[x], то по следствию 17.6
существует единственный унитарный многочлен F(x) такой, что An(u)=F(x)P[x]. Следовательно,
F(x) имеет минимальную степень в An(u) и делит любой многочлен из An(u).
Замечание 21.4:
Если u - ЛРП над полем, то ее минимальный многочлен обозначают mu(x).
Утверждение 21.5:
Унитарный многочлен F(x)∈R[x] является единственным минимальным многочленом последовательности u∈αR∞,
тогда и только тогда когда An(u)=F(x)R[x].
(Последовательность u∈αR∞ имеет единственный минимальный многочлен тогда и только тогда, когда An(u) главный идеал кольца R[x].)
Доказательство:
⇒) Из утверждения 21.4 и теоремы 21.2
следует, что F(x)R[x]⊂Au(u). Докажем обратное включение. Пусть G(x)∈Au(u) и m:=degF(x). Разделим G(x) на F(x) с остатком, тогда
∃Q(x),r(x)∈R[x]:(G(x)=F(x)Q(x)+r(x)∧degr(x)<m)⇒r(x)=G(x)−F(x)Q(x)∈Au(u)⇒(F(x)+r(x)∈Au(x)∧deg(F(x)+r(x))=m).
Многочлен F(x)+r(x) унитарен, следовательно, он минимальный для ЛРП u, тогда из единственности минимального следует, что F(x)+r(x)=F(x),
то есть r(x)=0. Таким образом, F(x)|G(x), следовательно, G(x)∈F(x)P[x].
⇐) Пусть G(x) - минимальный многочлен ЛРП u, тогда в силу унитарности F(x) и G(x)
G(x)∈F(x)P[x]⇒F(x)|G(x)⇒degG(x)≥m⇒degG(x)=m⇒(deg(F(x)−G(x))<m∧F(x)−G(x)∈F(x)P[x])⇒F(x)−G(x)=0⇒G(x)=F(x).
Утверждение 21.6:
Пусть многочлен F(x)∈R[x] унитарен, тогда последовательность eF∈αR∞ имеет единственный минимальный многочлен F(x) и
An(eF)=F(x)R[x].
Доказательство:
Так как F(x)eF=0, то F(x)P[x]⊂An(eF), докажем обратное включение. Пусть m:=degF(x) и G(x)∈An(eF).
Разделим G(x) на F(x), тогда
∃Q(x),r(x)∈R[x]:(G(x)=F(x)Q(x)+r(x)∧k:=degr(x)<m)⇒r(x)eF=(G(x)−F(x)Q(x))eF=0
Предположим, что k>0 и обозначим r(x):=rkxk+⋯+r1x+r0, где rk≠0 и
(r(x)eF)(m−k−1)=r0eF(m−k−1)+r1eF(m−k)+⋯+rkeF(m−1)=rkeF(m−1)=rk≠0
Получено противоречие с утвержденим r(x)eF=0, следовательно, k=0, r(x)=0.
Утверждение 21.7:
Пусть P - поле.
Доказательство:
Следствие 21.5:
Если P - поле, u∈LP(F), Φ(x) - генератор последовательности u, то mu(x)=F(x)(F(x),Φ(x)).
Доказательство:
Так как u=Φ(x)eF, то утверждение следует из п. 1 утверждения 21.7.
Практические способы нахождения минимального многочлена ЛРП над полем.
Если для ЛРП u известен характеристический многочлен
F(x)=fmxm+fm−1xm−1+⋯+f1x+f0,
то
Утверждение 21.8: Метод нахождения минимального многочлена с помощью решения гангелевой СЛУ.
Пусть P - поле, последовательность u∈αP∞ имеет ранг m.