NonCommutativeGroebnerBasis
NonCommutativeGroebnerBasis[{poly1,poly2,…},vars,alg]
attempts to find a list of polynomials that form a reduced Gröbner basis for the set of polynomials polyi in variables vars over the non-commutative algebra alg.
NonCommutativeGroebnerBasis[{poly1,poly2,…},alg]
attempts to find a list of polynomials that form a reduced Gröbner basis for the set of polynomials polyi in the generators of the non-commutative algebra alg.
NonCommutativeGroebnerBasis[{poly1,poly2,…},alg,Left]
finds a list of polynomials that form a reduced left Gröbner basis for the set of polynomials polyi in the generators of the algebra alg with commutation relations.
Details and Options
- NonCommutativeGroebnerBasis is used to compute the reduced Gröbner basis of a set of polynomials over a non-commutative algebra.
- alg can be a NonCommutativeAlgebra object or any valid NonCommutativeAlgebra specification. If the algebra argument is omitted, NonCommutativeAlgebra with the default property values is used.
- vars needs to be specified when alg does not have generators specified ("Generators"Automatic).
- vars should be {vs1,…,vsk}, where vsi are disjoint lists of variables that include all non-commutative variables that appear in {poly1,poly2,…}. vsi=x, where x is a variable, is equivalent to vsi={x}.
- vars, together with "VariableOrder" and "WordOrder" specifications in alg, determines a multi-graded monomial order.
- "VariableOrder" can be either "Increasing" or "Decreasing". With the default "Increasing" setting, variables that appear earlier in variable lists are considered to be smaller. The elements of "CommutativeVariables" of the algebra alg are always considered smaller than all vars.
- Monomials are ordered first on the number of occurrences of variables from variable lists vsi, starting with the list that contains the largest variables, then on the number of occurrences of "CommutativeVariables". If all numbers of occurrences are the same, monomials are ordered using "WordOrder", which can be one of "Lexicographic" (default), "ReverseLexicographic", "NegativeLexicographic" and "NegativeReverseLexicographic".
- When alg has generators specified ("Generators"gens), {poly1,poly2,…} need to be polynomials in gens, and gens determines the monomial order.
- A reduced Gröbner basis is a set gb of polynomials such that the leading monomial of each nonzero element of the ideal generated by {poly1,poly2,…} is divisible by the leading monomial of some element of gb, and no monomial of an element of gb is divisible by the leading monomial of another element of gb. For quotient algebras, that is, if alg has relations specified either through "Relations" or through "Structure", all polynomials are assumed to be in the standard form, that is, reduced modulo the Gröbner basis of the relations.
- For a given monomial order, a reduced Gröbner basis is unique.
- The notion of divisibility, and hence of Gröbner basis, differs depending on whether the algebra alg has commutation relations. For general non-commutative algebras (with "CommutationRelations"Automatic and "Structure"Automatic), a monomial
is divisible by a monomial 
if 
for some monomials 
and 
. For algebras with commutation relations, all algebra elements can be uniquely represented as linear combinations of standard monomials 
, where 
are the algebra generators, and the exponents denote repeated application of the algebra multiplication. In this case, a monomial 
is divisible by a monomial 
if 
for 
. - Left Gröbner basis computation is implemented only for algebras with commutation relations.
- The following option can be given:
-
MaxIterations Automatic the maximum number of iterations to use - A finite Gröbner basis may not exist. The value of the MaxIterations option limits the number of algorithm iterations in which a new basis element is found. If the limit is reached, NonCommutativeGroebnerBasis issues a message and returns the basis elements found so far.
- The Gröbner basis, and even finiteness of the Gröbner basis, in general depend on the ordering assigned to monomials.
- For algebras with commutation relations, reduced Gröbner bases are always finite.
Examples
open all close allBasic Examples (4)
Compute the Gröbner basis over a free noncommutative algebra:
NonCommutativeGroebnerBasis[{2 x**y**x + 3 x**x + 1, 3 y**x**x + 2 y**x - x**y}, {x, y}]Prove that polynomials generate the whole algebra:
NonCommutativeGroebnerBasis[{2 x**y**x + 3 x**x + 4 y + 5, 3 y**x**x + 2 y**x - x, y**x**y - 2x + 1}, {x, y}]Compute the Gröbner basis over an algebra with commutation relations:
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y}}, "CommutationRelations" -> {y**x - 2x**y + 3x + 4y + 5}|>]NonCommutativeGroebnerBasis[{ x**y**x**y + 2y**y**x**x - 3 y**x**x, 4 y**x**x**y + 5 y**x**y}, alg]Compute the Gröbner basis of a left ideal in a Weyl algebra:
alg = WeylAlgebra[{{x, y, z}, {dx, dy, dz}}]NonCommutativeGroebnerBasis[{dx + y**dz, dy - x}, alg, Left]Scope (11)
Free Algebras (5)
Gröbner basis over the default algebra:
NonCommutativeGroebnerBasis[{x**y - z, z**z - 2x}, {{x, y, z}}]Gröbner basis over a free algebra with generators specified:
alg = NonCommutativeAlgebra["Generators" -> {{x, y}}]NonCommutativeGroebnerBasis[{y**x**y - 2y + 1, y**y**y - 2x**x}, alg]Finiteness of the Gröbner basis may depend on the monomial order:
polys = {z**x + x**z**y, y**x - 1, x**y - 1};NonCommutativeGroebnerBasis[polys, {x, y, z}]//Short
NonCommutativeGroebnerBasis[polys, {{x, y}, z}]Gröbner basis over an algebra with commutative and scalar variables:
alg = NonCommutativeAlgebra[<|"ScalarVariables" -> {a, b}, "CommutativeVariables" -> {z, t}|>];
polys = {a t**x + b ^ 2 z**x**y + x**y + 5, 3 x**z + 5 x**x**t + a b};NonCommutativeGroebnerBasis[polys, {x, y}, alg]polys reduce to zero modulo the Gröbner basis:
NonCommutativePolynomialReduction[#, %, {x, y}, alg]& /@ polysGröbner basis over an algebra with symbolic property names:
alg = NonCommutativeAlgebra[<|"Multiplication" -> mult, "Addition" -> add, "Unity" -> one, "Zero" -> zero|>];
polys = {add[mult[x, y, x], z], add[mult[z, y], 2mult[x, y], 3]};NonCommutativeGroebnerBasis[polys, {x, y, z}, alg]polys reduce to zero modulo the Gröbner basis:
NonCommutativePolynomialReduction[#, %, {x, y, z}, alg]& /@ polysQuotient Algebras (2)
Compute a Gröbner basis over a quotient algebra:
alg = NonCommutativeAlgebra[<|"Relations" -> {y**y - x}|>];
polys = {y**x - z**x, z**z - 2x**y};gb = NonCommutativeGroebnerBasis[polys, {{x, y, z}}, alg]polys reduce to zero modulo the Gröbner basis:
NonCommutativePolynomialReduction[#, gb, {{x, y, z}}, alg]& /@ polysThe Gröbner basis is a subset of the Gröbner basis of polys and the relations over the free algebra:
fgb = NonCommutativeGroebnerBasis[Join[polys, {y**y - x}], {{x, y, z}}]It consists of elements whose leading terms do not reduce modulo the Gröbner basis of the relations:
lt = First[NonCommutativeMonomialList[#, {{x, y, z}}]]& /@ fgbrgb = NonCommutativeGroebnerBasis[{y**y - x}, {{x, y, z}}]rlt = NonCommutativePolynomialReduction[#, rgb, {{x, y, z}}]& /@ ltSymmetricDifference[First /@ Select[Transpose[{fgb, lt, rlt}], #[[2]] === #[[3]]&], gb]Compute a Gröbner basis over an algebra given by generators and relations:
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y, z}}, "Relations" -> {y**y - 2x**z}|>];
polys = {x**y**z - 1, z**z - 3y**y};gb = NonCommutativeGroebnerBasis[polys, alg]polys reduce to zero modulo the Gröbner basis:
NonCommutativePolynomialReduction[#, gb, alg]& /@ polysAlgebras with Commutation Rules (4)
Gröbner basis over an algebra with commutation relations specified:
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y, z}}, "CommutationRelations" -> {y**x - 2x**y + x, z**y - 2y**z + z, z**x - 2x**z + y}|>];
polys = {x**y - 2z**z, x**y**z - 1};gb = NonCommutativeGroebnerBasis[polys, alg]polys reduce to zero modulo the Gröbner basis:
NonCommutativePolynomialReduction[#, gb, alg]& /@ polysLeft Gröbner basis over an algebra with commutation relations specified:
alg = WeylAlgebra[{{x, y, z}, {dx, dy, dz}}];
polys = {dx**dy - dz**z, x**y**z - x**z**dx};gb = NonCommutativeGroebnerBasis[polys, alg, Left]polys reduce to zero modulo the Gröbner basis:
NonCommutativePolynomialReduction[#, gb, alg]& /@ polysGröbner basis over a quotient algebra with commutation relations specified:
alg = CliffordAlgebra[{{}, {x, y, z}}];
polys = {x**y**z - 1};gb = NonCommutativeGroebnerBasis[polys, alg]polys reduce to zero modulo the Gröbner basis:
NonCommutativePolynomialReduction[#, gb, alg]& /@ polysAlgebras with commutation relations have a different notion of divisibility than quotient algebras:
rels = {Commutator[x, y], Commutator[x, z], Commutator[y, z]};alg1 and alg2 are isomorphic, however 
divides 
in alg1, but not in alg2:
alg1 = NonCommutativeAlgebra[<|"Generators" -> {x, y, z}, "CommutationRelations" -> rels|>];alg2 = NonCommutativeAlgebra[<|"Generators" -> {x, y, z}, "Relations" -> rels|>];The Gröbner basis of 
over alg1 is finite, but over alg2 is infinite:
NonCommutativeGroebnerBasis[{x**z}, alg1]NonCommutativeGroebnerBasis[{x**z}, alg2]
Options (2)
MaxIterations (2)
NonCommutativeGroebnerBasis attempts up to 
iterations for algebras without commutation rules:
NonCommutativeGroebnerBasis[{b**b - b, b**a**b - a**b}, {a, b}]//AbsoluteTiming
Setting MaxIterations10 makes NonCommutativeGroebnerBasis give up faster:
NonCommutativeGroebnerBasis[{b**b - b, b**a**b - a**b}, {a, b}, MaxIterations -> 10]//AbsoluteTiming
A low value of MaxIterations may result in not finding a finite Gröbner basis even if one exists:
NonCommutativeGroebnerBasis[{b**b - b, b**a**b - a**b, GeneralizedPower[NonCommutativeMultiply, a, 15] - a}, {a, b}, MaxIterations -> 10]
NonCommutativeGroebnerBasis[{b**b - b, b**a**b - a**b, GeneralizedPower[NonCommutativeMultiply, a, 15] - a}, {a, b}]Applications (6)
Simplify an expression involving 
matrices 
and 
:
expr = (Inverse[a] + Inverse[b]).a.Inverse[a + b].bFind the inverses in the expression:
inv = Union[Cases[expr, _Inverse, Infinity]]Generate the relations satisfied by the inverses:
rel = Join@@({#1.First[#1] - SymbolicIdentityArray[{n}], First[#1].#1 - SymbolicIdentityArray[{n}]}& /@ inv)Pick a variable order that makes the most complicated variables largest:
vars = Join[{a, b}, inv]Compute the Gröbner basis of the ideal generated by the relations over the algebra of 
matrices:
alg = NonCommutativeAlgebra[{Dot, n}];gb = NonCommutativeGroebnerBasis[rel, vars, alg]Reducing the expression modulo the Gröbner basis shows that it is equal to the identity matrix:
NonCommutativePolynomialReduction[expr, gb, vars, alg]Use ArraySimplify to do the above simplification steps automatically:
ArraySimplify[expr, Element[a | b, Matrices[{n, n}]]]Prove the Woodbury matrix identity:
![TemplateBox[{{(, {a, +, {u, ., c, ., v}}, )}}, Inverse]=TemplateBox[{a}, Inverse]-TemplateBox[{a}, Inverse].u.TemplateBox[{{(, {{v, ., TemplateBox[{a}, Inverse, SyntaxForm -> SuperscriptBox], ., u}, +, TemplateBox[{c}, Inverse, SyntaxForm -> SuperscriptBox]}, )}}, Inverse].v.TemplateBox[{a}, Inverse]](Files/NonCommutativeGroebnerBasis.en/25.png "TemplateBox[{{(, {a, +, {u, ., c, ., v}}, )}}, Inverse]=TemplateBox[{a}, Inverse]-TemplateBox[{a}, Inverse].u.TemplateBox[{{(, {{v, ., TemplateBox[{a}, Inverse, SyntaxForm -> SuperscriptBox], ., u}, +, TemplateBox[{c}, Inverse, SyntaxForm -> SuperscriptBox]}, )}}, Inverse].v.TemplateBox[{a}, Inverse]"){kind=small}
In the standard formulation, 
is an 
matrix, 
is a 
matrix, with 
, 
is an 
matrix, and 
is a 
matrix. However, by replacing 
, 
and 
with the block matrices 
, 
and 
, one may assume that all matrices belong to the algebra of 
matrices. It will be shown that the difference of the sides of the identity reduces to zero modulo the Gröbner basis of the ideal generated by relations implied by the properties of the matrix inverse.
Compute the difference 
of the sides of the Woodbury matrix identity:
d = Subtract@@(Inverse[(a + u.c.v)] == Inverse[a] - Inverse[a].u.Inverse[(v.Inverse[a].u + Inverse[c])].v.Inverse[a])
inv = Union[Cases[d, _Inverse, Infinity]]Generate the relations satisfied by the inverses:
rel = Join@@({#1.First[#1] - SymbolicIdentityArray[{n}], First[#1].#1 - SymbolicIdentityArray[{n}]}& /@ inv)Pick a variable order that makes the most complicated variables largest:
vars = Join[{a, c, u, v}, inv]Compute the Gröbner basis of the ideal generated by the relations over the algebra of 
matrices:
alg = NonCommutativeAlgebra[{Dot, n}];gb = NonCommutativeGroebnerBasis[rel, vars, alg]Reduce 
modulo the Gröbner basis. The result is a zero matrix, which proves the identity:
NonCommutativePolynomialReduction[d, gb, vars, alg]Use ArraySimplify to do the above simplification steps automatically:
ArraySimplify[d, Element[a | c | u | v, Matrices[{n, n}]]]Construct a finitely presented group. The dicyclic group 
is given by generators 
and relations 
. The group algebra of 
is given by four generators:
gens = {a, x, inv[a], inv[x]};The generators satisfy the following relations:
rel = {GeneralizedPower[NonCommutativeMultiply, a, 6] - 1, GeneralizedPower[NonCommutativeMultiply, x, 2] - GeneralizedPower[NonCommutativeMultiply, a, 3], inv[x]**a**x - inv[a], a**inv[a] - 1, inv[a]**a - 1, x**inv[x] - 1, inv[x]**x - 1};Compute the Gröbner basis of the ideal generated by the relations:
vars = {{a, x}, {inv[a], inv[x]}};gb = NonCommutativeGroebnerBasis[rel, vars]Note that reducing an arbitrary monomial modulo the Gröbner basis gives a monomial that does not contain 
and 
. This shows that reducing an arbitrary monomial in 
and 
of total degree 
yields a monomial of a total degree at most 
:
NonCommutativePolynomialReduction[#, gb, vars]& /@ NonCommutativeMultiply@@@Tuples[{a, x}, 5]Hence, all elements of the group can be represented as reduced monomials of degree at most 
:
gg = Union[NonCommutativePolynomialReduction[#, gb, vars]& /@ Join@@Table[NonCommutativeMultiply@@@Tuples[{a, x}, i], {i, 0, 4}]]It has been proven that 
is a finite group of order 
:
Length[gg]Test left ideal membership in a Clifford algebra:
alg = CliffordAlgebra[{{x, y}, {u, v}}]Compute the Gröbner basis of the left ideal 
:
gb = NonCommutativeGroebnerBasis[{x**y - u**v}, alg, Left]A polynomial belongs to the ideal 
if it reduces to 
:
NonCommutativePolynomialReduction[x**u**v, gb, alg]NonCommutativePolynomialReduction[x**u**v**y + 1, gb, alg]Solve an overdetermined system of homogenous linear ODEs with polynomial coefficients:
eqns = {-y[x] - Derivative[1][y][x] - 2 Derivative[2][y][x] + Derivative[3][y][x] - x Derivative[3][y][x] + 3 Derivative[4][y][x] + x Derivative[5][y][x] == 0, 2 x^2 y[x] - 2 x^2 Derivative[2][y][x] - Derivative[3][y][x] + Derivative[5][y][x] == 0, 3 y[x] - 6 Derivative[2][y][x] - x Derivative[3][y][x] + 3 Derivative[4][y][x] + x Derivative[5][y][x] == 0};Convert equations to Weyl algebra elements, with 
representing differentiation with respect to 
:
toWeyl[a_ == b_] := toWeyl[a - b]
toWeyl[a : (_List | _Plus)] := toWeyl /@ a
toWeyl[c_ ? NumericQ a_] := c toWeyl[a]
toWeyl[a_] := a /. {Derivative[n_][y][x] -> z ^ n, y[x] -> 1} /.
Times -> NonCommutativeMultiply /.
{Power[x, n_.] -> GeneralizedPower[NonCommutativeMultiply, x, n], Power[z, n_.] -> GeneralizedPower[NonCommutativeMultiply, dx, n]}wpolys = toWeyl[eqns]Compute the Gröbner basis of the left ideal generated by the Weyl algebra elements:
wa = WeylAlgebra[{{x}, {dx}}]gb = NonCommutativeGroebnerBasis[wpolys, wa, Left]Find the differential equation corresponding to the Gröbner basis:
toDiff[f_Plus] := toDiff /@ f
toDiff[f_] :=
If[FreeQ[f, dx],
(f /. NonCommutativeMultiply -> Times) y[x],
(f /. NonCommutativeMultiply -> Times) /. Power[dx, n_.] :> D[y[x], {x, n}]]
toEqn[f_List] := toEqn /@ f
toEqn[f_] := toDiff[f] == 0eqn = toEqn[gb]Solve the differential equation:
sol = DSolve[eqn, y, x]Verify that the solution satisfies the original equations:
eqns /. solSolve an overdetermined system of homogenous linear PDEs with polynomial coefficients:
eqns = {u[x, y] + 8 y u[x, y] + 8 x y u[x, y] + u^(0, 1)[x, y] + 2 x u^(0, 1)[x, y] + u^(1, 0)[x, y] + x^2 u^(1, 0)[x, y] + 4 y u^(1, 0)[x, y] + 4 x^2 y u^(1, 0)[x, y] == 0, -3 u^(1, 0)[x, y] - 6 x u^(1, 0)[x, y] + 4 y u^(1, 0)[x, y] + 2 u^(1, 1)[x, y] + 2 x u^(1, 1)[x, y] - 3 u^(2, 0)[x, y] - 3 x^2 u^(2, 0)[x, y] + 4 y u^(2, 0)[x, y] + 2 u^(2, 1)[x, y] + x^2 u^(2, 1)[x, y] == 0, y u[x, y] + 4 x y u[x, y] + u^(0, 1)[x, y] + x u^(0, 1)[x, y] - 3 y u^(1, 0)[x, y] + x^2 y u^(1, 0)[x, y] + x^2 u^(1, 1)[x, y] == 0};Convert equations to Weyl algebra elements, with 
representing differentiation with respect to 
:
toWeyl[a_ == b_] := toWeyl[a - b]
toWeyl[a : (_List | _Plus)] := toWeyl /@ a
toWeyl[c_ ? NumericQ a_] := c toWeyl[a]
toWeyl[a_] := a /. {Derivative[n_, m_][u][x, y] -> zx ^ n zy ^ m, u[x, y] -> 1} /.
Times -> NonCommutativeMultiply /.
{Power[x, n_.] -> GeneralizedPower[NonCommutativeMultiply, x, n], Power[zx, n_.] -> GeneralizedPower[NonCommutativeMultiply, dx, n], Power[zy, n_.] -> GeneralizedPower[NonCommutativeMultiply, dy, n]}wpolys = toWeyl[eqns]Compute the Gröbner basis of the left ideal generated by the Weyl algebra elements:
wa = WeylAlgebra[{{x, y}, {dx, dy}}]gb = NonCommutativeGroebnerBasis[wpolys, wa, Left]Find the differential equations corresponding to the Gröbner basis:
toDiff[f_Plus] := toDiff /@ f
toDiff[f_] :=
If[FreeQ[f, dx | dy],
(f /. NonCommutativeMultiply -> Times) u[x, y],
(f /. NonCommutativeMultiply -> Times) /. {Power[dx, n_.]Power[dy, m_.] :> D[u[x, y], {x, n}, {y, m}],
Power[dx, n_.] :> D[u[x, y], {x, n}], Power[dy, n_.] :> D[u[x, y], {y, n}]}]
toEqn[f_List] := toEqn /@ f
toEqn[f_] := toDiff[f] == 0eqn = toEqn[gb]Solve the differential equations:
sol = DSolve[eqn, u, {x, y}]Verify that the solution satisfies the original equations:
Simplify[eqns /. sol]Properties & Relations (2)
A Gröbner basis generates the same ideal as the input polynomials:
{p, q} = {y**y - 2y**x**y, y**x - 2 x**x};gb = NonCommutativeGroebnerBasis[{p, q}, {{x, y}}]Use NonCommutativePolynomialReduction to show that p is in the ideal generated by gb:
NonCommutativePolynomialReduction[p, gb, {{x, y}}]Use NonCommutativePolynomialReduce to represent p as a combination of basis elements:
{fs, r} = NonCommutativePolynomialReduce[p, gb, {{x, y}}]Plus@@MapThread[Construct, {fs, gb}]NonCommutativeExpand[% - p]Use GroebnerBasis to compute a Gröbner basis of commutative polynomials:
GroebnerBasis[{x * x - 2x * y * x, x * y - 2 y * y}, {x, y}]Text
Wolfram Research (2025), NonCommutativeGroebnerBasis, Wolfram Language function, https://reference.wolfram.com/language/ref/NonCommutativeGroebnerBasis.html (updated 2026).
CMS
Wolfram Language. 2025. "NonCommutativeGroebnerBasis." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2026. https://reference.wolfram.com/language/ref/NonCommutativeGroebnerBasis.html.
APA
Wolfram Language. (2025). NonCommutativeGroebnerBasis. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/NonCommutativeGroebnerBasis.html