# Geometric algebra

Geometric algebra is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Geometric algebra is an other name for Clifford algebras and it's basically an algebra containing a vector space ${\displaystyle {\mathcal {V}}}$ and obeying the following axioms:

${\displaystyle {\begin{array}{c}(ab)c=a(bc)\\a(b+c)=ab+ac\\(a+b)c=ac+bc\\\forall \mathbf {x} \in {\mathcal {V}},\,\mathbf {x} ^{2}\in \mathbb {R} \end{array}}}$

The product operation in such algebra is called the geometric product. Elements are called multivectors, while multivectors in ${\displaystyle {\mathcal {V}}}$ are just called vectors.

There are a few simple examples of geometric algebras. A trivial one for instance is simply ${\displaystyle \mathbb {R} }$, where ${\displaystyle {\mathcal {V}}=\mathbb {R} }$. The complex numbers also form a geometric algebra, where the vector space is the one-dimensional space of all purely imaginary numbers. An other example is the space of quaternions, where the vector space is the three-dimensional space of all linear combinations of ${\displaystyle (i,j,k)}$.

The purpose of this task is to implement a geometric algebra with a vector space ${\displaystyle {\mathcal {V}}}$ of dimension n of at least five, but for extra-credit you can implement a version with n arbitrary large. Using a dimension five is useful as it is the dimension required for the so-called conformal model which will be the subject of a derived task.

To ensure the unicity of the solution (that is, up to some isomorphism), we will also restrict ourselves to the so-called euclidean case, where the square of a non-zero vector is positive:

${\displaystyle \forall \mathbf {x} \in {\mathcal {V}},\,\mathbf {x} \neq 0\implies \mathbf {x} ^{2}>0}$.

You can of course, for extra credit, implement the general case. This would require the definition of a parameter for the signature of the metric.

In order to show that your solution uses a vector space of dimension at least five, you will create a function n -> e(n) such that the vectors e(0), e(1), e(2), e(3), e(4) are linearly independent. To do so you will make them orthonormal with the following scalar product:

${\displaystyle \mathbf {x} \cdot \mathbf {y} =(\mathbf {x} \mathbf {y} +\mathbf {y} \mathbf {x} )/2}$

The fact that this so-called inner product defines a scalar product is a consequence of the fourth axiom. To see it one just needs to notice the relation:

${\displaystyle \mathbf {x} \mathbf {y} +\mathbf {y} \mathbf {x} =(\mathbf {x} +\mathbf {y} )^{2}-\mathbf {x} ^{2}-\mathbf {y} ^{2}}$

Once you'll have shown that your vector space is at least of dimension five, you will show that the axioms are satisfied. For this purpose you will pick three random multivectors a, b and c, along with a random vector ${\displaystyle \mathbf {x} }$.

Producing a random vector is easy. Just use a pseudo-random generation function rand and create a vector:

${\displaystyle \mathrm {randomVector} ()=\sum _{i=0}^{4}\mathrm {rand} ()\mathbf {e} _{i}}$

Producing a random multivector is slightly more involved. It is known that when the dimension of ${\displaystyle {\mathcal {V}}}$ is n, then the dimension of the algebra (seen as a vector space with its natural scalar multiplication) is 2n. This means that for n=5 there is a basis of 25 = 32 basis multivectors from which any multivector can be written as a linear combination. Create such a basis ${\displaystyle m_{0},m_{1},\ldots ,m_{31}}$ along with a function producting a random multivector:

${\displaystyle \mathrm {randomMultivector} ()=\sum _{i=0}^{31}\mathrm {rand} ()m_{i}}$

To summarize, to solve this task you will:

• define the inner product of two vectors : ${\displaystyle \mathbf {x} \cdot \mathbf {y} =(\mathbf {xy} +\mathbf {yx} )/2}$.
• define the function e
• verify the orthonormality ${\displaystyle \mathbf {e} _{i}\cdot \mathbf {e} _{j}=\delta _{i,j}}$ for i, j in ${\displaystyle \{0,1,2,3,4\}}$.
• create a function returning a random multivector
• create a function returning a random vector
• verify the axioms for three rarndom multivectors a, b, c and a random vector x.

Optionally, you will repeat the last step a large number of times, in order to increase confidence in the result.

## EchoLisp

