Polynomial Orderings

The leading term of a polynomial can be chosen in many different ways. For multivariate polynomials, sorting by the total degree of the monomials is often useful.

Different representations of polynomials.

Here is a polynomial in three variables:

poly=-10x^5y^4z^2+7x^2y^5z^3-10x^2y z^5-7x y^5z^4+6x y^4z^3+6x y^3z^3+3x y^2z+y^4z-7y^2z+2z^5

This is the list of the monomials:

MonomialList[poly,{x,y,z}]

This is the list of the monomials represented as exponent vectors and coefficients:

CoefficientRules[poly,{x,y,z}]

The first vector corresponds to (x^5) (y^4)(z^2):

MemberQ[poly,-10x^5y^4z^2]

(RefLink[FromCoefficientRules, paclet:ref/FromCoefficientRules]) constructs the original polynomial from the list of rules and variables:

FromCoefficientRules[CoefficientRules[poly,{x,y,z}],{x,y,z}]==poly

If the second argument to (RefLink[MonomialList, paclet:ref/MonomialList]) or (RefLink[CoefficientRules, paclet:ref/CoefficientRules]) is omitted, the variables are taken in the order in which they are returned by the function (RefLink[Variables, paclet:ref/Variables]).

The list of the variables is not always sorted:

Variables[poly]

Now the first vector corresponds to (y^5) (z^4)x:

CoefficientRules[poly]

MemberQ[poly,-7y^5z^4x]

By default, the monomials are sorted lexicographically and given in the decreasing order. In the previous example, {5,4,1} (corresponding to (y^5) (z^4)x) is taken to precede {5,3,2} (corresponding to (y^5) (z^3)(x^2)) by the second element.

An order is described by defining how two vectors of exponents ((Subscript[α, 1]),…,(Subscript[α, n])) and ((Subscript[β, 1]),…,(Subscript[β, n])) are sorted. For the lexicographic order,

((Subscript[α, 1]),…,(Subscript[α, n]))≻((Subscript[β, 1]),…,(Subscript[β, n]))⇔(Subscript[∃, i,1≤i≤n])((Subscript[α, 1])==(Subscript[β, 1])∧…∧(Subscript[α, i-1])==(Subscript[β, i-1])∧(Subscript[α, i])>(Subscript[β, i])).

An order can also be described by giving a weight matrix. In that case the exponent vectors are multiplied by the weight matrix and the results are sorted lexicographically, also in the decreasing order. The matrices for different orderings are given as follows.

Weight matrices corresponding to different orderings.

For functions such as (RefLink[GroebnerBasis, paclet:ref/GroebnerBasis]) and (RefLink[PolynomialReduce, paclet:ref/PolynomialReduce]), it is necessary that the order be well-founded, which ensures that any decreasing sequence of elements is finite (the elements being the vectors of non-negative exponents). In order for that condition to hold, the first nonzero value in each column of the weight matrix must be positive.

The default sorting used for polynomial terms in an expression corresponds to the negative lexicographic ordering with variables sorted in the reversed order. This is commonly known as reverse lexicographic ordering.

This is the internal representation of a polynomial. The arguments of (RefLink[Plus, paclet:ref/Plus]) and (RefLink[Times, paclet:ref/Times]) are sorted on evaluation:

y x+x//FullForm

This is the sorted list of terms:

List@@(y x+x)

This is the reverse lexicographic order in variables {x,y,z}:

MonomialList[poly,Reverse[{x,y,z}],"NegativeLexicographic"]

This is the same order specified by a weight matrix:

MonomialList[poly,{x,y,z},{{0,0,-1},{0,-1,0},{-1,0,0}}]

The result is identical to the automatically sorted list of terms in poly:

%==List@@poly

(RefLink[TraditionalForm, paclet:ref/TraditionalForm]) tries to arrange the terms in an order close to the lexicographic ordering.

The polynomial displayed in (RefLink[TraditionalForm, paclet:ref/TraditionalForm]):

poly//TraditionalForm

This uses advanced typesetting capabilities to obtain the list of terms in the same order as they appear in the (RefLink[TraditionalForm, paclet:ref/TraditionalForm]) output:

ToExpression[RowBox/@Partition[Prepend[ToBoxes[poly,TraditionalForm][[1,1]],"+"],2]]

The result agrees with the list of the monomials given in the default (lexicographic) order:

%==MonomialList[poly,{x,y,z}]

The option ParameterVariables tells (RefLink[TraditionalForm, paclet:ref/TraditionalForm]) which variables should be excluded from the ordering.

By default, the list of independent variables is assumed to be {a,b,x}:

TraditionalForm[x^3+a x+b]

Here x is assumed to be the only variable:

TraditionalForm[x^3+a x+b,ParameterVariables:>{a,b}]

One can obtain additional orderings from the six orderings used in (RefLink[MonomialList, paclet:ref/MonomialList]) simply by reversing the resulting list. This is effectively equivalent to negating the exponent vectors. In a commutative setting, one can also obtain other orderings by reversing the order of the variables.

This diagram illustrates the relations between various orderings. Red lines indicate reversing the list of variables and blue lines indicate negating the power vectors.