Monomiale ordening

In de algebra is een monomiale ordening een bepaald soort welordening op de verzameling monische eentermen in $n$ variabelen over een lichaam (synoniem: veld) $K$.

Verantwoording

Bij het oplossen van stelsels van veeltermvergelijkingen in meer dan een variabele is het vaak nuttig een 'voorkeur' uit te drukken waardoor sommige eentermen als eenvoudiger worden beschouwd dan andere. Het oplossen van het stelsel kan dan worden opgesplitst in stappen, waarbij elke stap leidt tot eenvoudiger veeltermen.

In de praktijk wordt een rangschikking opgelegd aan de monische eentermen, dat zijn producten van machten van de variabelen zonder coëfficiënt of, wat op hetzelfde neerkomt, met coëfficiënt één.

Definitie

Zij $E$ de verzameling van alle monische eentermen in de ring $R=K[x_{1},x_{2},\ldots ,x_{n}]$ van veeltermen met $n$ variabelen en met coëfficiënten in het lichaam $K$. Een monomiale ordening in $R$ is een totale orderelatie < op de verzameling $E$ met de bijkomende eigenschappen dat:

• geen enkele eenterm is kleiner dan de constante eenterm 1
• als $e,f$ en $g$ eentermen zijn, en $e<f$, dan is ook $e\cdot g<f\cdot g$.

Voorbeelden

De lexicografische orde rangschikt eentermen eerste volgens hun graad in de variabele $x_{1}$, daarna, bij gelijke graad in $x_{1}$, volgens hun graad in $x_{2}$, enzovoort. In de lexicografische orde geldt dus

$x_{1}^{2}x_{2}^{6}<x_{1}^{2}x_{2}^{7}<x_{1}^{3}x_{2}^{5}$

Dit zijn ook de eentermen, die in de elementair symmetrische veeltermen voorkomen.

De eerste ongelijkheid geldt omdat $x_{1}$ in beide termen met dezelfde exponent optreedt, namelijk 2, maar $x_{2}$ met een kleinere exponent in de eerste term 6 dan in de tweede term 7. De tweede ongelijkheid geldt omdat de exponenten van $x_{1}$ al verschillend zijn.

De lexicografische orde is een monomiale ordening omdat het een totale orde is. Bij twee verschillende eentermen is er altijd één lexicografische strikt kleiner dan de andere, omdat geen enkele eenterm strikt kleiner is dan de constante 1, die is immers van graad 0 in alle variabelen, en omdat de orderelatie tussen twee eentermen bewaard blijft als men beide eentermen met eenzelfde eenterm vermenigvuldigt. Die bewerking laat namelijk de onderlinge verschillen van de exponenten ongemoeid.

De gegradeerde lexicografische orde rangschikt eentermen eerst volgens hun totale graad in alle variabelen samen, pas bij gelijke totale graad wordt de volgorde bepaald door de gewone lexicografische orde. In de gegradeerde lexicografische orde geldt

$x_{1}^{2}x_{2}^{6}<x_{1}^{3}x_{2}^{5}<x_{1}^{2}x_{2}^{7}$

De eerste ongelijkheid geldt omdat beide eentermen dezelfde totale graad hebben, namelijk 8, waardoor hun volgorde wordt bepaald door de gewone lexicografische orde van hierboven. De tweede ongelijkheid geldt omdat de laatste eenterm totale graad 9 heeft.

De verificatie dat dit een monomiale ordening is, gebeurt net zoals bij de lexicografische orde rechtstreeks aan de hand van de definitie.

De omgekeerde lexicografische orde rangschikt eentermen eerst volgens omgekeerde, dalende volgorde van graad in de laatste variabele, dan de voorlaatste, enzovoort. In de omgekeerde lexicografische orde geldt

$x_{1}^{2}x_{2}^{7}<x_{1}^{2}x_{2}^{6}<x_{1}^{3}x_{2}^{5}$

