NonCommutativePolynomialReduce
NonCommutativePolynomialReduce[poly,{poly1,poly2,…},vars,alg]
yields a list representing a reduction of the polynomial poly modulo the polynomials polyi in variables vars over the non-commutative algebra alg. The list has the form {{f1,f2,…},r}, where r is minimal and f1[poly1]+f2[poly2]+…+r is exactly poly.
NonCommutativePolynomialReduce[poly,{poly1,poly2,…},alg]
yields a list representing a reduction of the polynomial poly modulo the polynomials polyi in the generators of the non-commutative algebra alg.
Details
- NonCommutativePolynomialReduce is used to reduce a polynomial modulo a list of polynomials over a non-commutative algebra.
- vars needs to be specified when alg does not have generators specified ("Generators"Automatic).
- When alg has generators specified ("Generators"gens), {poly1,poly2,…} need to be polynomials in gens, and gens determines the monomial order.
- {f1,f2,…} are univariate linear pure functions with coefficients that are polynomials in vars over alg.
- The polynomial r has the property that none of its terms are divisible by leading terms of any of the polyi.
- If the polyi form a Gröbner basis with respect to the monomial order determined by vars, then this property uniquely determines r.
- If the algebra alg has commutation relations specified, then fi=gi⋄#1&, where gi is a polynomial in the algebra generators and ⋄ is the multiplication in alg.
- NonCommutativePolynomialReduction computes just the reduced polynomial r.
- 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 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.
- The 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".
- The result of reducing a polynomial in general depends on the ordering assigned to monomials.
Examples
open all close allBasic Examples (1)
Reduce a polynomial p with respect to a list of polynomials qq:
p = x**x**y**x**y + 2 y**x**y**x + 3 x**y;
qq = {2 x**y**x + 3 x**x + 4 y + 5, 3 y**x**x + 4 y**x - 5 x + 6};{fs, r} = NonCommutativePolynomialReduce[p, qq, {x, y}]p is a linear combination of polynomials qq and the remainder polynomial r:
NonCommutativeExpand[p - Plus@@MapThread[Construct, {fs, qq}] - r]Scope (5)
Reduce a polynomial over an algebra with commutative and scalar variables:
alg = NonCommutativeAlgebra[<|"ScalarVariables" -> {a, b}, "CommutativeVariables" -> {z, t}|>];
p = 7 x**x**y**z**t**x + a z**x**t**x;
qq = {a t**x + b ^ 2 z**x**y + x**y + 5, 3 x**z + 5 x**x**t + a b};{fs, r} = NonCommutativePolynomialReduce[p, qq, {x, y}, alg]p is a linear combination of polynomials qq and the remainder polynomial r:
NonCommutativeExpand[p - Plus@@MapThread[Construct, {fs, qq}] - r, alg]Reduce a polynomial over an algebra with symbolic property names:
alg = NonCommutativeAlgebra[<|"Multiplication" -> mult, "Addition" -> add, "Unity" -> one, "Zero" -> zero|>];
p = add[mult[x, y, x, z, y], 2mult[z, x, x]];
qq = {add[mult[x, y, x], z], add[mult[z, y], 3]};{fs, r} = NonCommutativePolynomialReduce[p, qq, {{x, y}, {z}}, alg]p is a linear combination of polynomials qq and the remainder polynomial r:
NonCommutativeExpand[add[p, -add@@MapThread[Construct, {fs, qq}], -r], alg]The result of reduction depends on the monomial order:
p = y**x**y**y**x + 2x**y**x;
qq = {3 y**x**y + 4 x + 5, 3 x**y**x + 4 x**y - 5 y**y + 6};NonCommutativePolynomialReduce[p, qq, {x, y}]NonCommutativePolynomialReduce[p, qq, {{x, y}}]Reduce a polynomial modulo a list of polynomials that is not a Gröbner basis:
p = 2x**x**x + y**y**y + 3y;
qq = {x**x + y**y - 1, x**y - 2};
gb = NonCommutativeGroebnerBasis[qq, {{x, y}}]The remainder is not zero, even though p belongs to the ideal generated by qq:
NonCommutativePolynomialReduce[p, qq, {{x, y}}]When p belongs to the ideal generated by qq, the remainder modulo gb must be zero:
NonCommutativePolynomialReduce[p, gb, {{x, y}}]Reduce a polynomial over a Weyl algebra:
alg = WeylAlgebra[{{x, y}, {dx, dy}}]p = dx**dy**x**y;
qq = {x**dx - y**dy};
{fs, r} = NonCommutativePolynomialReduce[p, qq, alg]p is a linear combination of polynomials qq and the remainder polynomial r:
NonCommutativeExpand[p - Plus@@MapThread[Construct, {fs, qq}] - r, alg]Applications (4)
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:
NonCommutativePolynomialReduce[expr, gb, vars, alg][[2]]Use ArraySimplify to do the above simplification steps automatically:
ArraySimplify[expr, Element[a | b, Matrices[{n, n}]]]Prove the Woodbury matrix identity:
Inverse[(a + u.c.v)]=Inverse[a] - Inverse[a].u.Inverse[(v.Inverse[a].u + Inverse[c])].v.Inverse[a]In the standard formulation, 
is an 
matrix, 
is a 
matrix, with 
, 
is a 
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:
NonCommutativePolynomialReduce[d, gb, vars, alg][[2]]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 
:
NonCommutativePolynomialReduce[#, gb, vars][[2]]& /@ NonCommutativeMultiply@@@Tuples[{a, x}, 5]Hence, all elements of the group can be represented as reduced monomials of degree at most 
:
gg = Union[NonCommutativePolynomialReduce[#, gb, vars][[2]]& /@ 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 
:
NonCommutativePolynomialReduce[x**u**v, gb, alg]NonCommutativePolynomialReduce[x**u**v**y + 1, gb, alg]Properties & Relations (5)
NonCommutativePolynomialReduction gives only the reduced polynomial:
NonCommutativePolynomialReduce[z**y**x**y**z + 2x**y**z, {z**y - 3x, y**z + 5x**x}, {x, y, z}]NonCommutativePolynomialReduction[z**y**x**y**z + 2x**y**z, {z**y - 3x, y**z + 5x**x}, {x, y, z}]Reduce a polynomial p with respect to a list of polynomials qq:
p = x**y**z**y**x + 2z**y**x;
qq = {x**y - 3z, y**x + 5z**z};{fs, r} = NonCommutativePolynomialReduce[p, qq, {{x, y, z}}]p is a linear combination of polynomials qq and the remainder polynomial r:
NonCommutativeExpand[p - Plus@@MapThread[Construct, {fs, qq}] - r]A polynomial belongs to the ideal generated by a Gröbner basis iff it reduces to zero:
{p, q} = {y**y - 2y**x**y, y**x - 2 x**x};gb = NonCommutativeGroebnerBasis[{p, q}, {x, y}]This shows that p is in the ideal generated by gb:
NonCommutativePolynomialReduce[p, gb, {x, y}]Over an algebra with commutation relations specified, a polynomial belongs to the left ideal generated by a left Gröbner basis iff it reduces to zero:
alg = WeylAlgebra[{{x, y, z}, {dx, dy, dz}}]{p, q} = {x**x - z**dz, y**y - 2 dz**dz};lgb = NonCommutativeGroebnerBasis[{p, q}, alg, Left]This shows that 
is in the left ideal generated by 
:
NonCommutativePolynomialReduce[p + dx**q, lgb, alg]Use PolynomialReduction to reduce a commutative polynomial with respect to a list of polynomials:
p = x * y * z * y * x + 2z * y * x;
qq = {x * y - 3z, y * x + 5z * z};PolynomialReduction[p, qq, {x, y, z}]Use PolynomialReduce to represent p as a linear combination of qq plus the reduced polynomial r:
{cfs, r} = PolynomialReduce[p, qq, {x, y, z}]Expand[p - cfs.qq - r]Text
Wolfram Research (2025), NonCommutativePolynomialReduce, Wolfram Language function, https://reference.wolfram.com/language/ref/NonCommutativePolynomialReduce.html (updated 2026).
CMS
Wolfram Language. 2025. "NonCommutativePolynomialReduce." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2026. https://reference.wolfram.com/language/ref/NonCommutativePolynomialReduce.html.
APA
Wolfram Language. (2025). NonCommutativePolynomialReduce. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/NonCommutativePolynomialReduce.html