The Free Algebra in R

Downloads Build
Status CRAN_Status_Badge Codecov test


The free algebra is an interesting and useful object. Here I present the freealg package which provides some functionality for free algebra. The package uses C++’s STL map class for efficiency, which uses the fact that the order of the terms is algebraically immaterial. The package conforms to disordR discipline.


You can install the released version of freealg from CRAN with:

# install.packages("freealg")  # uncomment this to install the package

The free algebra

The free algebra is the free R-module with a basis consisting of all words over an alphabet of symbols with multiplication of words defined as concatenation. Thus, with an alphabet of \{x,y,z\} and

A=\alpha x^2yx + \beta zy


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


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.

A natural and easily implemented extension is to use upper-case symbols to represent multiplicative inverses of the lower-case equivalents (formally we would use the presentation xX=1). Thus if

C=\epsilon\left(x^{-1}\right)^2=\epsilon X^2

we would have

AC=\left(\alpha x^2yx+\beta zy\right)\epsilon X^2=
\alpha\epsilon x^2yX + \beta\epsilon zyX^2


CA=\epsilon X^2\left(\alpha x^2yx+\beta zy\right)=
\alpha\epsilon yx + \beta\epsilon X^2zy.

The system inherits associativity from associativity of concatenation, and distributivity is assumed, but it is not commutative.

The freealg package in use

Creating a free algebra object is straightforward. We can coerce from a character string with natural idiom:

X <- as.freealg("1 + 3a + 5b + 5abba")
#> free algebra element algebraically equal to
#> + 1 + 3*a + 5*abba + 5*b

or use a more formal method:

#> free algebra element algebraically equal to
#> + 1*a + 2*ab + 3*abc + 4*abcd + 5*abcde
Y <- as.freealg("6 - 4a +2aaab")
#> free algebra element algebraically equal to
#> + 7 - 1*a + 2*aaab + 5*abba + 5*b
#> free algebra element algebraically equal to
#> + 6 + 14*a - 12*aa + 6*aaaab + 2*aaab + 30*abba - 20*abbaa + 10*abbaaaab + 30*b
#> - 20*ba + 10*baaab
#> free algebra element algebraically equal to
#> + 1 + 6*a + 9*aa + 15*aabba + 15*ab + 10*abba + 15*abbaa + 25*abbaabba +
#> 25*abbab + 10*b + 15*ba + 25*babba + 25*bb

We can demonstrate associativity (which is non-trivial):

(x1 <- rfalg(inc=TRUE))
#> free algebra element algebraically equal to
#> + 7*C + 6*Ca + 4*B + 3*BC + 1*a + 5*aCBB + 2*bc
(x2 <- rfalg(inc=TRUE))
#> free algebra element algebraically equal to
#> + 6 + 1*CAAA + 2*Ca + 3*Cbcb + 7*aaCA + 4*b + 5*c
(x3 <- rfalg(inc=TRUE))
#> free algebra element algebraically equal to
#> + 3*C + 5*CbAc + 1*BACB + 2*a + 10*b + 7*cb

(function rfalg() generates random freealg objects). Then

x1*(x2*x3) == (x1*x2)*x3
#> [1] TRUE

Further information

For more detail, see the package vignette


Try the freealg package in your browser

Any scripts or data that you put into this service are public.

freealg documentation built on Dec. 12, 2022, 1:06 a.m.