Beide ongelijkheden worden bepaald door de opeenvolgende exponenten in de tweede variabele, respectievelijk 7, 6 en 5.

De omgekeerde lexicografische orde is zelf geen monomiale ordening omdat de constante eenterm 1 niet kleiner is dan elke andere eenterm, maar zelfs groter dan elke andere eenterm. We gebruiken deze orde echter om een andere monomiale ordening te definiëren:

De 'gegradeerde omgekeerde lexicografische orde' rangschikt eentermen eerst volgens stijgende totale graad in alle variabelen samen. Pas bij gelijke totale graad wordt de volgorde bepaalde door de hierboven gedefinieerde omgekeerde lexicografische orde. In de gegradeerde omgekeerde lexicografische orde geldt

$x_{1}^{2}x_{2}^{6}<x_{1}^{3}x_{2}^{5}<x_{1}^{2}x_{2}^{7}$

De eerste ongelijkheid geldt omdat beide eentermen dezelfde totale graad hebben, namelijk 8, waardoor hun volgorde wordt bepaald door de omgekeerde lexicografische orde van hierboven: de eerste eenterm heeft een hogere exponent in $x_{2}$, namelijk 6, dan de tweede, namelijk 5. De tweede ongelijkheid geldt omdat de laatste eenterm totale graad 9 heeft.

Het is niet toevallig dat onze drie voorbeelden hier in dezelfde volgorde staan als bij de gegradeerde lexicografische orde, pas bij drie of meer variabelen is er een verschil tussen de gegradeerde lexicografische orde en de gegradeerde omgekeerde lexicografische orde.

De definiërende vereisten van een monomiale ordening zijn ook hier niet moeilijk na te gaan. Ditmaal is er geen probleem met de constante eenterm 1 omdat we in eerste instantie naar de totale graad kijken, en die is 0 voor een constante.

Eigenschappen

Een monomiale ordening is een welordening, dat wil zeggen dat iedere, eventueel oneindige, verzameling eentermen een kleinste element bevat.

Men kan in de definitie het vereiste dat 1 het kleinste element is ook vervangen door de eis dat < een welordening is. Immers, als er een eenterm $e<1$ bestaat, en de orde is compatibel met de vermenigvuldiging, dan heeft de oneindige verzameling $\{e,e^{2},e^{3},\ldots \}$ geen kleinste element.

Monomiale ordening op tupels natuurlijke getallen

Er is een bijectie tussen de verzameling monische eentermen in $n$ variabelen en de verzameling $n$-tupels van natuurlijke getallen. Dat is te begrijpen door naar de opeenvolgende exponenten te kijken in alle variabelen. Soms wordt een monomiale ordening dan ook gedefinieerd als een orderelatie op dergelijke $n$-tupels. Die definitie is heel gelijkaardig, behalve dat we er rekening mee houden dat een product van eentermen overeenkomt met een som van exponenten.

Definieer de bewerking + op de machtsverzameling $\mathbb {N} ^{n}$ door componentsgewijs getallen bij elkaar op te tellen

$(a_{1},a_{2},\ldots ,a_{n})+(b_{1},b_{2},\ldots ,b_{n})=(a_{1}+b_{1},a_{2}+b_{2},\ldots ,a_{n}+b_{n})$

Een monomiale ordening op $\mathbb {N} ^{n}$ is een totale orderelatie die $(0,0,...,0)$ als kleinste element heeft en die compatibel is met de optelling van $n$-tupels in de zin dat voor alle $A,B,C\in \mathbb {N}$

$A<B\implies A+C<B+C$

De voorbeelden en eigenschappen hierboven gaan zonder meer over op monomiale ordeningen van $n$-tupels van natuurlijke getallen.

Gebruik

Monomiale ordeningen worden gebruikt bij de definitie van gröbner-basissen, die op hun beurt de sleutel vormen tot het geautomatiseerd oplossen van vraagstukken uit de computeralgebra zoals stelsels veeltermvergelijkingen, eliminatie en extensie.

Voetnoten