How many ways are there to represent a monomial order by term order via matrices? During the lecture, my professor brought up a list of project ideas to work on. One of the ideas I am interested and currently working on is term order via matrices. That is: I need to find the number of ways to order $n$-tuples with matrices in any type of orders. Here is the problem:
$$\Large\textbf{Problem}$$
Let $>$ be a monomial ordering and $A$ be the following $m$-by-$n$ matrix:
$$\begin{pmatrix}
a_{11} & \cdots & a_{1m}\\
\vdots & \ddots & \vdots\\
a_{n1} & \cdots & a_{nm}
\end{pmatrix}$$
such that the integers $m,n > 0$ and $a_{ij} \in \mathbb{R}$ for $1 \leq i \leq n$ and $1 \leq j \leq m$.  Define $>_A$ by
$$\overline{a} = (a_1, \dots, a_n) > _A \overline{b} = (b_1, \dots, b_n)\text{ iff }\overline{a}A > \overline{b}A.$$
How many ways are there to represent a monomial order by term order via matrices?  Determine conditions such that $>_A$ defines a monomial ordering.

$$\Large\textbf{My Current List of Term Orders Via Matrices}$$
Let $\overline{a} = (a_1, \dots, a_n)$ and $\overline{b} = (b_1, \dots, b_n)$ for each of the following orders.  Here are my results:
$$\large\textbf{Lexicographic Order}$$


*

*If $A = I$, then clearly $>_A$ is $>_{\text{lex}}$.

*$A = (1, \dots, 1)^T$ is the column matrix consisting of $n$ $1$'s, such that $\overline{a}A$ and $\overline{b}A$ exist.


Next parts are not easy.  I found few of them.
$$\large\textbf{Degree Lexicographic Order}$$


*

*$A$ is the following $n$-by-$m$ matrix:
$$A = \begin{pmatrix}
1 & 1 & \cdots & 1 & 1\\
1 & 0 & 0 & \cdots & 0\\
0 & 1 & 0 & \cdots & 0\\
\vdots & 0 & \ddots & 0 & 0\\
0 & \vdots & 0 & 1 & 0\\
0 & 0 & \vdots & 0 & 1
\end{pmatrix}$$
So if $\overline{a} > \overline{b}$, then $\overline{a}A >_{\text{deglex}} \overline{b}A$.

*If $A$ is the following square $n$-by-$n$ matrix
$$A = \begin{pmatrix}
1 & 1 & \cdots & 1 & 1\\
1 & 0 & 0 & \cdots & 0\\
0 & 1 & 0 & \cdots & 0\\
\vdots & 0 & \ddots & 0 & 0\\
0 & \cdots & 0 & 1 & 0
\end{pmatrix}$$
then $>_A$ is $>_{\text{deglex}}$

*$A = (1, \dots, 1)^T$ might work for this order.


$$\large\textbf{Degree Reversed Lexicographic Order}$$
 1. If $A$ is the following $m$-by-$n$ matrix
$$\begin{pmatrix}
1 & 1 & \cdots & 1 & 1\\
0 & 0 & \cdots & 0 & -1\\
0 & \cdots & 0 & -1 & 0\\
\vdots & 0 & \kern3mu\raise1mu{.}\kern3mu\raise6mu{.}\kern3mu\raise12mu{.} & 0 & \vdots\\
0 & -1 & 0 & \vdots & 0\\
-1 & 0 & \cdots & 0 & 0
\end{pmatrix}$$
Then, $>_A$ is $>_{\text{degrev}}$.


*If $A$ is the following $n$-by-$m$ matrix
$$\begin{pmatrix}
1 & 1 & \cdots & 1 & 1\\
0 & 0 & \cdots & 0 & -1\\
0 & \cdots & 0 & -1 & 0\\
\vdots & 0 & \kern3mu\raise1mu{.}\kern3mu\raise6mu{.}\kern3mu\raise12mu{.} & 0 & \vdots\\
0 & -1 & 0 & \cdots & 0
\end{pmatrix}$$
Then, $>_A$ is also $>_{\text{degrev}}$.

*I think that $A = (1,\dots,1)^T$ also works for this order.


$$\large\textbf{Inverse Lexicographic Order}$$
Same list of term orders via matrices as lexicographic order list.

$$\Large\textbf{Results and Thoughts}$$
After hours of investigating the number of ways to represent types of order via matrices, I took down the following conditions I believe may be correct:


*

*Given $\overline{a} = (a_1, \dots,a_n)$, in order for $\overline{a}A$ to be defined, we need the row of a matrix $A$ to corresponds with the column of $\overline{a}$.

*In order to specify the order by matrices, each term in $\overline{a}$ must be multiplied by each nonzero term in the matrix $A$.  Otherwise, the ordering of the tuples is not defined very well.  In other words, for this case, if $\overline{a} >_A \overline{b}$, then we can't conclude that $\overline{a}A > \overline{b}A$ for an ordering $>$.


I believe the list of matrix-orderings I have is not enough; there might be more types of matrix-ordering that works for orders, like $\text{lex}$, $\text{deglex}$ and $\text{invlex}$, that I haven't figured out yet.
Any comments or thoughts you have for the problem I am working on?  I exhausted lots of tries to determine the number of matrix-orderings.
 A: The following definition can be found in D. Cox, J. Little, D. O'Shea "Ideals, Varieties and Algorithms":
A monomial ordering > on $k[x_1,...,x_n]$ is any relation > on $\mathbb{Z}^n_{\geqslant 0}$, satisfying:
1) > is a total (or linear) ordering on $\mathbb{Z}^n_{\geqslant 0}$.
2) If $\alpha > \beta$ and $\gamma \in \mathbb{Z}^n_{\geqslant 0}$, then $\alpha + \gamma > \beta + \gamma$.
3) > is a well-ordering on $\mathbb{Z}^n_{\geqslant 0}$. This means that every nonempty subset of $\mathbb{Z}^n_{\geqslant 0}$ has a smallest element under >.
Usually the definition of a monomial ordering defined by a matrix is as follows:
Let $x^\alpha$ and $x^\beta$ be monomials in $k[x_1,...,x_n]$ and $A \in \mathbb{R}^{m \times n}$. We say $x^\alpha >_A x^\beta$ if $A \alpha >_{lex} A \beta$.
When you try to define any monomial ordering via matrix-vector multiplication obviously there should be some restrictions on matrix $A$.
The situation is quite clear when $A \in \mathbb{Z}^{m \times n}$ is a matrix of full row rank. The second condition in the definition above (the condition of compatibility with addition) is automatically satisfied. When $m \geqslant n$ the first condition is satisfied as well. Finally $>_A$ is a well-ordering when the first row of matrix $A$ has all its entries positive.
Moreover L. Robbiano has shown that all monomial orders on $k[x_1,...,x_n]$ can be obtained in this fashion.
However, when $A \in \mathbb{R}^{m \times n}$ the situation becomes less predictable. For example, if $A = (1,\sqrt{2})$, then $>_A$ is a monomial ordering on $k[x,y]$.
The full answer to you question is quite cumbersome, so I suggest you to check the following literature for more:
1) D. Cox, J. Little, D. O'Shea "Using Algebraic Geometry" (Chapter 1, paragraph 2).
2) L. Robbiano "Term orderings on the polynomial ring", in: Proceedings  of EUROCAL 1985, Lecture Notes in Computer Science 204.
