Showing the polynomials form a Gröbner basis

Question

Let $A$ be an $m \times n$ real matrix in row echelon form and $I \subset \mathbb{R}[x_1,\dots,x_n]$ is an ideal generated by polynomials $p_i = \sum_{j = 1}^na_{ij}x_j$ with $1 \leq i \leq m$. Then the generators form a Gröbner basis for $I$ w.r.t. some monomial order.

So I guess one should try the standard lexicographic order $x_n > \dots > x_1$ first? Since these are linear, aren't the leading terms automatically the same as the $p_i$?

Answer 1

This holds in a more general setting: if the leading terms are pairwisely coprime, then the $S$-polynomials reduce to zero. (For instance, whenever $\gcd(\mathrm{LT}(f),\mathrm{LT}(g))=1$ one can write $S(f,g)=-(g-\mathrm{LT}(g))f+(f-\mathrm{LT}(f))g$.)

In your case every monomial order for which the variables are ordered according with the corresponding columns of the matrix work. This is Exercise 1.6.5 from An Introduction to Gröbner Bases by Adams and Loustaunau.