Monomordnung

Eine Monomordnung oder Termordnung $\leq$ ist eine lineare Ordnung auf der Menge der Monome über einer endlichen Variablenmenge. Monomordnungen werden zur Definition der Division mit Rest von Polynomen in mehreren Variablen benötigt. Eine Gröbnerbasis bzgl. $\leq$ definiert den Rest dieser Division eindeutig.

Definition

Eine lineare Ordnung $\leq$ auf der Menge

M := {x^{α} = x_{1}^{α_{1}} \dots x_{n}^{α_{n}} ∣ α = (α_{1}, \dots, α_{n}) \in ℤ_{\geq 0}^{n}}

der Monome in den Variablen $x_{1}, \dots, x_{n}$ heißt Monomordnung, falls gilt

(1) Für alle Monome $x^{α}, x^{β}, x^{γ} \in M$ gilt

x^{α} \leq x^{β} \Rightarrow x^{α + γ} \leq x^{β + γ}

(2) Das Monom $1$ ist das kleinste Monom, also

\forall x^{α} \in M : 1 \leq x^{α}

Äquivalente Definitionen

Es sind auch andere äquivalente Definitionen üblich. So ist es etwa möglich die Bedingung (2) durch eine andere Bedingung auszutauschen. In der Literatur finden sich zum Beispiel:

