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.
Algebra specification
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.
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.
Named algebra structures.
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.
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.
Word orders.
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:
• implies .
• implies , for any .
In the rest of this section, a generalized polynomial algebra is fixed.
Remark 1: The monomial divisibility relation is reflexive, antisymmetric and transitive.
Proof:
since .
Suppose that and . Then and , hence .
Suppose that and . Then and . Hence
and
where , and . Therefore
Since , , and so , which shows that .
Notation:
• 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:
• Set .
• 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 .
• Return .
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.
Remark 2: .
Proof: After iterations of the while loop,
where , and .
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 .
Corollary:
• If and then .
• For any , .
• If then .
• For any , iff .
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.
Notation:
• ( 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.
Proof:
since .
Suppose that and . Then and , hence .
Suppose that and . Then and . Hence
and
where , and . Therefore
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:
• Set .
• 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 .
• Return .
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.
Remark 4: .
Proof: After iterations of the while loop,
where , and .
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 .
Corollary:
• If and then .
• For any , .
• If then .
• For any , iff .
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
and
is defined by
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
• implies .
• implies , for any .
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.
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:
• Set .
• While changes:
• Let .
• Let .
• Return .
Remark: .
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
• implies .
• implies , for any .
Corollary: is a generalized polynomial algebra.
Let alg be a NonCommutativeAlgebra object representing a polynomial algebra with commutation relations.
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:
• Set .
• While changes:
• Let .
• Let .
• Return .
Remark: .
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}].
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];