We build a CGA based upon a generating quadratic form in R^n. The implementation is general enough, that is ei*ei = +/- 1 , and not restricted to 1. The 5 dimension limit comes from the use of 32 bits numbers to generate all permutations 101... , but this could be improved. The multi-vector multiplication is based on a multiplication table 2^n * 2^n , generated once for all.

 (define e-bits (build-vector 32 (lambda(i) (arithmetic-shift 1 i)))) ;; 1,2,4,..(define (e-index i) ;; index of ei in native vector	(if (zero? i) 0 (arithmetic-shift 1 (1- i)))) (define DIM 0) ;; 2^N(define N 0)(define MultTable null) ;; multiplication table eijk * el.. = exyz..(define SignTable null) ;; sign of products(define Signature null) ;; input quadratic form ;; return "eijk"(define( e-print E  sign )	(string-append		(cond ((= sign 1) " ") ((= sign -1) "- ") (else ""))	  (if (zero? E) "1"	  (for/string ((i  N))	  #:continue (zero? (bitwise-and E (vector-ref e-bits  i)))	  (string-append "e" (1+ i)))))) ;; returns a string a *e1 + b*e2 + .. z*eijk + ..(define (multi-print V (x))	(for/string ((i DIM))	(set! x (vector-ref V i))	#:continue (zero? x)	(string-append " " (if (> x 0) "+" "") x  "*" (e-print i 0))))  ;; generates the multiplication table e_i e__k . * e_j e_l ..==> e_u e_v ...;; E_I and E_J are sets of indices >=1 , increasing order,  represented by a 32 bits number (define (make-mult-table (verbose #f) (result) (swaps) (ej))(when verbose (writeln 'N= N 'DIM= DIM 'Q= Signature))(for* ((E_I (in-range 1 DIM))(E_J (in-range 1 DIM)))		(set! result E_I)		(set! swaps 0)		(for ((j DIM)) ; each bit# in E_J		(set! ej (vector-ref e-bits j))		#:continue (zero? (bitwise-and  ej E_J)) 			(for((s (in-range (1- N) j -1))) ;; count swaps				(when (!zero? (bitwise-and E_I (vector-ref e-bits s)))					  (set! swaps (1+ swaps)))) 		(if (zero? (bitwise-and E_I ej)) ;; e_i * e_j		(set! result (bitwise-ior result ej))		(begin ;; else e_i * e_i		(set! result (bitwise-xor result ej))		(when (= -1 (vector-ref Signature ej)) (set! swaps (1+ swaps)))		))) ;; j loop 		(when verbose (writeln  (e-print E_I 0) '* (e-print E_J 0) 				'= (e-print result  (if (even? swaps) 1 -1)))) 		(matrix-set! MultTable E_I E_J result)		(matrix-set! SignTable E_I E_J (if (even? swaps) 1 -1))		)) ;; multivector operations;; addition is standard vector addition;; multiplication a  b -> c(define (multi-mult  a b)	(define c (make-vector DIM 0))	(for* ((i DIM) (j DIM))		#:continue (zero? (vector-ref a i))		#:continue (zero? (vector-ref b j))		(vector-set! c  			(array-ref MultTable i j) 			(+ 				(* (array-ref  SignTable i j) (vector-ref a i) (vector-ref b j))				(vector-ref c (array-ref MultTable i j)))))		c) ;; pretty print  a • b or a • b • c(define ( • a b (c #f))	(multi-print	(if c  (multi-mult a (multi-mult b c)) (multi-mult a b))))  ;; (Eij i j) ->  return multi-vector eiej 0 <= i <= n(define (Eij i j (coeff 1))	(define Eij (make-vector DIM))	(vector-set! Eij (array-ref MultTable (e-index i) (e-index j)) coeff)	Eij)  ;; Reference : https://en.wikipedia.org/wiki/Clifford_algebra#Real_numbers ;; (make-cga  m p [verbose])  => Algebra A(m p);; Input : a quadratic form Q(x) =  x1*x1 + + xm*xm - xm+1*xm+1 - xm+p*xm+p;; n = m + p = dimension of vector space R^n;; generates an algebra A(m p) of dimension  DIM  = 2^n;; Ex : A(n 0) = use R^n dot product as quadratic form : ei*ei = 1;; Ex : A (0 1) = Complex , e1*e1 = -1 ;  A(0 2) => quaternions ei*ei = -1;;;; Implementation;; limitation n <= 5;; multivectors of A(m p) will be mapped on Vectors  V of dimension 2^n;; V[0] is the scalar part of a multivector.;; Blade of vectors of R^n :  :V[2^(i-1)] = 1 , 0 elsewhere , i in [1 ..n] (define (make-cga m p (verbose #f))(string-delimiter "")	(set! N (+ m p))	(set! DIM (expt 2 N))	(set! MultTable (build-array DIM DIM (lambda(i j) (cond ((zero? i) j)((zero? j) i)(else 0)))))	(set! SignTable (make-array DIM DIM 1))	(set! Signature (make-vector DIM 1)) ;; Q polynomial	(for ((j (in-range m N))) (vector-set! Signature (vector-ref e-bits j) -1)) 	(make-mult-table verbose) DIM )
Output:
 ;; we use indices (1 ... n) in conformity with the Wikipedia reference ;; dimension 2;; (1 + e1e2) • (e1 -2e2) = -e1 -3e2(make-cga 2 0)(define u #(1 0 0 1))(define v #(0 1 -2 0)) (multi-print u) → +1*1 +1*e1e2(multi-print v) → +1*e1 -2*e2(• u v)         → -1*e1 -3*e2 ;; task(make-cga 5 0)(define X #(0 1 -1 0 2 0 0 0 -3 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ))(multi-print X) → +1*e1 -1*e2 +2*e3 -3*e4 -2*e5(• X X)  →  +19*1 ; with another polynomial(make-cga 0 5)Signature → #( 1 -1 -1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)(• X X) → -19*1 ;(make-cga 4 0)(define i (Eij 1 2))(define j (Eij 2 3))(define k (Eij 1 3)) (multi-print i) → +1*e1e2(multi-print j) → +1*e2e3(multi-print k)]→ +1*e1e3(• i i) → -1*1(• j j) → -1*1(• k k) → -1*1(• i j k) → -1*1 (define I (Eij 2 3))😖️ error: define : cannot redefine : I (used in Complex) ;; use II instead (define II (Eij 2 3)) → +1*e2e3(define J (Eij 3 4)) → +1*e3e4(define K (Eij 2 4)) → +1*e2e4 (• II II) → -1*1(• J J)  → -1*1(• K K)  → -1*1(• II J K) → -1*1

Multiplication table for A(3 0)

N= 3 DIM= 8 Q= #( 1 1 1 1 1 1 1 1)
e1 * e1 = 1
e1 * e2 = e1e2
e1 * e1e2 = e2
e1 * e3 = e1e3
e1 * e1e3 = e3
e1 * e2e3 = e1e2e3
e1 * e1e2e3 = e2e3
e2 * e1 = - e1e2
e2 * e2 = 1
e2 * e1e2 = - e1
e2 * e3 = e2e3
e2 * e1e3 = - e1e2e3
e2 * e2e3 = e3
e2 * e1e2e3 = - e1e3
e1e2 * e1 = - e2
e1e2 * e2 = e1
e1e2 * e1e2 = - 1
e1e2 * e3 = e1e2e3
e1e2 * e1e3 = - e2e3
e1e2 * e2e3 = e1e3
e1e2 * e1e2e3 = - e3
e3 * e1 = - e1e3
e3 * e2 = - e2e3
e3 * e1e2 = e1e2e3
e3 * e3 = 1
e3 * e1e3 = - e1
e3 * e2e3 = - e2
e3 * e1e2e3 = e1e2
e1e3 * e1 = - e3
e1e3 * e2 = - e1e2e3
e1e3 * e1e2 = e2e3
e1e3 * e3 = e1
e1e3 * e1e3 = - 1
e1e3 * e2e3 = - e1e2
e1e3 * e1e2e3 = e2
e2e3 * e1 = e1e2e3
e2e3 * e2 = - e3
e2e3 * e1e2 = - e1e3
e2e3 * e3 = e2
e2e3 * e1e3 = e1e2
e2e3 * e2e3 = - 1
e2e3 * e1e2e3 = - e1
e1e2e3 * e1 = e2e3
e1e2e3 * e2 = - e1e3
e1e2e3 * e1e2 = - e3
e1e2e3 * e3 = e1e2
e1e2e3 * e1e3 = e2
e1e2e3 * e2e3 = - e1
e1e2e3 * e1e2e3 = - 1

## J

Sparse arrays give better performance for this task, than dense arrays, and support relatively arbitrary dimensions, but can be a bit quirky because current implementations of J do not support some features for sparse arrays. We add multivectors x and y using x + y. Also, the first element of one of these multivectors represents the "real valued" or "scalar component" of the multivector.

Implementation: