Eine Monomordnung oder Termordnung
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.
definiert den Rest dieser Division eindeutig.
Definition
Eine lineare Ordnung
auf der Menge
![{\displaystyle M:=\{x^{\alpha }=x_{1}^{\alpha _{1}}\cdots x_{n}^{\alpha _{n}}\mid \alpha =(\alpha _{1},\dotsc ,\alpha _{n})\in \mathbb {Z} _{\geq 0}^{n}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d85afd853d6e7f75ff1d4f7f13c3f746397bf690)
der Monome in den Variablen
heißt Monomordnung, falls gilt
(1) Für alle Monome
gilt
![{\displaystyle x^{\alpha }\leq x^{\beta }\Rightarrow x^{\alpha +\gamma }\leq x^{\beta +\gamma }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4710182ff43c7287344c98e568caba1a37e44fab)
(2) Das Monom
ist das kleinste Monom, also
![{\displaystyle \forall x^{\alpha }\in M:1\leq x^{\alpha }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a3a22d87c91bc9bc72c6aea77d99f8137729a06)
Ä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[1] finden sich zum Beispiel:
(2') Die Ordnung
ist eine Wohlordnung
oder auch äquivalenten dazu
(2*) Bezüglich der Ordnung
gibt es keine unendlichen absteigenden Ketten
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
gilt, gibt es nur eine Monomordnung
. Aus der Definition einer Monomordnung folgt nämlich direkt, dass in diesem Fall
sein muss.
(Rein) Lexikalische Ordnung
Bezüglich der lexikalischen oder lexikographischen Ordnung
gilt
genau dann, wenn der am weitesten links stehende, von Null verschiedene Eintrag von
negativ ist. Das heißt, es kann rekursiv definiert werden
![{\displaystyle 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}}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/281067570e44d94a6336b593c8039181c29edc4d)
Totalgradordnung
Die Totalgradordnung oder graduierte lexikalische Ordnung
ist definiert durch
![{\displaystyle 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d98af31f4a9f1715a47d8f566d3c072dfafea7d0)
Grad-revers-lex-Ordnung (Degree reverse lexicographical order)
Hier gilt[2]:
Matrix-Ordnungen
Sei
invertierbar mit der Eigenschaft, dass in jeder Spalte der erste von Null verschiedene Eintrag positiv ist. Dann gilt[3]:
Insbesondere kann man jede beliebige Monomordnung als Matrixordnung in
darstellen. So ergibt sich beispielsweise für die Totalordnung (graduiert lexikographische Ordnung) folgende Matrix:
. Die Grad-revers-lex-Ordnung kann folgendermaßen in eine Matrix umgesetzt werden:
.
Blockordnungen oder Eliminationsordnungen
Jedes Monom
über einer Variablenmenge
kann auf eindeutige Weise in ein Produkt
zerlegt werden, so dass in
nur Variablen aus
und in
nur Variablen aus
vorkommen. Mit dieser Schreibweise wird für gegebene Monomordnungen
und
auf Monomen über den Variablen aus
bzw.
die Blockordnung
auf Monomen in
definiert als
![{\displaystyle m\leq _{x>y}n{\mbox{ genau dann, wenn }}(m_{x}\leq _{x}n_{x}){\mbox{ oder }}(m_{x}=n_{x}{\mbox{ und }}m_{y}\leq _{y}n_{y})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acad6041554981dfb5820856adb2d2346c64eba3)
Begriffe im Zusammenhang mit Polynomen
Eine Monomordnung erlaubt es die Monome in einem Polynom anzuordnen. Für ein Polynom
kann dann zum Beispiel der Multigrad
, der Leitkoeffizient
, das Leitmonom
oder der Leitterm
von
bezüglich der Monomordnung
definiert werden.[4] Es gilt
![{\displaystyle {\mbox{multideg}}_{\leq }(f):=\max _{\alpha \in \mathbb {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)}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27a93569f165b37bfee0985a4dabc46133cbb9f3)
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
.
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.