2

I just want to know what the difference between graded lex and graded reverse lex is. For example, if we have \begin{equation} f=3x^4 y - 2x^2 y^3 z + 7x^2 y z^3 - x^3 y^2 z + z^3 y^3 - 6x^3 yz^2 \end{equation}

I know that if we have a graded rev lex with z>x>y we have that the lead term (LT) of $f$ will be $7x^2 y z^3$, what would LT$(f)$ be with graded lex?

tellap
  • 161

2 Answers2

1

Both are graded, so for both you choose the largest total degree first, the lex and revlex stuff is only used if you need to break a tie.

If $y < x < z$ then for lex you look at the variables in the order $z \to x \to y$ (largest to smallest) and choose the largest degree, moving on to the next variable if you need to break a tie. So among those terms with total degree $6$ (the largest) we choose $7x^2yz^3$ because we look at $z$ first and choose the term with the largest $z$-degree.

If we still have $y < x < z$ then for revlex you look at the variables in the order $y \to x \to z$ (smallest to largest) and you choose the smallest degree, moving on to the next variable if you need to break a tie. So among those terms with total degree $6$ we would take $\mathrm{LT}(f) = 7x^2yz^3$ because the smallest $y$-degree you can get is $1$, and of the two monomials that have that $y$-degree the smallest $x$-degree you can get is $2$.

It's a little funny because the leading term comes out to be the same. To see one that comes out different let $f = x^2 + zy$. Keep $y < x < z$. Then with graded lex we have $\mathrm{LT}(f) = yz$ and with graded revlex we have $\mathrm{LT}(f) = x^2$.

To keep them straight think that the "l" in lex is for large, and reverse large is small, so:

  • lex $\to$ largest variable first, take largest degree
  • revlex $\to$ smallest variable first, take smallest degree
Jim
  • 30,682
  • Ok I think I get what you're saying. So say for example if I were to apply gr lex on $f$ then we would get $7x^2 y z^3 - 6x^3 yz^2 - x^3 y^2 z - 2x^2 y^3 z + z^3 y^3 +3x^4 y$ since if the degrees of the terms are the same we look at the degree of $y$ first right? – tellap Feb 11 '15 at 01:49
  • I mean we look at $z$ first then $x$ then $y$. But if it was gr rev lex would the only difference be swapping the $z^3 y^3$ term with $-2x^2 y^3 z$? – tellap Feb 11 '15 at 01:55
  • Yes, swapping those two terms is the only difference. – Jim Feb 11 '15 at 02:00
  • Ok I think I am getting the hang of this. Thank you very much for your explanation, it has helped me understand this a lot further – tellap Feb 11 '15 at 02:10
  • I read that a matrix monomial ordering is a total ordering if we have $Ker A \cap \mathbb Z^n=0$ (where $A$ is the matrix), can you please tell me why is that? – Fareed Abi Farraj Feb 08 '20 at 04:41
0

That's right: one must inspect the monomials of highest total degree with indeterminats ordered by decreasing weights. For two monomials $m=z^{\alpha}x^{\beta}y^{\gamma}$ and $m'z^{\alpha'}x^{\beta'}y^{\gamma'}$, one has $m>m'$ if for the first differing exponent, starting from the right, $m$ has the smallest. So , by decreasing order, we have:

$$z^3x^2y\succ z^2x^3y\succ zx^3y^2\succ z^3y^3\succ zx^2y^3\succ x^4y$$

Bernard
  • 175,478
  • I read that a matrix monomial ordering is a total ordering if we have $Ker A \cap \mathbb Z^n=0$ (where $A$ is the matrix), can you please tell me why is that? – Fareed Abi Farraj Feb 08 '20 at 04:42