(2') Die Ordnung $\leq$ ist eine Wohlordnung

oder auch äquivalenten dazu

(2*) Bezüglich der Ordnung $\leq$ gibt es keine unendlichen absteigenden Ketten $x^{α_{1}} > x^{α_{2}} > x^{α_{3}} > \dots$ von Monomen.

Die Eigenschaft (2*) ist Grundlage vieler Terminierungsbeweise für Algorithmen im Zusammenhang mit Gröbnerbasen.

Beispiele für Monomordnungen

Monome in einer Variablen

Falls wir nur eine Variable haben, also $n = 1$ gilt, gibt es nur eine Monomordnung $\leq$ . Aus der Definition einer Monomordnung folgt nämlich direkt, dass in diesem Fall $1 = x^{0} \leq x^{1} \leq x^{2} \leq \dots$ sein muss.

(Rein) Lexikalische Ordnung

Bezüglich der lexikalischen oder lexikographischen Ordnung $\leq_{l e x}$ gilt $x^{α} \leq_{l e x} x^{β}$ genau dann, wenn der am weitesten links stehende, von Null verschiedene Eintrag von $α - β$ negativ ist. Das heißt, es kann rekursiv definiert werden

x^{α} \leq_{l e x} x^{β} \Leftrightarrow (α_{1} < β_{1}) oder (α_{1} = β_{1} und x_{2}^{α_{2}} \dots x_{n}^{α_{n}} \leq_{l e x} x_{2}^{β_{2}} \dots x_{n}^{β_{n}}) .

Totalgradordnung

Die Totalgradordnung oder graduierte lexikalische Ordnung $\leq_{t d e g}$ ist definiert durch

x_{1}^{e_{1}} \dots x_{n}^{e_{n}} \leq_{t d e g} x_{1}^{f_{1}} \dots x_{n}^{f_{n}} \Leftrightarrow (\sum_{i = 1}^{n} e_{i} < \sum_{i = 1}^{n} f_{i}) oder (\sum_{i = 1}^{n} e_{i} = \sum_{i = 1}^{n} f_{i} und x_{1}^{e_{1}} \dots x_{n}^{e_{n}} \leq_{l e x} x_{1}^{f_{1}} \dots x_{n}^{f_{n}})

Grad-revers-lex-Ordnung (Degree reverse lexicographical order)

Hier gilt:

$x_{1}^{e_{1}} \dots x_{n}^{e_{n}} \leq_{d e g r e v l e x} x_{1}^{f_{1}} \dots x_{n}^{f_{n}} \Leftrightarrow (\sum_{i = 1}^{n} e_{i} < \sum_{i = 1}^{n} f_{i}) oder (\sum_{i = 1}^{n} e_{i} = \sum_{i = 1}^{n} f_{i} und f_{j} \leq e_{j} für j = m a x {i : e_{i} \neq f_{i}})$

Matrix-Ordnungen

Sei $A \in ℤ^{n \times n}$ invertierbar mit der Eigenschaft, dass in jeder Spalte der erste von Null verschiedene Eintrag positiv ist. Dann gilt:

$x^{α} \leq_{A} x^{β} \Leftrightarrow (A α \leq_{l e x} A β) .$

Insbesondere kann man jede beliebige Monomordnung als Matrixordnung in $ℝ^{n \times n}$ darstellen. So ergibt sich beispielsweise für die Totalordnung (graduiert lexikographische Ordnung) folgende Matrix: $(\begin{matrix} 1 & 1 & ... & 1 & 1 \\ 1 & 0 & ... & 0 & 0 \\ 0 & 1 & ... & 0 & 0 \\ ... & ... & ... & ... & ... \\ 0 & 0 & ... & 1 & 0 \end{matrix})$ . Die Grad-revers-lex-Ordnung kann folgendermaßen in eine Matrix umgesetzt werden: $(\begin{matrix} 1 & 1 & ... & 1 & 1 \\ 0 & 0 & ... & 0 & - 1 \\ 0 & 0 & ... & - 1 & 0 \\ ... & ... & ... & ... & ... \\ 0 & - 1 & ... & 0 & 0 \end{matrix})$ .

Blockordnungen oder Eliminationsordnungen

Jedes Monom $m$ über einer Variablenmenge $X \cup Y$ kann auf eindeutige Weise in ein Produkt $m_{x} m_{y}$ zerlegt werden, so dass in $m_{x}$ nur Variablen aus $X$ und in $m_{y}$ nur Variablen aus $Y$ vorkommen. Mit dieser Schreibweise wird für gegebene Monomordnungen $\leq_{x}$ und $\leq_{y}$ auf Monomen über den Variablen aus $X$ bzw. $Y$ die Blockordnung $\leq_{x > y}$ auf Monomen in $X \cup Y$ definiert als

m \leq_{x > y} n genau dann, wenn (m_{x} <_{x} n_{x}) oder (m_{x} = n_{x} und m_{y} \leq_{y} n_{y})

Begriffe im Zusammenhang mit Polynomen

Eine Monomordnung erlaubt es die Monome in einem Polynom anzuordnen. Für ein Polynom $f (x) = \sum_{α} a_{α} x^{α} \in k [x] = k [x_{1}, \dots, x_{n}]$ kann dann zum Beispiel der Multigrad ${multideg}_{\leq} (f)$ , der Leitkoeffizient ${LC}_{\leq} (f)$ , das Leitmonom ${LM}_{\leq} (f)$ oder der Leitterm ${LT}_{\leq} (f)$ von $f$ bezüglich der Monomordnung $\leq$ definiert werden. Es gilt

{multideg}_{\leq} (f) := max_{α \in ℤ_{\geq 0}^{n}, a_{α} \neq 0} α, {LC}_{\leq} (f) := a_{{multideg}_{\leq} (f)}, {LM}_{\leq} (f) := x^{{multideg}_{\leq} (f)}, {LT}_{\leq} (f) := {LC}_{\leq} (f) {LM}_{\leq} (f) = a_{{multideg}_{\leq} (f)} x^{{multideg}_{\leq} (f)} .

Für den Polynomring in einer Variablen ergeben sich daraus die üblichen Definitionen für den Grad des Polynoms, seinen Leitkoeffizienten und seinen Leitterm.

Literatur

T. Becker, V. Weispfenning: Gröbner Bases, a computational approach to commutative algebra. Springer-Verlag, 1993, ISBN 3-540-97971-9.
David A. Cox, John B. Little, Donal O’Shea: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra (= Undergraduate Texts in Mathematics). 3. Auflage. Springer, New York 2007, ISBN 978-0-387-35650-1, 2.2. Orderings on the Monomials in $k [x_{1}, \dots, x_{n}]$ .

Einzelnachweise

↑ D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 1, Lemma 2.
↑ Winfried Bruns: Computer-Algebra. (PDF) Abgerufen am 31. Juli 2019.
↑ M. Roczen, H. Wolter, W. Pohl, D. Popescu, R. Laza: Lineare Algebra individuell – Kapitel 2: Algebraische Gleichungen. (PDF) Abgerufen am 31. Juli 2019.
↑ D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 7.

[1] D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 1, Lemma 2.

[2] Winfried Bruns: Computer-Algebra. (PDF) Abgerufen am 31. Juli 2019.

[3] M. Roczen, H. Wolter, W. Pohl, D. Popescu, R. Laza: Lineare Algebra individuell – Kapitel 2: Algebraische Gleichungen. (PDF) Abgerufen am 31. Juli 2019.

[4] D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 7.