Monomordnung

Eine Monomordnung oder Termordnung <math>\leq</math> 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. <math>\leq</math> definiert den Rest dieser Division eindeutig.

Definition

Eine lineare Ordnung <math>\leq</math> auf der Menge

<math>M := \{ x^\alpha=x_1^{\alpha_1}\cdots x_n^{\alpha_n} \mid \alpha=(\alpha_1,\dotsc,\alpha_n)\in \Z_{\geq 0}^n\} </math>

der Monome in den Variablen <math>x_1,\dots,x_n</math> heißt Monomordnung, falls gilt

(1) Für alle Monome <math>x^\alpha, x^\beta, x^\gamma \in M</math> gilt

<math>x^\alpha \leq x^\beta \Rightarrow x^{\alpha+\gamma} \leq x^{\beta+\gamma}</math>

(2) Das Monom <math>1</math> ist das kleinste Monom, also

<math>\forall x^\alpha \in M: 1 \leq x^\alpha</math>

Ä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<ref>D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 1, Lemma 2.</ref> finden sich zum Beispiel:

(2') Die Ordnung <math>\leq </math> ist eine Wohlordnung

oder auch äquivalenten dazu

(2*) Bezüglich der Ordnung <math>\leq</math> gibt es keine unendlichen absteigenden Ketten <math>x^{\alpha_1}> x^{\alpha_2} > x^{\alpha_3} > \cdots</math> 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 <math>n=1</math> gilt, gibt es nur eine Monomordnung <math>\leq </math>. Aus der Definition einer Monomordnung folgt nämlich direkt, dass in diesem Fall <math>1=x^0\leq x^1\leq x^2\leq \dotsc</math> sein muss.

(Rein) Lexikalische Ordnung

Bezüglich der lexikalischen oder lexikographischen Ordnung <math>\leq_\mathrm{lex}</math> gilt <math> x^\alpha \leq_\mathrm{lex} x^\beta </math> genau dann, wenn der am weitesten links stehende, von Null verschiedene Eintrag von <math>\alpha-\beta </math> negativ ist. Das heißt, es kann rekursiv definiert werden

<math> x^\alpha \leq_\mathrm{lex} x^\beta\Leftrightarrow (\alpha_1 < \beta_1)\mbox{ oder }(\alpha_1 = \beta_1\mbox{ und } x_2^{\alpha_2}\cdots x_n^{\alpha_n} \leq_\mathrm{lex} x_2^{\beta_2}\cdots x_n^{\beta_n}).</math>

Totalgradordnung

Die Totalgradordnung oder graduierte lexikalische Ordnung <math>\leq_\mathrm{tdeg}</math> ist definiert durch

<math>x_1^{e_1}\cdots x_n^{e_n} \leq_\mathrm{tdeg} x_1^{f_1}\cdots x_n^{f_n} \Leftrightarrow\left(\sum_{i=1}^n e_i < \sum_{i=1}^n f_i\right)\mbox{ oder }\left(\sum_{i=1}^n e_i = \sum_{i=1}^n f_i\mbox{ und } x_1^{e_1}\cdots x_n^{e_n} \leq_\mathrm{lex} x_1^{f_1}\cdots x_n^{f_n}\right)</math>

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

Hier gilt<ref>Winfried Bruns: Computer-Algebra. (PDF) Abgerufen am 31. Juli 2019. </ref>:

<math>x_1^{e_1}\cdots x_n^{e_n} \leq_\mathrm{degrevlex} x_1^{f_1}\cdots x_n^{f_n} \Leftrightarrow\left(\sum_{i=1}^n e_i < \sum_{i=1}^n f_i\right)\mbox{ oder }\left(\sum_{i=1}^n e_i = \sum_{i=1}^n f_i\mbox{ und } f_j\leq e_j \mbox{ für } j = max \{i: e_i\neq f_i\}\right)</math>

Matrix-Ordnungen

Sei <math>A \in \Z^{n \times n}</math>invertierbar mit der Eigenschaft, dass in jeder Spalte der erste von Null verschiedene Eintrag positiv ist. Dann gilt<ref>M. Roczen, H. Wolter, W. Pohl, D. Popescu, R. Laza: Lineare Algebra individuell – Kapitel 2: Algebraische Gleichungen. (PDF) Abgerufen am 31. Juli 2019. </ref>:

<math> x^\alpha \leq_\mathrm{A} x^\beta\Leftrightarrow (A\alpha \leq_\mathrm{lex} A\beta).</math>

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

Blockordnungen oder Eliminationsordnungen

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

<math>m \leq_{x > y} n \mbox{ genau dann, wenn }(m_x <_x n_x)\mbox{ oder }

(m_x = n_x\mbox{ und } m_y \leq_y n_y)</math>

Begriffe im Zusammenhang mit Polynomen

Eine Monomordnung erlaubt es die Monome in einem Polynom anzuordnen. Für ein Polynom <math>f(x)=\sum_\alpha a_\alpha x^\alpha \in k[x]=k[x_1,\dotsc,x_n]</math> kann dann zum Beispiel der Multigrad <math>\mbox{multideg}_\leq(f)</math>, der Leitkoeffizient <math>\mbox{LC}_\leq(f)</math>, das Leitmonom <math>\mbox{LM}_\leq(f)</math> oder der Leitterm <math>\mbox{LT}_\leq(f)</math> von <math>f</math> bezüglich der Monomordnung <math>\leq </math> definiert werden.<ref>D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 7.</ref> Es gilt

<math>\mbox{multideg}_\leq(f):= \max_{\alpha\in \Z_{\geq 0}^n, a_\alpha\neq 0} \alpha,\quad \mbox{LC}_\leq(f):= a_{\mbox{multideg}_\leq(f)}, \quad\mbox{LM}_\leq(f):= x^{\mbox{multideg}_\leq(f)}, \quad\mbox{LT}_\leq(f):= \mbox{LC}_\leq(f)\mbox{LM}_\leq(f)= a_{\mbox{multideg}_\leq(f)}x^{\mbox{multideg}_\leq(f)}.</math>

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 <math>k[x_1,\dotsc,x_n]</math>.

Einzelnachweise