Monomordnung

Eine Monomordnung oder Termordnung ${\displaystyle \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. ${\displaystyle \leq }$ definiert den Rest dieser Division eindeutig.

Definition

Eine lineare Ordnung ${\displaystyle \leq }$ 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}\}}$

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

(1) Für alle Monome ${\displaystyle x^{\alpha },x^{\beta },x^{\gamma }\in M}$ gilt

${\displaystyle x^{\alpha }\leq x^{\beta }\Rightarrow x^{\alpha +\gamma }\leq x^{\beta +\gamma }}$

(2) Das Monom ${\displaystyle 1}$ ist das kleinste Monom, also

${\displaystyle \forall x^{\alpha }\in M:1\leq x^{\alpha }}$

Äquivalente Definitionen

Es s​ind auch andere äquivalente Definitionen üblich. So i​st es e​twa möglich d​ie Bedingung (2) d​urch eine andere Bedingung auszutauschen. In d​er Literatur[1] finden s​ich zum Beispiel:

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

oder a​uch äquivalenten dazu

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

Die Eigenschaft (2*) i​st Grundlage vieler Terminierungsbeweise für Algorithmen i​m Zusammenhang m​it Gröbnerbasen.

Beispiele für Monomordnungen

Monome in einer Variablen

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

(Rein) Lexikalische Ordnung

Bezüglich der lexikalischen oder lexikographischen Ordnung ${\displaystyle \leq _{\mathrm {lex} }}$ gilt ${\displaystyle x^{\alpha }\leq _{\mathrm {lex} }x^{\beta }}$ genau dann, wenn der am weitesten links stehende, von Null verschiedene Eintrag von ${\displaystyle \alpha -\beta }$ 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}}).}$

Totalgradordnung

Die Totalgradordnung oder graduierte lexikalische Ordnung ${\displaystyle \leq _{\mathrm {tdeg} }}$ 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)}$

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

Hier gilt[2]:

${\displaystyle 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)}$

Matrix-Ordnungen

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

${\displaystyle x^{\alpha }\leq _{\mathrm {A} }x^{\beta }\Leftrightarrow (A\alpha \leq _{\mathrm {lex} }A\beta ).}$

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

Blockordnungen oder Eliminationsordnungen

Jedes Monom ${\displaystyle m}$ über einer Variablenmenge ${\displaystyle X\cup Y}$ kann auf eindeutige Weise in ein Produkt ${\displaystyle m_{x}m_{y}}$ zerlegt werden, so dass in ${\displaystyle m_{x}}$ nur Variablen aus ${\displaystyle X}$ und in ${\displaystyle m_{y}}$ nur Variablen aus ${\displaystyle Y}$ vorkommen. Mit dieser Schreibweise wird für gegebene Monomordnungen ${\displaystyle \leq _{x}}$ und ${\displaystyle \leq _{y}}$ auf Monomen über den Variablen aus ${\displaystyle X}$ bzw. ${\displaystyle Y}$ die Blockordnung ${\displaystyle \leq _{x>y}}$ auf Monomen in ${\displaystyle X\cup Y}$ 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})}$

Begriffe im Zusammenhang mit Polynomen

Eine Monomordnung erlaubt es die Monome in einem Polynom anzuordnen. Für ein Polynom ${\displaystyle f(x)=\sum _{\alpha }a_{\alpha }x^{\alpha }\in k[x]=k[x_{1},\dotsc ,x_{n}]}$ kann dann zum Beispiel der Multigrad ${\displaystyle {\mbox{multideg}}_{\leq }(f)}$, der Leitkoeffizient ${\displaystyle {\mbox{LC}}_{\leq }(f)}$, das Leitmonom ${\displaystyle {\mbox{LM}}_{\leq }(f)}$ oder der Leitterm ${\displaystyle {\mbox{LT}}_{\leq }(f)}$ von ${\displaystyle f}$ bezüglich der Monomordnung ${\displaystyle \leq }$ 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)}.}$

Für d​en Polynomring i​n einer Variablen ergeben s​ich daraus d​ie üblichen Definitionen für d​en Grad d​es Polynoms, seinen Leitkoeffizienten u​nd 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 ${\displaystyle k[x_{1},\dotsc ,x_{n}]}$.

Einzelnachweise

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.