Лексикографическое упорядочение одночленов многочлена.

Свойства отношения «выше»

В отличие от многочленов от одной переменной многочлен от нескольких переменных может иметь несколько старших членов. Например, многочлен f(x_1, x₂, x₃)=5x₁x₂³x₃-3x₁⁵+2x₁⁴x₂+3х₁⁴х₃+2x₁x₂⁴+3x₂² (deg f =5) имеет 5 старших членов.

Для упорядочения многочленов от нескольких переменных используют следующее правило, которое называется лексикографическим упорядочением:

из двух одночленов u=ax₁^k1x₂^k2...x_n^kn v=bx₁^l1x₂^l2...x_n^ln выше считается тот, у которого показатель при х₁ больше; если k₁=l₁, то выше считается тот, у которого показатель при х₂ больше и т. д.

Упорядочим лексикографически многочлен f(x₁, x₂, x₃):

f(x_1, x₂, x₃)=-3x₁⁵+2x₁⁴x₂+3х₁⁴х₃+2x₁x₂⁴+5x₁x₂³x₃+3x₂².

Если u выше v, то пишут u> v. Также в этом случае говорят, что v ниже u, и пишут v< u.

Свойства отношения «выше»

Лемма 28.1. Oтношение «выше» на множестве всех одночленов из K [ x₁,..., x_n ] является отношением строгого линейного порядка.

Доказательство. 1) Проверим, что отношение «выше» транзитивно. Пусть u> v и v> w. Покажем, что u> w. Пусть u=ax₁^k1x₂^k2...x_n^kn; v=bx₁^l1x₂^l2...x_n^ln; w=cx₁^m1x₂^m2...x_n^mn.

Так как u> v, то $ r Î N, 1 ≤ r ≤ n-1: k_i=l_{i ,} i= и k_r+1> l_r+1.

Так как v> w, то $ s Î N, 1 ≤ s ≤ n-1: l_j=m_{j ,} j= и l_s+1> m_{s+1 .}

Так как r, s Î N, то возможны следующие случаи: либо r< s, либо r³ s.

a) Пусть r< s Þ k_i=l_i=m_i, i= , k_r+1> l_r+1=m_r+1 Þ u> w.

б) Пусть r³ s Þ k_j=l_j=m_j, j= , k_s+1³ l_s+1> m_{s+1 .} (если r=s, то k_s+1³ l_{s+1 ;} если r> s, то r³ s+1 Þ k_s+1=l_s+1) Þ u> w.

Таким образом, отношение «выше»транзитивно.

2) Так как для любого одночлена u из K [ x₁,..., x_n ] u не выше u Þ отношение «выше» антирефлексивно.

3) Из транзитивности и антирефлексивности следует антисимметричность.

Из 1)-3) Þ отношения «выше» являетсяотношением строгого порядка.

4) Так как для любых одночленов u, v из K [ x₁,..., x_n ] из того, что u¹ v Þ либо u> v, либо v> u, то отношение «выше»связано.

Следовательно, из 1)-4) Þ отношение «выше» —отношение строгого линейного порядка. Лемма доказана.

Из леммы 28.1 Þ множество всех одночленов из K [ x₁,..., x_n ]относительно бинарного отношения > является линейно упорядоченным множеством.

Определение 28.1. Пусть f Î K [ x₁,..., x_n ]. Множество всех одночленов многочлена f относительно бинарного отношения > является линейно упорядоченным. Наибольший элемент этого множества называется высшим членом многочлена f.

Высший член f(x₁, x₂, x₃): -3x₁⁵.

Лемма 28.2. Пусть u, v, w - одночлены из K [ x₁,..., x_n ], K — область целостности. Тогда если u> v, то uw> vw.

Доказательство. Пусть u=ax₁^k1x₂^k2...x_n^kn, v=bx₁^l1x₂^l2...x_n^ln, w=cx₁^m1x₂^m2...x_n^mn Þ

uw=acx₁^{k1+ m1}…x_n^kn+mn, vw =bcx₁^{l1+ m1}… x_n^ln+mn.

Так как u> v Þ $ 1 r n- 1, такое, что k_i=l_i, i= , k_r+1> l_r+1 Þ k_i+m_i=l_i+m_{i ,} i= , k_r+1+m_r+1> l_r+1+ m_r+1 Þ uw> vw. Лемма доказана.

Лемма 28.3. Пусть u, v, w, t — ненулевые одночлены из K [ x₁,.., x_n ], K — область целостности. Если u> v, w> t, то uw> vt.

Доказательство. Так как u> v uw> vw. Так как w> t vw> wt. Тогда по лемме 1 uw> vt. Лемма доказана.