The free algebra

The free algebra is the free R-module with a basis consisting of all words over an alphabet of symbols [conventionally lower-case letters] with multiplication of words defined as concatenation. It is easiest to give an example: with an alphabet of \(\{x,y,z\}\) and formally write \(A=\alpha x^2yx + \beta zy\) and \(B=\gamma z + \delta y^4\), we would have

\[ AB=\left(\alpha x^2yx+\beta zy\right)\left(\gamma z+\delta y^4\right)= \alpha\gamma x^2yxz+\alpha\delta x^2yxy^4+\beta\gamma zyz+\beta\delta zy^5 \]

and

\[ BA=\left(\gamma z+\delta y^4\right)\left(\alpha x^2yx+\beta zy\right)= \alpha\gamma zx^2yx + \alpha\delta y^4 x^2yx + \beta\gamma z^2y + \beta\delta y^4zy. \]

The system inherits associativity from associativity of concatenation; distributivity follows from the definition of R-module. However, the free algebra is not commutative in general.

The freealg package in use

The above examples are a little too general for the freealg package; the idiom requires that we have specific numerical values for the coefficients \(\alpha,\beta,\gamma\delta\). Here we will use \(1,2,3,4\) respectively.

(A <- as.freealg("xxyx + 2zy"))

## free algebra element algebraically equal to
## + 1*xxyx + 2*zy

(B <- as.freealg("3z + 4yyyy"))

## free algebra element algebraically equal to
## + 4*yyyy + 3*z

A*B

## free algebra element algebraically equal to
## + 4*xxyxyyyy + 3*xxyxz + 8*zyyyyy + 6*zyz

B*A

## free algebra element algebraically equal to
## + 4*yyyyxxyx + 8*yyyyzy + 3*zxxyx + 6*zzy

Note that the terms are stored in an implementation-specific order. For example, B might appear as + 4*yyyy + 3*z or the algebraically equivalent form 3*z + 4*yyyy (see the disordR package vignette for an extended discussion).

Inverses are coded using upper-case letters.

(C <- as.freealg("3 + 5X - 2Xyx"))

## free algebra element algebraically equal to
## + 3 + 5*X - 2*Xyx

A*C

## free algebra element algebraically equal to
## + 5*xxy + 3*xxyx - 2*xxyyx + 6*zy + 10*zyX - 4*zyXyx

C*A

## free algebra element algebraically equal to
## - 2*Xyxxxyx - 4*Xyxzy + 10*Xzy + 3*xxyx + 5*xyx + 6*zy

With these objects we may verify that the distributive and associative laws are true:

A*(B+C) == A*B + A*C

## [1] TRUE

(A+B)*C == A*C + B*C

## [1] TRUE

A*(B*C) == (A*B)*C

## [1] TRUE

Various utilities are included in the package. For example, the commutator bracket is represented by reasonably concise idiom:

.[as.freealg("x"),as.freealg("y")]

## free algebra element algebraically equal to
## + 1*xy - 1*yx

Using rfalg() to generate random free algebra objects, we may verify the Jacobi identity:

x <- rfalg()
y <- rfalg()
z <- rfalg()

.[x,.[y,z]] + .[y,.[z,x]] + .[z,.[x,y]]

## free algebra element algebraically equal to
## 0

The package includes functionality for substitution:

subs("aabccc",b="1+3x")  # aa(1+3x)ccc

## free algebra element algebraically equal to
## + 1*aaccc + 3*aaxccc

subs("abccc",b="1+3x",x="1+d+2e")

## free algebra element algebraically equal to
## + 4*accc + 3*adccc + 6*aeccc

There is even some functionality for calculus:

deriv(as.freealg("aaaxaa"),"a")

## free algebra element algebraically equal to
## + 1*aaaxa(da) + 1*aaax(da)a + 1*aa(da)xaa + 1*a(da)axaa + 1*(da)aaxaa