Non‐Commutative Algebras
Introduction
The Wolfram Language provides representation of finitely generated associative unitary algebras as NonCommutativeAlgebra objects. Objects representing Weyl, Clifford and Grassmann algebras can be created using, respectively, WeylAlgebra, CliffordAlgebra and GrassmannAlgebra. Algebra elements are represented as non-commutative polynomials in the algebra generators. Non-commutative polynomials can be transformed using the functions NonCommutativeExpand and NonCommutativeCollect. NonCommutativeGroebnerBasis and NonCommutativePolynomialReduce implement Gröbner basis computation and polynomial reduction over non-commutative algebras.
An algebra 
is a vector space over a field 
, equipped with a binary multiplication operation 
. The multiplication is required to be bilinear, that is if 
and 
, then
is associative if its multiplication operation is associative, that is, if 
,
is unitary if its multiplication operation has a neutral element 
such that for any 
,
is finitely generated if there is a finite set 
such that any element of 
can be represented as an expanded non-commutative polynomial in elements of 
, that is, as an expression of the form
where 
and 
. Elements of 
are called generators of 
. Expressions
are called the monomials of 
, 
are called the terms of 
, and 
are called the coefficients of 
.
In the following sections, an algebra will always mean a finitely generated associative unitary algebra.
Every element of an algebra can be represented as a non-commutative polynomial in the algebra generators. A relation satisfied by generators is a polynomial in the generators that is equal to zero in the algebra. If the generators satisfy nonzero relations, then distinct expanded polynomials in the generators may represent the same algebra element. However, there always exists a set 
of monomials in the generators that forms a vector space basis of 
, that is, each element of 
can be uniquely represented as an expanded polynomial that contains only monomials from 
.
The Wolfram Language representation of an algebra specifies a monomial order. This fixes a set 
of monomials that forms a vector space basis of 
, namely the elements of 
are monomials that are not leading monomials of any relation satisfied by the generators. Elements of 
will be called standard monomials. The representation of 
as an expanded polynomial involving only standard monomials will be called the standard representation of 
. NonCommutativeExpand gives the standard representation of algebra elements.
Algebra Representation
An algebra is represented by a NonCommutativeAlgebra object.
| NonCommutativeAlgebra[spec] | represents the algebra given by the specification spec. |
A valid algebra specification may be an association or a list of rules giving values for some of the algebra properties listed in the table below or a single rule.
Property | Default value | Description |
| "Multiplication" | NonCommutativeMultiply | algebra multiplication |
| "Addition" | Plus | vector space addition |
| "Unity" | 1 | neutral element of multiplication |
| "Zero" | 0 | neutral element of addition |
| "CommutativeVariables" | {} | variables that commute with all elements |
| "ScalarVariables" | Automatic | scalar variables |
| "Generators" | Automatic | generators of the algebra |
| "Relations" | Automatic | relations satisfied by the generators |
| "CommutationRelations" | Automatic | relations for commuting the generators |
| "Structure" | Automatic | named algebra structure |
| "VariableOrder" | "Increasing" | ordering of variables |
| "WordOrder" | "Lexicographic" | ordering of monomials that differ only in the order of variables |
Properties of NonCommutativeAlgebra objects.
alg = NonCommutativeAlgebra[]NonCommutativeExpand[(x**y + 2z)**(3y**z + 4x**x)]Products of consecutive instances of the same variable are represented using GeneralizedPower.
"Multiplication", "Addition", "Unity" and "Zero" specify notation to be used for, respectively, algebra multiplication, vectors space addition, the neutral element of multiplication and the neutral element of addition.
alg = NonCommutativeAlgebra[<|"Multiplication" -> mult, "Addition" -> add, "Unity" -> one, "Zero" -> zero|>]NonCommutativeExpand[mult[add[2x, 3one], add[4x, 5y, 6one]], alg]"Generators" can be a list of lists of variables (the list structure determines the monomial order) or Automatic. In the first case, the generators of the algebra are all variables that appear in "Generators" or in "CommutativeVariables". If "Generators" is Automatic, the set of generators is not specified in the algebra. Instead, in each computation over the algebra, all variables that appear in the input and are not in "ScalarVariables" are assumed to be generators. Non-commutative variables in an expression can be found using NonCommutativeVariables.
NonCommutativeVariables[(x + 2y)**(3z + 4x**y + 5y**z**y)]"ScalarVariables" gives a list of variables that are assumed to be scalars, that is elements of the field 
.
alg = NonCommutativeAlgebra["ScalarVariables" -> {s, t}]NonCommutativeExpand[(s x + t y)**(s ^ 2 x**y + t ^ 2 y**x), alg]If "ScalarVariables" is Automatic, then if the set of generators is specified in the algebra, all symbolic variables that are not generators are assumed to be scalars; otherwise, no symbolic variables are assumed to be scalars.
alg = NonCommutativeAlgebra["Generators" -> {{x, y}}]NonCommutativeExpand[(s x + t y)**(s ^ 2 x**y + t ^ 2 y**x), alg]"Relations" can be a list of relations (polynomials in the algebra generators that are zero in the algebra) or Automatic. The Automatic setting means that there are no relations other than those implied by "CommutativeVariables", "CommutationRelations" and "Structure".
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y}}, "Relations" -> {y**y + 2x + 3}|>]NonCommutativeExpand[(x + 2y)**(3x + 4y), alg]"CommutationRelations" can be Automatic or a list of commutation relations for the algebra generators. Specifying a list of commutation relations requires "Generators" to be specified and requires "CommutativeVariables" to be an empty list. If the generators are 
, then for 
, 
in the monomial order, and the commutation relation for 
and 
needs to have the form
where 
are nonzero scalars, and 
is a polynomial in 
all of whose monomials are less than 
in the monomial order. Moreover, for all 
, polynomials
should reduce to zero modulo the commutation relations. These conditions guarantee that the commutation relations form a Gröbner basis. Generator pairs for which commutation relations are not listed are assumed to commute.
For algebras with commutation relations, all algebra elements can be uniquely represented as linear combinations of standard monomials 
, where the exponents denote repeated application of the algebra multiplication. The definition of monomial divisibility, and hence of Gröbner basis, is different for algebras with and without commutation relations. Therefore, even though an algebra with "CommutationRelations" specified is isomorphic to an algebra obtained by putting the same commutation relations in "Relations", NonCommutativeGroebnerBasis may give different results for these algebras.
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y}}, "CommutationRelations" -> {y**x + 3x**y - 5x + 7}|>]NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, x + y, 3], alg]"Structure" can be Automatic or one of the named structures listed below. With the Automatic setting the algebra structure is determined by the settings of "Generators", "Relations", "CommutationRelations" and "CommutativeVariables". With a named structure setting, "Generators" is expected to be Automatic or a list of lists containing the same generators as given in the structure specification, "Relations" and "CommutationRelations" are expected to be Automatic, and "CommutativeVariables" is expected to be an empty list.
| {"Weyl",{vars,dvars}} | Weyl algebra in variables vars and derivatives dvars |
| {"Clifford",{pvars,nvars,zvars}} | generalized Clifford algebra with generators pvars that square to  , nvars that square to  and zvars that square to  |
| {"Grassmann",vars} | Grassmann algebra with generators vars |
| {"Dirac",{γ0,γ1,γ2,γ3}} | Dirac algebra with generators {γ0,γ1,γ2,γ3} |
| {"Anticommutative",{x1,x2,…}} | algebra with generators {x1,x2,…} and commutation relations  for  |
An algebra with the structure {"Weyl",{x1,…,xn},{dx1,…,dxn}} has commutation relations
all other generator pairs commute, and there are no other relations.
For all other named structures, the commutation relations are 
for all pairs of generators.
An algebra with the structure {"Anticommutative",{x1,x2,…}} has no other relations.
An algebra with the structure {"Clifford",{{p1,p2,…},{n1,n2,…},{z1,z2,…}}} has additional relations 
, 
, and 
.
An algebra with the structure {"Grassmann",{z1,z2,…}} has additional relations 
.
An algebra with the structure {"Dirac",{γ0,γ1,γ2,γ3}} has additional relations 
, 
, 
, and 
.
WeylAlgebra, CliffordAlgebra and GrassmannAlgebra construct NonCommutativeAlgebra objects with structure, respectively, "Weyl", "Clifford" and "Grassmann".
Monomial Ordering
Specification of monomial order is necessary for Gröbner basis computation and polynomial reduction. Computation of standard representation of algebra elements in algebras with relations requires polynomial reduction with respect to a Gröbner basis of the ideal generated by the relations, hence the standard representation also depends on monomial order.
The multi-graded monomial order used is determined by the settings of "Generators", "VariableOrder" and "WordOrder" in the NonCommutativeAlgebra object.
"Generators" can be Automatic or {gs1,…,gsk}, where gsi are disjoint lists of variables. gsi=x, where x is a variable, is equivalent to gsi={x}. If "Generators" is Automatic, the specification of generators needs to be given as an argument to functions like NonCommutativePolynomialReduction or NonCommutativeGroebnerBasis.
NonCommutativeExpand[expr,alg] needs a monomial order if the algebra alg has relations. If alg does not specify generators, the assumed setting of generators is {NonCommutativeVariables[expr,alg]}.
"VariableOrder" can be either "Increasing" or "Decreasing". With the default "Increasing" setting, variables that appear earlier in generator lists are considered to be smaller. Elements of "Generators" are always considered to be larger than elements of "CommutativeVariables".
Monomials are ordered first on the number of occurrences of variables from generator lists gsi, 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".
NonCommutativeMonomialList[expr,alg] lists terms of the standard representation of expr in the decreasing order of monomials.
, then on the number of occurrences of 
, then lexicographically:alg = NonCommutativeAlgebra[<|"Generators" -> {x, y}|>];
NonCommutativeMonomialList[x**x + 2y**y + 3x**y + 4y**x + 5x + 6y + 7, alg]
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y}}|>];
NonCommutativeMonomialList[x**x + 2y**y + 3x**y + 4y**x + 5x + 6y + 7, alg]Word orders are used for comparing monomials that have the same number of occurrences of variables from each generator list gsi and the same number of occurrences of "CommutativeVariables". In particular, the monomials have the same total degree.
| "Lexicographic" | x1⋄…⋄xn≺y1⋄…⋄yn if xi==yi for 1<=i<k and xk≺yk |
| "ReverseLexicographic" | x1⋄…⋄xn≺y1⋄…⋄yn if xi==yi for k<i<=n and xk≻yk |
| "NegativeLexicographic" | x1⋄…⋄xn≺y1⋄…⋄yn if xi==yi for 1<=i<k and xk≻yk |
| "NegativeReverseLexicographic" | x1⋄…⋄xn≺y1⋄…⋄yn if xi==yi for k<i<=n and xk≺yk |
poly = Range[6].NonCommutativeMultiply@@@Permutations[{x, y, z}];
{lex, rlex, nlex, nrlex} = NonCommutativeAlgebra[<|"Generators" -> {{x, y, z}}, "WordOrder" -> #|>]& /@ {"Lexicographic", "ReverseLexicographic", "NegativeLexicographic", "NegativeReverseLexicographic"};NonCommutativeMonomialList[poly, lex]NonCommutativeMonomialList[poly, rlex]NonCommutativeMonomialList[poly, nlex]NonCommutativeMonomialList[poly, nrlex]Gröbner Bases
Theory
This section gives a definition and proves some basic properties of Gröbner bases in a somewhat abstract setting. The level of abstraction is chosen to cover both algebras with and without commutation rules.
Let 
be a unitary algebra over a field 
, and let 
be a 
-vector space basis of 
such that 
, where 
denotes the neutral element of multiplication in 
. Let 
be a well-order in 
, with 
denoting the corresponding strict order.
Notation: If 
, then there is a unique representation 
, where 
, 
and 
.
• 
is called the lead monomial of 
.
• 
is called the lead coefficient of 
.
• 
is called the lead term of 
.
• 
(
divides 
), where 
, iff there exist 
such that 
.
• 
(
does not divide 
), where 
, iff 
is false.
Definition: 
is a generalized polynomial algebra if the following conditions are satisfied:
In the rest of this section, a generalized polynomial algebra 
is fixed.
Remark 1: The monomial divisibility relation is reflexive, antisymmetric and transitive.
Suppose that 
and 
. Then 
and 
, hence 
.
Suppose that 
and 
. Then 
and 
. Hence
Since 
, 
, and so 
, which shows that 
.
• 
denotes the set of lead monomials of 
.
• 
(
is divisible by 
), where 
and 
, iff there exist 
such that 
.
• 
denotes the two-sided ideal generated by 
.
Definition: The normal form of 
modulo a well-ordered set 
is the element 
returned by the following procedure:
• While 
contains any monomials divisible by 
:
• Let 
be the term of 
with the largest monomial 
such that 
.
• Let 
be the smallest element of 
such that 
.
• Let 
be such that 
.
• Let 
.
The procedure terminates because the largest monomial in 
divisible by 
is strictly smaller in each iteration of the while loop, and the monomial order is a well-order. Note that the algorithm may have a choice of 
, and the result may depend on how this choice is made. It may be assumed that there is a fixed procedure for making the choice, for instance, the pair 
is lexicographically smallest in the set of the possible pairs.
Proof: After 
iterations of the while loop,
Definition: The set 
is a Gröbner basis of a two-sided ideal 
in 
if 
for any 
.
Lemma 1: If 
and 
are well-ordered Gröbner bases of 
, then for any 
, 
.
Proof: Let 
and 
. By Remark 1, 
for any monomial 
of 
or 
. Hence, 
for any monomial 
of 
. On the other hand, by Remark 2, 
, and so 
.
Lemma 1 shows that, for a Gröbner basis 
, 
) is well-defined without specifying a well-order in 
or a procedure for picking pairs 
.
Lemma 2: If 
is a Gröbner basis of 
and 
, then 
iff 
.
Proof: By Remark 2, 
, hence 
implies 
. Suppose now that 
. At each iteration of the while loop computing 
, 
. Hence if 
, then 
and the loop continues. Therefore, when the loop returns, 
.
Corollary: If 
is a Gröbner basis of 
, then 
.
Definition: A Gröbner basis 
is reduced if, for any 
, 
and 
, i.e. 
for any monomial 
of 
.
Lemma 3: A reduced Gröbner basis of 
is unique.
Proof: Let 
and 
be reduced Gröbner bases of 
. Let 
. Since 
, there exists 
such that 
. Similarly, there exists 
such that 
. Hence 
, and so 
, since 
is reduced. Therefore 
. Since 
for any monomial 
of 
, 
for any monomial 
of 
. Similarly, 
for any monomial 
of 
. Hence, 
for any monomial 
of 
. Since 
, 
.
Lemma 4: If 
has more than one element, then 
has infinitely many elements.
Proof: Suppose 
with 
. Without loss of generality, one may assume that 
. Since 
and 
, 
. Then 
, which contradicts the assumption that 
is the largest monomial.
Corollary: If an algebra 
has a finite dimension 
over 
, then there is no 
and 
such that 
is a generalized polynomial algebra.
The corollary shows that the definition of Gröbner basis does not cover arbitrary algebras given by generators and relations, since, for instance, the algebra given by one generator 
and the relation 
has dimension 
over 
. However, it will be shown that an arbitrary algebra given by generators and relations is a quotient algebra of 
for some generalized polynomial algebra 
. Therefore, Gröbner bases for quotient algebras will be defined.
Let 
be a generalized polynomial algebra. Let 
be a two-sided ideal in 
, let 
be the reduced Gröbner basis of 
, let 
be a two-sided ideal in 
, and let 
be the reduced Gröbner basis of 
.
Definition: The reduced Gröbner basis of 
is the set 
.
Lemma 5: 
is a Gröbner basis (not necessarily reduced) of 
.
Proof: Let 
. There is a 
such that 
. Either 
or 
, which shows that 
.
The Gröbner basis of 
has been defined to be a subset of 
rather than a subset of 
. However, 
can be identified with a subset of 
consisting of elements reduced modulo 
, i.e. such that 
. With this identification, 
is a subset of 
and, in fact, a subset of 
.
Left Gröbner Bases
This section gives a definition and proves some basic properties of left Gröbner bases. It follows the terminology and the notation of the previous section. The definitions and proven properties are very similar to the two-sided ideal case, with subtle but important differences appearing in the quotient algebra case.
Let 
be a generalized polynomial algebra, as defined in the previous section.
• 
(
left-divides 
), where 
, iff there exists 
such that 
.
• 
(
does not left-divide 
), where 
, iff 
is false.
• 
(
is left-divisible by 
), where 
and 
, iff there exist 
such that 
.
• 
denotes the left ideal generated by 
.
Remark 3: The monomial left-divisibility relation is reflexive, antisymmetric and transitive.
Suppose that 
and 
. Then 
and 
, hence 
.
Suppose that 
and 
. Then 
and 
. Hence
Since 
, 
, and so 
, which shows that 
.
Definition: The left normal form of 
modulo a well-ordered set 
is the element 
returned by the following procedure:
• While 
contains any monomials left-divisible by 
:
• Let 
be the term of 
with the largest monomial 
such that 
.
• Let 
be the smallest element of 
such that 
.
• Let 
be such that 
.
• Let 
.
The procedure terminates because the largest monomial in 
left-divisible by 
is strictly smaller in each iteration of the while loop, and the monomial order is a well-order.
Proof: After 
iterations of the while loop,
Definition: The set 
is a left Gröbner basis of a left ideal 
in 
if 
for any 
.
Lemma 6: If 
and 
are well-ordered left Gröbner bases of 
then for any 
, 
.
Proof: Let 
and 
. By Remark 3, 
for any monomial 
of 
or 
. Hence, 
for any monomial 
of 
. On the other hand, by Remark 4, 
, and so 
.
Lemma 6 shows that, for a left Gröbner basis 
, 
is well-defined without specifying a well-order in G.
Lemma 7: If 
is a left Gröbner basis of 
and 
then 
iff 
.
Proof: By Remark 4, 
, hence 
implies 
. Suppose now that 
. At each iteration of the while loop computing 
, 
. Hence if 
, then 
and the loop continues. Therefore, when the loop returns, 
.
Corollary: If 
is a left Gröbner basis of 
then 
.
Definition: A left Gröbner basis 
is reduced if, for any 
, 
and 
, i.e. 
for any monomial 
of 
.
Lemma 8: A reduced left Gröbner basis of 
is unique.
Proof: Let 
and 
be reduced left Gröbner bases of 
. Let 
. Since 
, there exists 
such that 
. Similarly, there exists 
such that 
. Hence 
, and so 
, since 
is reduced. Therefore 
. Since 
for any monomial 
of 
, 
for any monomial 
of 
. Similarly, 
for any monomial 
of 
. Hence, 
for any monomial 
of 
. Since 
, 
.
Now, left Gröbner bases will be defined for quotient algebras. While the theory looks very similar to the two-sided Gröbner basis case, the crucial difference is that a two-sided ideal is still needed to define a quotient algebra, but there needs to be a left Gröbner basis of this ideal. In general, a set of two-sided generators is given for this ideal, and a two-sided Gröbner basis can be computed from this set. On the other hand, one may not have a set of left generators and in general one may not be able to compute left generators from two-sided generators. In fact, there may not be a finite set of left generators. In the case of polynomials with commutation relations, two-sided Gröbner bases of two-sided ideals are also left Gröbner bases, which is why Wolfram Language implements left Gröbner basis computation only for algebras with commutation relations.
Let 
be a two-sided ideal in 
, let 
be the reduced left Gröbner basis of 
, let 
be a left ideal in 
, and let 
be the reduced left Gröbner basis of 
.
Definition: The reduced left Gröbner basis of 
is the set 
.
Lemma 9: 
is a left Gröbner basis (not necessarily reduced) of 
.
Proof: Let 
. There is a 
such that 
. Either 
or 
, which shows that 
.
The left Gröbner basis of 
has been defined to be a subset of 
rather than a subset of 
. However, 
can be identified with a subset of 
consisting of elements reduced modulo 
, i.e. such that 
. With this identification, 
is a subset of 
and, in fact, a subset of 
.
Polynomial Algebras
Polynomial algebras are represented by NonCommutativeAlgebra objects with "Relations", "CommutationRelations" and "Structure" all set to Automatic. These are algebras with no relations satisfied by the generators, other than commutativity relations satisfied by the elements of "CommutativeVariables".
A monomial in commutative variables 
and non-commutative variables 
is an expression of the form
where 
and 
are non-negative integers and 
. Let 
be the set of all monomials. Multiplication of monomials
A polynomial algebra 
in commutative variables 
and non-commutative variables 
is a 
-vector space with basis 
, and with multiplication of 
-linear combinations of monomials defined by the distributive law.
A monomial 
divides a monomial 
(notation 
) iff there exist monomials 
and 
such that 
. An admissible monomial order is a well-order 
on 
that satisfies
Remark: 
, where 
is an admissible monomial order, is a generalized polynomial algebra.
Remark: Multi-graded monomial orders described in the Monomial Ordering section are admissible monomial orders.
Let alg be a NonCommutativeAlgebra object, with "Relations", "CommutationRelations" and "Structure" all set to Automatic.
Corollary: The polynomial algebra represented by alg is a generalized polynomial algebra.
| NonCommutativeGroebnerBasis[polys,alg] | attempts to compute the reduced Gröbner basis of the two-sided ideal generated by polys in the polynomial algebra represented by alg |
| NonCommutativeGroebnerBasis[polys,vars, alg] | if the value of "Generators" in alg is Automatic, vars specify the algebra generators |
| NonCommutativePolynomialReduction[f,polys, alg] | computes Red(f,polys) in the polynomial algebra represented by alg |
| NonCommutativePolynomialReduction[f,polys,vars,alg] | if the value of "Generators" in alg is Automatic, vars specify the algebra generators |
Gröbner basis computation and polynomial reduction for polynomial algebras.
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y}}, "CommutativeVariables" -> {t}|>];gb = NonCommutativeGroebnerBasis[{t**x**y - 2y**x, y**y + 3x**y**x}, alg]NonCommutativePolynomialReduction[x**y**x**y**x, gb, alg]NonCommutativePolynomialReduce returns functions that give a representation of the input polynomial as a sum of the reduced polynomial and a linear combination of basis elements.
{fs, r} = NonCommutativePolynomialReduce[x**y**x**y**x, gb, alg]NonCommutativeExpand[r + Plus@@MapThread[Construct, {fs, gb}], alg]A Gröbner basis in a polynomial algebra may be infinite, hence NonCommutativeGroebnerBasis limits the number of iterations executed by the algorithm.
NonCommutativeGroebnerBasis[{y**x**y - x**y**x, y**y - x**y}, alg]
NonCommutativeGroebnerBasis[{y**x**y - x**y**x, y**y - x**y}, alg, MaxIterations -> 10]
Quotient Algebras
Quotient algebras of polynomial algebras are represented by NonCommutativeAlgebra objects with "Relations" set to a list of relations and "CommutationRelations" and "Structure" set to Automatic.
Let alg be a NonCommutativeAlgebra object, with "Relations"rels, and "CommutationRelations" and "Structure" set to Automatic. Let 
be the polynomial algebra represented by alg with "Relations" reset to Automatic. Let 
be the two-sided ideal in 
generated by rels, and let 
be the reduced Gröbner basis of 
.
Definition: The normal form of 
modulo a well-ordered set 
over 
is the element 
returned by the following procedure:
• While 
changes:
• Let 
.
• Let 
.
| NonCommutativeGroebnerBasis[polys,alg] | attempts to compute the reduced Gröbner basis of the two-sided ideal generated by polys in  |
| NonCommutativeGroebnerBasis[polys,vars,alg] | if the value of "Generators" in alg is Automatic, vars specify the algebra generators |
| NonCommutativePolynomialReduction[f,polys,alg] | computes RedI(f,polys) |
| NonCommutativePolynomialReduction[f,polys,vars,alg] | if the value of "Generators" in alg is Automatic, vars specify the algebra generators |
Gröbner basis computation and polynomial reduction for quotients of polynomial algebras.
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y}}, "Relations" -> {t**x - 2x**y}, "CommutativeVariables" -> {t}|>];gb = NonCommutativeGroebnerBasis[{y**y + 3x**y**x}, alg]NonCommutativePolynomialReduction[x**y**x**y**x, gb, alg]NonCommutativePolynomialReduce returns functions that give a representation of the input polynomial as a sum of the reduced polynomial and a linear combination of basis elements in the quotient algebra.
{fs, r} = NonCommutativePolynomialReduce[x**y**x**y**x, gb, alg]NonCommutativeExpand[r + Plus@@MapThread[Construct, {fs, gb}], alg]NonCommutativeExpand[x**y**x**y**x, alg]Polynomial Algebras with Commutation Relations
Polynomial algebras with commutation relations are algebras in which the generators satisfy commutation relations and no other relations. They are represented by NonCommutativeAlgebra objects with "Generators" specifying an explicit set of generators (and in consequence a fixed monomial order), "CommutationRelations" specifying a list of commutation relations for the generators, "Relations"Automatic and "CommutativeVariables"{}. Algebras with "Structure" set to {"Weyl",…} or {"Anticommutative",…} are also polynomial algebras with commutation relations.
Let 
be a polynomial algebra with commutation relations, let 
be the generators of 
, and let 
be the set of commutation relations. Let 
be the polynomial algebra obtained from 
by removing the commutation relations. 
is isomorphic to the quotient algebra 
; however, the Wolfram Language does not use the quotient algebra Gröbner basis definition for 
. It turns out that 
is a generalized polynomial algebra, with a different set of monomials and a different divisibility relation than used for 
.
Let 
be the set of standard monomials, i.e. expressions of the form
where 
are non-negative integers. 
is required to satisfy conditions described in the section on Algebra Representation. These conditions imply that 
is a Gröbner basis (in 
); if 
, then 
is a 
-linear combination of standard monomials; if 
is a 
-linear combination of standard monomials, then 
and
This means that if elements of 
are represented in the form reduced modulo 
, then 
is a 
-vector space basis of 
and 
. If 
, where 
and 
; then 
iff 
for 
.
Remark: Any multi-graded monomial order 
described in the Monomial Ordering section is a well-order on 
and satisfies
Corollary: 
is a generalized polynomial algebra.
Let alg be a NonCommutativeAlgebra object representing a polynomial algebra with commutation relations.
| NonCommutativeGroebnerBasis[polys,alg] | computes the reduced Gröbner basis of the two-sided ideal generated by polys in the polynomial algebra with commutation relations represented by alg |
| NonCommutativeGroebnerBasis[polys,alg,Left] | computes the reduced Gröbner basis of the left ideal generated by polys in the polynomial algebra with commutation relations represented by alg |
| NonCommutativePolynomialReduction[f,polys,alg] | computes Red(f,polys) in the polynomial algebra with commutation relations represented by alg |
Gröbner basis computation and polynomial reduction for polynomial algebras with commutation relations.
In polynomial algebras with commutation relations, Gröbner bases are always finite.
Since in 
left-divisibility and two-sided divisibility are equivalent, the left normal form is the same as the two-sided normal form. Hence, NonCommutativePolynomialReduction does not need the left variant.
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y, z}}, "CommutationRelations" -> {y**x - 2x**y + x, z**y - 2y**z + z, z**x - 2x**z + y}|>];gb = NonCommutativeGroebnerBasis[{z**y - 2y**x + 1}, alg]NonCommutativePolynomialReduction[z**z**z, gb, alg]NonCommutativePolynomialReduce returns functions that give a representation of the input polynomial as a sum of the reduced polynomial and a linear combination of basis elements.
{fs, r} = NonCommutativePolynomialReduce[z**z**z, gb, alg]NonCommutativeExpand[r + Plus@@MapThread[Construct, {fs, gb}], alg]alg = WeylAlgebra[{{x, y, z}, {dx, dy, dz}}]gb = NonCommutativeGroebnerBasis[{dx**dy - dz**z, x**y**z - x**y**dz}, alg, Left]NonCommutativePolynomialReduction[x**y**dx**dz + 2z**dy**dz, gb, alg]NonCommutativePolynomialReduce returns functions that give a representation of the input polynomial as a sum of the reduced polynomial and a linear combination of basis elements. In polynomial algebras with commutation relations, the multipliers are always given on the left, hence the representation corresponds to left reduction.
{fs, r} = NonCommutativePolynomialReduce[x**y**dx**dz + 2z**dy**dz, gb, alg]NonCommutativeExpand[r + Plus@@MapThread[Construct, {fs, gb}], alg]A NonCommutativeAlgebra object that has commutation relations for generators given in "Relations" represents a quotient algebra of a polynomial algebra. It is isomorphic to the polynomial algebra with commutation relations represented by a NonCommutativeAlgebra object with the same relations given in "CommutationRelations". However, the algebras have different definitions of monomial divisibility and different definitions of Gröbner basis.
In the following example, the first NonCommutativeAlgebra object represents a polynomial algebra with commutation relations. In this algebra, 
divides 
, and the Gröbner basis of 
is finite. The second NonCommutativeAlgebra object represents a quotient algebra of polynomial algebra. This algebra is isomorphic to the first algebra, but since the divisibility relation is defined differently, in this algebra, 
does not divide 
, and the Gröbner basis of 
is infinite.
rels = {x**y + y**x, x**z + z**x, y**z + z**y};
alg1 = NonCommutativeAlgebra[<|"Generators" -> {x, y, z}, "CommutationRelations" -> rels|>];
NonCommutativeGroebnerBasis[{x**z}, alg1]alg2 = NonCommutativeAlgebra[<|"Generators" -> {x, y, z}, "Relations" -> rels|>];
NonCommutativeGroebnerBasis[{x**z}, alg2]
Quotient Algebras with Commutation Relations
Quotient algebras of polynomial algebras with commutation relations are represented by NonCommutativeAlgebra objects, with "Generators" specifying an explicit set of generators (and in consequence a fixed monomial order), "CommutationRelations" specifying a list of commutation relations for the generators, "Relations" set to a list of relations and "CommutativeVariables"{}. Algebras with "Structure" set to {"Clifford",…}, {"Grassmann",…} or {"Dirac",…} are also quotient algebras of polynomial algebras with commutation relations.
Let alg be a NonCommutativeAlgebra object that represents a quotient algebra of a polynomial algebra with commutation relations. Let 
be the polynomial algebra with commutation relations represented by alg, with "Relations" reset to Automatic. Let 
be the two-sided ideal in 
generated by rels, and let 
be the reduced Gröbner basis of 
.
Definition: The normal form of 
modulo a well-ordered set 
over 
is the element 
returned by the following procedure:
• While 
changes:
• Let 
.
• Let 
.
| NonCommutativeGroebnerBasis[polys,alg] | computes the reduced Gröbner basis of the two-sided ideal generated by polys in  |
| NonCommutativeGroebnerBasis[polys,alg,Left] | computes the reduced Gröbner basis of the left ideal generated by polys in  |
| NonCommutativePolynomialReduction[f,polys, alg] | computes RedI(f,polys) |
Gröbner basis computation and polynomial reduction for quotients of polynomial algebras with commutation relations.
alg = NonCommutativeAlgebra[<|"Generators" -> {{x, y, z}}, "Relations" -> {x**y**z - 1}, "CommutationRelations" -> {y**x - 2x**y + x, z**y - 2y**z + z, z**x - 2x**z + y}|>];gb = NonCommutativeGroebnerBasis[{2y**y + 3x**y**x}, alg]NonCommutativePolynomialReduction[x**y**x**y**x, gb, alg]NonCommutativePolynomialReduce returns functions that give a representation of the input polynomial as a sum of the reduced polynomial and a linear combination of basis elements in the quotient algebra.
{fs, r} = NonCommutativePolynomialReduce[x**y**x**y**x, gb, alg]NonCommutativeExpand[r + Plus@@MapThread[Construct, {fs, gb}], alg]NonCommutativeExpand[x**y**x**y**x, alg]alg = CliffordAlgebra[{{x, y}, {z}}]gb = NonCommutativeGroebnerBasis[{x**y - z**x}, alg, Left]NonCommutativePolynomialReduction[x**y**z, gb, alg]NonCommutativePolynomialReduce returns functions that give a representation of the input polynomial as a sum of the reduced polynomial and a linear combination of basis elements. In quotient algebras of polynomial algebras with commutation relations, the multipliers are always given on the left, hence the representation corresponds to left reduction.
{fs, r} = NonCommutativePolynomialReduce[x**y**z, gb, alg]NonCommutativeExpand[r + Plus@@MapThread[Construct, {fs, gb}], alg]System Options
System options from the NonCommutativeAlgebraOptions group affect the behavior of non-commutative algebra functions. The options can be set with
SetSystemOptions["NonCommutativeAlgebraOptions"->{"option name"->value}].
Option name | Default value | Description |
| "CoefficientSimplifier" | Identity | function used to simplify symbolic coefficients |
| "ExpandMaxExponent" | 30 | maximal exponent for which powers of sums get expanded |
| "NonCommutativeAlgebraDefaults" | {"Multiplication"NonCommutativeMultiply,"Addition"Plus,"Unity"1,"Zero"0,"CommutativeVariables"{},"ScalarVariables"Automatic,"Generators"Automatic,"Relations"Automatic,"CommutationRelations"Automatic,"Structure"Automatic,"VariableOrder""Increasing","WordOrder""Lexicographic"} | default values of NonCommutativeAlgebra properties |
| "PolynomialPowerCrossover" | 4 | maximal exponent for which powers of polynomials are computed by repeated multiplication |
| "ReduceMaxLength" | 40 | maximal segment length for polynomial reduction |
| "ReductionCacheDegree" | 5 | maximal total degree of a monomial for which reduction with respect to commutation relations is cached |
System options in the "NonCommutativeAlgebraOptions" group.
CoefficientSimplifier
The setting of "CoefficientSimplifier" specifies the function used in non-commutative polynomial arithmetic computations to simplify symbolic coefficients of non-commutative polynomials.
alg = NonCommutativeAlgebra["ScalarVariables" -> {a}];
NonCommutativeExpand[(x + y)**x / a + ((a - 1) / a )(x + y)**(x + y) - (x + y)**y, alg]SetSystemOptions["NonCommutativeAlgebraOptions" -> "CoefficientSimplifier" -> Together];
NonCommutativeExpand[(x + y)**x / a + ((a - 1) / a )(x + y)**(x + y) - (x + y)**y, alg]SetSystemOptions["NonCommutativeAlgebraOptions" -> "CoefficientSimplifier" -> Identity];ExpandMaxExponent
The expanded form of the 
th power of a sum of 
terms can have up to 
terms. There is a built-in bound on the exponent for which expansion of powers of sums is attempted.
Length[NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, x + y, 10]]]
NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, x + y, 31]]
When relations specified in the algebra are expected to significantly reduce the number of terms in the expanded form, the bound on the exponent can be increased by setting "ExpandMaxExponent" to a higher value.
SetSystemOptions["NonCommutativeAlgebraOptions" -> "ExpandMaxExponent" -> 100];
alg = NonCommutativeAlgebra[<|"Generators" -> {x, y}, "Relations" -> {x**y - y**x, x**x**x - 2, y**y**y - 3}|>];
NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, x + y, 100], alg]SetSystemOptions["NonCommutativeAlgebraOptions" -> "ExpandMaxExponent" -> 30];alg = CliffordAlgebra[{{x, y}, {u, v}}];
NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, x + 2y + 3u + 4v, 1000], alg]NonCommutativeAlgebraDefaults
The setting of "NonCommutativeAlgebraDefaults" specifies the default values of NonCommutativeAlgebra properties.
defaults = "NonCommutativeAlgebraDefaults" /. ("NonCommutativeAlgebraOptions" /. SystemOptions[])NonCommutativeAlgebra[] === NonCommutativeAlgebra[defaults]SetSystemOptions["NonCommutativeAlgebraOptions" -> "NonCommutativeAlgebraDefaults" -> {"Multiplication" -> CircleTimes, "Addition" -> CirclePlus}];NonCommutativeAlgebra[]SetSystemOptions["NonCommutativeAlgebraOptions" -> "NonCommutativeAlgebraDefaults" -> defaults];PolynomialPowerCrossover
The setting of "PolynomialPowerCrossover" specifies the maximal exponent for which powers of polynomials are computed by repeated multiplication. For higher exponents, powers are computed by binary exponentiation.
NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, x + y, 20]]//Length//AbsoluteTimingSetSystemOptions["NonCommutativeAlgebraOptions" -> "PolynomialPowerCrossover" -> 21];
NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, x + y, 20]]//Length//AbsoluteTimingSetSystemOptions["NonCommutativeAlgebraOptions" -> "PolynomialPowerCrossover" -> 4];ReduceMaxLength
The setting "ReduceMaxLength"len specifies the maximal segment length for polynomial reduction. NonCommutativePolynomialReduction subdivides large polynomials into segments of length len and adds the segment reduction results.
(poly = NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, x + 2y + 3z, 10]])//Length(red1 = NonCommutativePolynomialReduction[poly, {y**x - 2x**y + 3, z**x - 4x**z + 5, z**y - 6y**z + 7}, {x, y, z}])//Length//AbsoluteTimingSetSystemOptions["NonCommutativeAlgebraOptions" -> "ReduceMaxLength" -> 60000];
(red2 = NonCommutativePolynomialReduction[poly, {y**x - 2x**y + 3, z**x - 4x**z + 5, z**y - 6y**z + 7}, {x, y, z}])//Length//AbsoluteTimingred1 === red2SetSystemOptions["NonCommutativeAlgebraOptions" -> "ReduceMaxLength" -> 40];ReductionCacheDegree
For algebras with commutation relations, results of reducing monomials with respect to commutation relations are cached for monomials whose total degree does not exceed "ReductionCacheDegree".
alg = WeylAlgebra[{{x, y, z}, {dx, dy, dz}}];
SeedRandom[1234];
ClearSystemCache[];
Table[First[AbsoluteTiming[NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, RandomInteger[{-10, 10}, 6].{x, y, z, dx, dy, dz}, 5], alg]]], {5}]
SeedRandom[1234];
ClearSystemCache[];
Table[First[AbsoluteTiming[NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, RandomInteger[{-10, 10}, 6].{x, y, z, dx, dy, dz}, 7], alg]]], {5}]
SeedRandom[1234];
ClearSystemCache[];
SetSystemOptions["NonCommutativeAlgebraOptions" -> "ReductionCacheDegree" -> 7];
Table[First[AbsoluteTiming[NonCommutativeExpand[GeneralizedPower[NonCommutativeMultiply, RandomInteger[{-10, 10}, 6].{x, y, z, dx, dy, dz}, 7], alg]]], {5}]SetSystemOptions["NonCommutativeAlgebraOptions" -> "ReductionCacheDegree" -> 5];