Non-commutative Algebra and Its Applications

Adam Strzeboński, Wolfram Reasearch Inc.

#WolframTechConf

ABSTRACT

Mathematica 14.3 introduced new functionality for computation with non-commutative polynomials, including polynomial transformations, polynomial reduction and Groebner basis computation. The upcoming version extends this functionality to non-commutative algebras given by generators and relations, including Weyl, Clifford, and Grassmann algebras. In my talk, I will present the new functionality and show some examples.

Non-commutative Polynomial Functions

Algebra Representation

Mathematica 14.3:

NonCommutativeAlgebra

Coming soon:

WeylAlgebra

CliffordAlgebra

GrassmannAlgebra

Non-commutative Polynomials

NonCommutativePolynomialQ

NonCommutativeVariables

Polynomial Transformations

NonCommutativeExpand

NonCommutativeCollect

Groebner Bases

NonCommutativeGroebnerBasis

NonCommutativePolynomialReduce

NonCommutativeMonomialList

Related Functions

GeneralizedPower

Commutator

Anticommutator

Algebra Representation

A NonCommutativeAlgebra object represents a unitary algebra. It is used in non-commutative polynomial functions to specify the names for algebra operations, neutral elements of addition and multiplication, variables that are assumed to represent scalars and variables that are assumed to represent commutative elements of the algebra.

An algebra is a vector space equipped with a bilinear product operation. An algebra is unitary if its product operation has a neutral element.

In Mathematica 14.3 NonCommutativeAlgebra objects represent free algebras. Algebra elements are non-commutative polynomials in symbolic variables, and the variables do not satisfy any relations, that is distinct (expanded) polynomials represent distinct algebra elements.

In the development version, which I am using here, it is also possible to specify algebra generators and relations that the generators satisfy.

This gives an algebra with default settings:

alg=NonCommutativeAlgebra[]

Here is the full underlying expression:

alg//InputForm

Extract an algebra property value:

alg["Unity"]

Specifying Algebra Operations

The default multiplication operation is NonCommutativeMultiply, which is entered as x**y and typesets as:

x**y

Algebra of n×n matrices:

NonCommutativeAlgebra[{Dot,n}]

Algebra of linear endomorphisms with composition:

NonCommutativeAlgebra[Composition]

Tensor algebra:

NonCommutativeAlgebra[TensorProduct]

Algebra with symbolic operation names:

NonCommutativeAlgebra[<|"Multiplication"->mult,"Addition"->add,"Unity"->one,"Zero"->zero|>]

Non-commutative Polynomials

A polynomial in the default algebra:

p=(x+2y**z)**(3x**z+4y)+5x**z**x+6

Find the variables in p:

NonCommutativeVariables[p]

Check that p is a polynomial in the variables:

NonCommutativePolynomialQ[p,{x,y,z}]

Unlike in the commutative case, p is not a polynomial in a subset of the variables (since z is not an element of the coefficient field):

NonCommutativePolynomialQ[p,{x,y}]

This declares that z is an element of the coefficient field:

NonCommutativePolynomialQ[p,{x,y},NonCommutativeAlgebra["ScalarVariables"->{z}]]

Expand p:

NonCommutativeExpand[p]

GeneralizedPower is used to represent powers with respect to the multiplication operator:

(GeneralizedPower[NonCommutativeMultiply, x, 2, **])//InputForm

(GeneralizedPower[NonCommutativeMultiply, x, 2, **])==NonCommutativeExpand[x**x]

Expand p with z an element of the coefficient field:

NonCommutativeExpand[p,NonCommutativeAlgebra["ScalarVariables"->{z}]]

Expand p with z a commutative element of the algebra:

NonCommutativeExpand[p,NonCommutativeAlgebra["CommutativeVariables"->{z}]]

Collecting Terms

A polynomial in the default algebra:

p=x**a**x+2b**x+3x**a**b**x+4x**a**x**b**x+5x**x+6y**x**x;

Collect with respect to x (on both sides, first on the right):

NonCommutativeCollect[p,x]

Collect with respect to x on one side:

NonCommutativeCollect[p,{x,Left}]

NonCommutativeCollect[p,{x,Right}]

Collect with respect to x on both sides, first on the left:

NonCommutativeCollect[p,{{x,Left},{x,Right}}]

Collect with respect to multiple variables:

NonCommutativeCollect[p,{a,b,x}]

NonCommutativeCollect[p,{x,a,b}]

NonCommutativeCollect[p,{{x,Left},a,b}]

NonCommutativeCollect[p,{{x,Right},a,b}]

Algebras with Non-default Operations

Algebra of n×n matrices:

NonCommutativeExpand[(2a+3b).(4a+5b+6c),{Dot,n}]

Algebra of linear endomorphisms with composition:

