Loading [MathJax]/extensions/TeX/mathchoice.js
previous contents next

21.4 Минимальный многочлен и аннулятор.

Определение 21.15:
Характерестический многочлен минимальной степени называют минимальным многочленом лиейной рекуррентной последовательности, а его степень рангом этой последовательности.
Ранг линейной рекуррентной последовательности u обозначают ranku.

Пример 21.10:
Минимальный многочлен может быть не единственен. Например, пусть R=Z4, для любого iN0 u(i)=2, тогда x1 и x3 являются минимальными многочленами ЛРП u.

Определение 21.16:
Аннулятором линейной рекуррентной последовательности uαR называется множество многочленов An(u)R[x] аннулирующих последовательность u, то есть An(u):={F(x)R[x]F(x)u=0}.

Замечание 21.3:

  1. Из определения следует, что в аннуляторе An(u) лежат все характеристические многочлены ЛРП u, а так же все неунитарные многочлены аннулирующие u.
  2. Из утверждения 21.4 и теоремы 21.2 следует, что для любой ЛРП uαR An(u)R[x].

Теорема 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)mdegG(x)=m(deg(F(x)G(x))<mF(x)G(x)F(x)P[x])F(x)G(x)=0G(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, где rk0 и (r(x)eF)(mk1)=r0eF(mk1)+r1eF(mk)++rkeF(m1)=rkeF(m1)=rk0 Получено противоречие с утвержденим r(x)eF=0, следовательно, k=0, r(x)=0.

Утверждение 21.7:
Пусть P - поле.

  1. Если uαP, H(x)P[x], v:=H(x)u, тогда mv(x)=mu(x)(mu(x),H(x)).
  2. Если последовательноси u,vαP имеют взаимнопростые характеристические многочлены, то mu+v(x)=mu(x)mv(x).

Доказательство:

  1. Для любого F(x)P[x] F(x)v=0F(x)H(x)u=0mu(x)|F(x)H(x)mu(x)(mu(x),H(x))|F(x).
  2. Так как над полем минимальный многочлен делит любой характерестический, то (mu(x),mv(x))=e, тогда по теореме 21.3 LP(mumv)=LP(mu)LP(mv). Тогда для любого F(x)P[x] F(x)(u+v)=0F(x)u+F(x)v=0(F(x)u=0F(x)v=0)(mu(x)|F(x)mv(x)|F(x))mu(x)mv(x)|F(x).

Следствие 21.5:
Если P - поле, uLP(F), Φ(x) - генератор последовательности u, то mu(x)=F(x)(F(x),Φ(x)).

Доказательство:

Так как u=Φ(x)eF, то утверждение следует из п. 1 утверждения 21.7.

Практические способы нахождения минимального многочлена ЛРП над полем.

Если для ЛРП u известен характеристический многочлен F(x)=fmxm+fm1xm1++f1x+f0, то

  1. по формуле Φ(x)=m1k=0(u(k)+fm1u(k1)++fmku(0))xmk1 находим генератор последовательности u;
  2. по следствию 21.5 находим минимальный многочлен, как mu(x)=F(x)(F(x),Φ(x)).

Утверждение 21.8: Метод нахождения минимального многочлена с помощью решения гангелевой СЛУ.
Пусть P - поле, последовательность uαP имеет ранг m.

  1. Многочлен F(x)=xmcm1xm1f1xf0P[x] является характеристическим многочленом последовательности u тогда и только тогда, когда (c0,c1,,cm1)T является решением системы линейных уравнений (u(0)u(1)u(m1)u(1)u(2)u(m)u(m1)u(m)u(2m2))x=(u(m)u(m+1)u(2m1))(1)
  2. Если ранг u равен r, то система линейных уравнений (u(0)u(1)u(r1)u(1)u(2)u(r)u(r1)u(r)u(2r2))x=(u(r)u(r+1)u(2r1))(2) имеет единственное решение и если (a0,a1,,ar1)T решение системы (2), то mu(x)=xrar1xr1a1xa0.
  3. Если ранг u равен r, то ранг матрицы U=(u(0)u(1)u(r1)u(1)u(2)u(r)u(r1)u(r)u(2r2)) равен r и минор M_U\binom{1,2,\ldots,r\:}{1,2,\ldots,r\:} является ранговым.


  1. \Rightarrow) Пусть F(x)=x^m-c_{m-1}x^{m-1}-\cdots-c_1x-c_0 характеристический многочлен ЛРП u, тогда для любого i\in\mathbb{N}_0 u(i+m)=c_{m-1}u(i+m-1)+\cdots+c_0u(i), в частности это равенство выполняется для любого i\in\overline{1,m-1}, то есть (c_0,c_1,\ldots,c_{m-1})^T является решением СЛУ (1).
    \Leftarrow) По п.1 следствия 21.4 ЛРП v:=F(x)u имеет тот же ранг и тот же характеристический многочлен что и ЛРП u. Если (c_0,c_1,\ldots,c_{m-1})^T решение СЛУ (1), тогда для любого i\in\overline{1,m-1} u(i+m)=c_{m-1}u(i+m-1)+\cdots+c_0u(i), то есть для любого i\in\overline{1,m-1} v(i)=0. Тогда, так как {\deg{v}=\deg{u}=m}, то v=0, то есть F(x)u=0 и по утверждению 21.4 u\in{L}_P(F).
  2. Следует из пункта 1 и единственности минимального многочлена над полем.
  3. Так как \rank{u}=r, то u имеет характеристический многочлен степени r. Тогда все столбцы матрицы U начиная с r+1-вого ЛВЧ первые r, то есть \rang{U}\leq{r}. С другой стороны, по пункту 2 СЛУ (2) имеет единственное решение, то есть ее матрица равная M_U\binom{1,2,\ldots,r\:}{1,2,\ldots,r\:} обратима. Значит \rang{U}=r и M_U\binom{1,2,\ldots,r\:}{1,2,\ldots,r\:}\neq0.


previous contents next