It can be shown that every m-order on may be obtained as follows.
Let , and let be a set of pairwise orthogonal elements of such that the coordinates of are all nonnegative. (Recall that and are called orthogonal if .) Now define a relation as follows: let and let . We say that if is empty or if is nonempty with minimal element and . It turns out that is an m-order, and that every m-order is equal to for some .
- Let , where if and 0 otherwise. Prove that is the lex order with respect to .
- Let , where for all and if , if , if , and 0 otherwise for . Prove that is the grevlex order with respect to .
- First we will show that the elements of are pairwise orthogonal. To that end, suppose , and consider . If , then . If , then , and if , then . Thus as desired.
Now suppose . If is empty, then in fact for all . Now , and likewise . So . Suppose instead that is nonempty with minimal element . Then for all , we have , and . Thus with respect to the lex order.
Now suppose with respect to the lex order. If for all , we have for all , so that for all . Thus . Otherwise, if is minimal such that , we have . In fact, , and thus .
- First we will show that the elements of are pairwise orthoigonal. To that end, suppose and consider . Without loss of generality, there are two cases. If , then we have . If , then .
Now we show that this is equivalent to the natural grlex order.
Suppose . If is empty, then we have for all . We claim that . To see this, we proceed by induction on the entries in reverse order. For the base case, since , we have . Since , we have . Subtracting one equation from the other, we see that , and thus . Suppose now that for all . Since , we have . Again subtracting from , we see that , so that . So for all , we easily see that from . Thus , and so with respect to the grlex order. Supppose instead that is nonempty with minimal element . Then for all , and . If , then we see that , so that has greater total degree than b$. If , then and have the same total degree. By an adaptation of the induction proof we used above, we see that for all . Moreover, we have ; subtracting from , we see that , and since , . Thus with respect to the natural grevlex order.
Conversely, suppose with respect to the natural grevlex order. If , then , and so . Suppose instead that and that is maximal such that (and for all ). Certainly we have . Again by a straightforward induction argument, we have for all . Finally, since , we have , so that , and thus . Hence .