NonCommutativeExpand[Composition[f+g,g+h,h+f],Composition]

Tensor algebra:

NonCommutativeExpand[(1+2a+3b)⊗(4c+5a⊗b),TensorProduct]

Algebra with symbolic property names:

alg=NonCommutativeAlgebra[<|"Multiplication"->mult,"Addition"->add,"Unity"->one,"Zero"->zero|>];

NonCommutativeExpand[mult[add[2x,3y],add[4x,5y],add[6x,7y]],alg]

NonCommutativeCollect[%,{x,y},alg]

NonCommutativeExpand[add[%%,-%],alg]

Algebras Given by Generators and Relations

Specify an algebra with generators x and y satisfying relation (y^2)==x:

alg=NonCommutativeAlgebra[<|"Generators"->{{x,y}},"Relations"->{(GeneralizedPower[NonCommutativeMultiply, y, 2, **])-x}|>]

NonCommutativeExpand automatically uses the relations to put the result in the canonical form:

NonCommutativeExpand[(GeneralizedPower[NonCommutativeMultiply, (2 x+3 y), 5, **]),alg]

The canonical form is obtained by reducing the polynomial modulo the Gröbner basis of the relations.

Monomial Orderings

A list of lists of variables {(Subscript[vs, 1]),…,(Subscript[vs, k])}, together with “VariableOrder” and “WordOrder” specified in the algebra, determines a multi-graded monomial order.

alg=NonCommutativeAlgebra[];

alg["VariableOrder"]

alg["WordOrder"]

Monomials are ordered first on the number of occurrences of variables from variable lists (Subscript[vs, i]) starting with the list that contains the largest variables, then on the number of occurrences of commutative variables. If all numbers of occurrences are the same, monomials are ordered using “WordOrder”. Non-list elements of the variable list are equivalent to one-element lists, e.g. {x,y} is equivalent to {{x},{y}}.

p=x**x+2x**y+3y**x+4y**y+5x+6y+7

NonCommutativeMonomialList[p,{x,y}]

NonCommutativeMonomialList[p,{{x,y}}]

Algebras with Commutation Relations

When “CommutationRelations” are given all algebra elements can be uniquely represented as linear combinations of canonical monomials (GeneralizedPower[NonCommutativeMultiply, (Subscript[x, 1]), (Subscript[k, 1]), **])**…**(GeneralizedPower[NonCommutativeMultiply, (Subscript[x, n]), (Subscript[k, n]), **]), where {(Subscript[x, 1]),…,(Subscript[x, n])} are the algebra generators.

The commutation relations need to have the form

(Subscript[x, j])**(Subscript[x, i])-(Subscript[c, i,j]) (Subscript[x, i])**(Subscript[x, j])-(Subscript[d, i,j])

where j>i, (Subscript[c, i,j]) are nonzero scalars, and (Subscript[d, i,j]) is a polynomial in {(Subscript[x, 1]),…,(Subscript[x, n])} whose all monomials are less than (Subscript[x, i])**(Subscript[x, j])⪯(Subscript[x, j])**(Subscript[x, i]) in the monomial order. Moreover, for all i<j<k, polynomials

(Subscript[f, i,j,k])=(Subscript[c, i,k]) (Subscript[c, j,k])(Subscript[d, i,j])**(Subscript[x, k])-(Subscript[x, k])**(Subscript[d, i,j]) +(Subscript[c, j,k]) (Subscript[x, j])**(Subscript[d, i,k])-(Subscript[c, i,j]) (Subscript[d, i,k])**(Subscript[x, j])+(Subscript[d, j,k])**(Subscript[x, i]) -(Subscript[c, i,j]) (Subscript[c, i,k]) (Subscript[x, i])**(Subscript[d, j,k])

should reduce to zero modulo the commutation relations. These conditions guarantee that commutation relations form a Gröbner basis.

alg=NonCommutativeAlgebra[<|"Generators"->{{x,y,z}},"CommutationRelations"->{y**x-2x**y+x,z**y-2y**z+z,z**x-2x**z+y}|>]

NonCommutativeExpand automatically uses the commutation relations to put the result in the canonical form:

NonCommutativeExpand[z**y**x**x**y**z,alg]

Special Algebras

This defines a Weyl algebra (Subscript[A, 2]):

alg=WeylAlgebra[{{x,y},{dx,dy}}]

The algebra has automatically defined commutation relations. This puts an algebra element in the canonical form:

NonCommutativeExpand[dy**dx**x**y,alg]

This defines a Clifford algebra (Subscript[Cl, 0,2]):

alg=CliffordAlgebra[{{},{e1,e2}}]

The algebra has automatically defined commutation relations and relations, and is isomorphic to quaternions:

alg=CliffordAlgebra[{{},{e1,e2}}]

NonCommutativeExpand[(GeneralizedPower[NonCommutativeMultiply, (1+2 e1+3 e2+4 e1**e2), 5, **]),alg]

Do the same computation using the Quaternions package:

<<Quaternions`

Quaternion[1,2,3,4]^5

Gröbner Bases

Compute a Gröbner basis for a two-sided ideal in a free non-commutative algebra:

polys={x**x+2 y**y,3 y**x+4x**y+5x+6y+7};

gb=NonCommutativeGroebnerBasis[polys,{{x,y}}]

Reduce a polynomial modulo the Gröbner basis:

{fs,r}=NonCommutativePolynomialReduce[x**y**x**y**x,gb,{{x,y}}]

NonCommutativeExpand[Plus@@MapThread[Construct,{fs,gb}]+r]

A non-commutative Gröbner basis may be infinite:

polys={z**x+x**z**y,y**x-1,x**y-1};

NonCommutativeGroebnerBasis[polys,{x,y,z}]//Short//AbsoluteTiming

With a different monomial ordering, a finite Gröbner basis may exist:

NonCommutativeGroebnerBasis[polys,{{x,y},z}]

An Application of Non-commutative Gröbner Basis

Show that the Woodbury matrix identity

(Inverse[(a+u.c.v)])==(Inverse[a])-(Inverse[a]).u.(Inverse[(v.(Inverse[a]).u+(Inverse[c]))]).v.(Inverse[a])

is true in an arbitrary algebra and requires only that (((...))^(-1)) be an inverse.

Convert the formula to default multiplication and a symbolic inverse:

eqn=((Inverse[(a+u.c.v)])==(Inverse[a])-(Inverse[a]).u.(Inverse[(v.(Inverse[a]).u+(Inverse[c]))]).v.(Inverse[a]))/.{Dot->NonCommutativeMultiply,Inverse->inv}

Find all inverses in the formula:

inverses=Union[Cases[eqn,_inv,Infinity]]

List the relations implied by the definition of inverse:

relations=Join@@({#1**First[#1]-1,First[#1]**#1-1}&/@inverses)

Compute a Gröbner basis of the relations:

vars=Join[{a,c,u,v},inverses]

gb=NonCommutativeGroebnerBasis[relations,vars]

Show that the difference of the sides of the identity reduces to zero:

NonCommutativePolynomialReduce[Subtract@@eqn,gb,vars][[2]]

An Application of Left Gröbner Basis in Weyl Algebra

Solve 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]+Derivative[0,1][u][x,y]+2 x Derivative[0,1][u][x,y]+Derivative[1,0][u][x,y]+(x^2) Derivative[1,0][u][x,y]+4 y Derivative[1,0][u][x,y]+4 (x^2) y Derivative[1,0][u][x,y]==0,-3 Derivative[1,0][u][x,y]-6 x Derivative[1,0][u][x,y]+4 y Derivative[1,0][u][x,y]+2 Derivative[1,1][u][x,y]+2 x Derivative[1,1][u][x,y]-3 Derivative[2,0][u][x,y]-3 (x^2) Derivative[2,0][u][x,y]+4 y Derivative[2,0][u][x,y]+2 Derivative[2,1][u][x,y]+(x^2) Derivative[2,1][u][x,y]==0,y u[x,y]+4 x y u[x,y]+Derivative[0,1][u][x,y]+x Derivative[0,1][u][x,y]-3 y Derivative[1,0][u][x,y]+(x^2) y Derivative[1,0][u][x,y]+(x^2) Derivative[1,1][u][x,y]==0};

Convert equations to Weyl algebra elements, with dx and dy representing differentiation with respect to x and y:

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]==0

eqn=toEqn[gb]

Solve the differential equations:

sol=DSolve[eqn,u,{x,y}]

Verify that the solution satisfies the original equations:

Simplify[eqns/.sol]

Commutator and Anticommutator

Commutator of two variables:

Commutator[x,y]

Anticommutator of two variables:

Anticommutator[x,y]

Commutator in the matrix algebra:

Commutator[x,y,Dot]

Prove that [x,[y,z]]+[y,[z,x]]+[z,[x,y]]==0 (Jacobi identity):

Commutator[x,Commutator[y,z]]+Commutator[y,Commutator[z,x]]+Commutator[z,Commutator[x,y]]

NonCommutativeExpand[%]

Prove that [x,y**z]==[x, y]**z+y**[x,z] (Leibniz rule):

Commutator[x,y**z]-(Commutator[x,y]**z+y**Commutator[x,z])

NonCommutativeExpand[%]

Prove that [x,{y,z}]+[z,{x,y}]+[y,{z,x}]==0:

Commutator[x,Anticommutator[y,z]]+Commutator[z,Anticommutator[x,y]]+Commutator[y,Anticommutator[z,x]]

NonCommutativeExpand[%]

Thank you for listening!