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.