path: root/src/algebra/clifford.spad.pamphlet

\documentclass{article}
\usepackage{open-axiom}
\usepackage{amssymb}
\input{diagrams.tex}
\begin{document}
\title{\$SPAD/src/algebra clifford.spad}
\author{Stephen M. Watt}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{domain QFORM QuadraticForm}
<<domain QFORM QuadraticForm>>=
)abbrev domain QFORM QuadraticForm
++ Author: Stephen M. Watt
++ Date Created: August 1988
++ Date Last Updated: May 17, 1991
++ Basic Operations: quadraticForm, elt
++ Related Domains: Matrix, SquareMatrix
++ Also See:
++ AMS Classifications:
++ Keywords: quadratic form
++ Examples:
++ References:
++
++ Description:
++   This domain provides modest support for quadratic forms.
QuadraticForm(n, K): T == Impl where
    n: PositiveInteger
    K: Field
    SM ==> SquareMatrix
    V  ==> DirectProduct
 
    T ==> AbelianGroup with
        quadraticForm: SM(n, K) -> %
            ++ quadraticForm(m) creates a quadratic form from a symmetric,
            ++ square matrix m.
        matrix: % -> SM(n, K)
            ++ matrix(qf) creates a square matrix from the quadratic form qf.
        elt: (%, V(n, K)) -> K
            ++ elt(qf,v) evaluates the quadratic form qf on the vector v, 
            ++ producing a scalar.
 
    Impl ==> SM(n,K) add
        Rep := SM(n,K)
 
        quadraticForm m ==
            not symmetric? m =>
                error "quadraticForm requires a symmetric matrix"
            m::%
        matrix q == q pretend SM(n,K)
        elt(q,v) == dot(v, (matrix q * v))

@
\section{domain CLIF CliffordAlgebra\cite{7,12}}
\subsection{Vector (linear) spaces}
This information is originally from Paul Leopardi's presentation on
the {\sl Introduction to Clifford Algebras} and is included here as
an outline with his permission. Further details are based on the book
by Doran and Lasenby called {\sl Geometric Algebra for Physicists}.

Consider the various kinds of products that can occur between vectors.
There are scalar and vector products from 3D geometry. There are the
complex and quaterion products. There is also
the {\sl outer} or {\sl exterior} product.

Vector addition commutes:
\[a + b = b + a\]
Vector addtion is associative:
\[a + (b + c) = (a + b) + c\]
The identity vector exists:
\[a + 0 = a\]
Every vector has an inverse:
\[a + (-a) = 0\]

If we consider vectors to be directed line segments, thus establishing
a geometric meaning for a vector, then each of these properties has a
geometric meaning.

A multiplication operator exists between scalars and vectors with
the properties:
\[\lambda(a + b) = \lambda a + \lambda b\]
\[(\lambda + \mu)a = \lambda a + \mu a\]
\[(\lambda\mu)a = \lambda(\mu a)\]
\[{\rm If\ }1\lambda = \lambda{\rm\ for\ all\ scalars\ }\lambda
{\rm\ then\ }1a=a{\rm\ for\ all\ vectors\ }a\]

These properties completely define a vector (linear) space. The
$+$ operation for scalar arithmetic is not the same as the $+$
operation for vectors.

{\bf Definition: Isomorphic} The vector space $A$ is isomorphic to
the vector space $B$ if their exists a one-to-one correspondence
between their elements which preserves sums and there is a one-to-one
correspondence between the scalars which preserves sums and products.

{\bf Definition: Subspace} Vector space $B$ is a subspace of vector
space $A$ if all of the elements of $B$ are contained in $A$ and
they share the same scalars.

{\bf Definition: Linear Combination} Given vectors $a_1,\ldots,a_n$
the vector $b$ is a linear combination of the vectors if we can find
scalars $\lambda_i$ such that
\[b = \lambda_1 a_1+\ldots+\lambda_n a_n = \sum_{k=1}^n \lambda_i a_i\]

{\bf Definition: Linearly Independent} If there exists scalars $\lambda_i$
such that
\[\lambda_1 a_1 + \ldots + \lambda_n a_n = 0\]
and at least one of the $\lambda_i$ is not zero
then the vectors $a_1,\ldots,a_n$ are linearly dependent. If no such
scalars exist then the vectors are linearly independent.

{\bf Definition: Span} If every vector can be written as a linear
combination of a fixed set of vectors $a_1,\ldots,a_n$ then this set
of vectors is said to span the vector space.

{\bf Definition: Basis} If a set of vectors $a_1,\ldots,a_n$ is linearly
independent and spans a vector space $A$ then the vectors form a basis
for $A$.

{\bf Definition: Dimension} The dimension of a vector space is the 
number of basis elements, which is unique since all bases of a 
vector space have the same number of elements.
\subsection{Quadratic Forms\cite{1}}
For vector space $\mathbb{V}$ over field $\mathbb{F}$, characteristic 
$\ne 2$:
\begin{list}{}
\item Map $f:\mathbb{V} \rightarrow \mathbb{F}$, with
$$f(\lambda x)=\lambda^2f(x),\forall \lambda \in \mathbb{F}, x \in \mathbb{V}$$
\item $f(x) = b(x,x)$, where
$$b:\mathbb{V}{\rm\ x\ }\mathbb{V} \rightarrow \mathbb{F}{\rm\ ,given\ by\ }$$
$$b(x,y):=\frac{1}{2}(f(x+y)-f(x)=f(y))$$
is a symmetric bilinear form
\end{list}
\subsection{Quadratic spaces, Clifford Maps\cite{1,2}}
\begin{list}{}
\item A quadratic space is the pair($\mathbb{V}$,$f$), where $f$ is a 
quadratic form on $\mathbb{V}$
\item A Clifford map is a vector space homomorphism
$$\rho : \mathbb{V} \rightarrow \mathbb{A}$$
where $\mathbb{A}$ is an associated algebra, and
$$(\rho v)^2 = f(v),{\rm\ \ \ } \forall v \in \mathbb{V}$$
\end{list}
\subsection{Universal Clifford algebras\cite{1}}
\begin{list}{}
\item The {\sl universal Clifford algebra} $Cl(f)$ for the quadratic space
$(\mathbb{V},f)$ is the algebra generated by the image of the Clifford
map $\phi_f$ such that $Cl(f)$ is the universal initial object such
that $\forall$ suitable algebra $\mathbb{A}$ with Clifford map
$\phi_{\mathbb{A}} \exists$ a homomorphism
$$P_\mathbb{A}:Cl(f) \rightarrow \mathbb{A}$$
$$\rho_\mathbb{A} = P_\mathbb{A}\circ\rho_f$$
\end{list}
\subsection{Real Clifford algebras $\mathbb{R}_{p,q}$\cite{2}}
\begin{list}{}
\item The real quadratic space $\mathbb{R}^{p,q}$ is $\mathbb{R}^{p+q}$ with
$$\phi(x):=-\sum_{k:=-q}^{-1}{x_k^2}+\sum_{k=1}^p{x_k^2}$$
\item For each $p,q \in \mathbb{N}$, the real universal Clifford algebra
for $\mathbb{R}^{p,q}$ is called $\mathbb{R}_{p,q}$
\item $\mathbb{R}_{p,q}$ is isomorphic to some matrix algebra over one of:
$\mathbb{R}$,$\mathbb{R}\oplus\mathbb{R}$,$\mathbb{C}$,
$\mathbb{H}$,$\mathbb{H}\oplus\mathbb{H}$ 
\item For example, $\mathbb{R}_{1,1} \cong \mathbb{R}(2)$ 
\end{list}
\subsection{Notation for integer sets}
\begin{list}{}
\item For $S \subseteq \mathbb{Z}$, define
$$\sum_{k \in S}{f_k}:=\sum_{k={\rm min\ }S, k \in S}^{{\rm max\ } S}{f_k}$$
$$\prod_{k \in S}{f_k}:=\prod_{k={\rm min\ }S, k \in S}^{{\rm max\ } S}{f_k}$$
$$\mathbb{P}(S):={\rm\ the\ }\ power\ set\ {\rm\ of\ }S$$
\item For $m \le n \in \mathbb{Z}$, define
$$\zeta(m,n):=\{m,m+1,\ldots,n-1,n\}\backslash\{0\}$$
\end{list}
\subsection{Frames for Clifford algebras\cite{9,10,11}}
\begin{list}{}
\item A {\sl frame} is an ordered basis $(\gamma_{-q},\ldots,\gamma_p)$
for $\mathbb{R}^{p,q}$ which puts a quadratic form into the canonical
form $\phi$
\item For $p,q \in \mathbb{N}$, embed the frame for $\mathbb{R}^{p,q}$
into $\mathbb{R}_{p,q}$ via the maps
$$\gamma:\zeta(-q,p) \rightarrow \mathbb{R}^{p,q}$$
$$\rho:\mathbb{R}^{p,q} \rightarrow \mathbb{R}_{p,q}$$
$$(\rho\gamma k)^2 = \phi\gamma k = {\rm\ sgn\ }k$$
\end{list}
\subsection{Real frame groups\cite{5,6}}
\begin{list}{}
\item For $p,q \in \mathbb{N}$, define the real {\sl frame group} $\mathbb{G}_{p,q}$
via the map
$$g:\zeta(-q,p) \rightarrow \mathbb{G}_{p,q}$$
with generators and relations
$$\langle \mu,g_k | \mu g_k = g_k \mu,{\rm\ \ \ }\mu^2 = 1,$$
$$(g_k)^2 = 
\left\{
\begin{array}{lcc}
\mu,&{\rm\ \ }&{\rm\ if\ }k < 0\\
1&{\rm\ \ }&{\rm\ if\ }k > 0
\end{array}
\right.$$
$$g_kg_m = \mu g_mg_k{\rm\ \ \ }\forall k \ne m\rangle$$
\end{list}
\subsection{Canonical products\cite{1,3,4}}
\begin{list}{}
\item The real frame group $\mathbb{G}_{p,q}$ has order $2^{p+q+1}$
\item Each member $w$ can be expressed as the canonically ordered product
$$w=\mu^a\prod_{k \in T}{g_k}$$
$$\ =\mu^a\prod_{k=-q,k\ne0}^p{g_k^{b_k}}$$
where $T \subseteq \zeta(-q,p),a,b_k \in \{0,1\}$
\end{list}
\subsection{Clifford algebra of frame group\cite{1,4,5,6}}
\begin{list}{}
\item For $p,q \in \mathbb{N}$ embed $\mathbb{G}_{p,q}$ into 
$\mathbb{R}_{p,q}$ via the map
$$\alpha  \mathbb{G}_{p,q} \rightarrow \mathbb{R}_{p,q}$$
$$\alpha 1 := 1,{\rm\ \ \ \ \ } \alpha\mu := -1$$
$$\alpha g_k := \rho\gamma_k, {\rm \ \ \ \ \ }
\alpha(gh) := (\alpha g)(\alpha h)$$
\item Define {\sl basis elements} via the map
$$e:\mathbb{P}\zeta(-q,p) \rightarrow \mathbb{R}_{p,q}, 
{\rm \ \ \ \ \ }e_T := \alpha \prod_{k \in T}{g_k}$$
\item Each $a \in \mathbb{R}_{p,q}$ can be expressed as
$$a = \sum_{T \subseteq \zeta(-q,p)}{a_T e_T}$$
\end{list} 
\subsection{Neutral matrix representations\cite{1,2,8}}
The {\sl representation map} $P_m$ and {\sl representation matrix} $R_m$
make the following diagram commute:
\begin{diagram}
\mathbb{R}_{m,m} & \rTo^{coord} & \mathbb{R}^{4^m}\\
\dTo^{P_m} & & \dTo_{R_m}\\
\mathbb{R}(2^m) & \rTo_{reshape} &  \mathbb{R}^{4^m}\\
\end{diagram}
<<domain CLIF CliffordAlgebra>>=
)abbrev domain CLIF CliffordAlgebra
++ Author: Stephen M. Watt
++ Date Created: August 1988
++ Date Last Updated: May 17, 1991
++ Basic Operations: wholeRadix, fractRadix, wholeRagits, fractRagits
++ Related Domains: QuadraticForm, Quaternion, Complex
++ Also See:
++ AMS Classifications:
++ Keywords: clifford algebra, grassman algebra, spin algebra
++ Examples:
++ References:
++
++ Description:
++  CliffordAlgebra(n, K, Q) defines a vector space of dimension \spad{2**n}
++  over K, given a quadratic form Q on \spad{K**n}.
++
++  If \spad{e[i]}, \spad{1<=i<=n} is a basis for \spad{K**n} then
++     1, \spad{e[i]} (\spad{1<=i<=n}), \spad{e[i1]*e[i2]} 
++  (\spad{1<=i1<i2<=n}),...,\spad{e[1]*e[2]*..*e[n]}
++  is a basis for the Clifford Algebra.
++
++  The algebra is defined by the relations
++     \spad{e[i]*e[j] = -e[j]*e[i]}  (\spad{i \~~= j}),
++     \spad{e[i]*e[i] = Q(e[i])}
++
++  Examples of Clifford Algebras are: gaussians, quaternions, exterior 
++  algebras and spin algebras.
 
CliffordAlgebra(n, K, Q): T == Impl where
    n: PositiveInteger
    K: Field
    Q: QuadraticForm(n, K)
 
    PI ==> PositiveInteger
    NNI==> NonNegativeInteger
 
    T ==> Join(Ring, Algebra(K), VectorSpace(K)) with
        e: PI -> %
          ++ e(n) produces the appropriate unit element.
        monomial: (K, List PI) -> %
          ++ monomial(c,[i1,i2,...,iN]) produces the value given by
          ++ \spad{c*e(i1)*e(i2)*...*e(iN)}.
        coefficient:  (%, List PI) -> K
          ++ coefficient(x,[i1,i2,...,iN])  extracts the coefficient of
          ++ \spad{e(i1)*e(i2)*...*e(iN)} in x.
        recip: % -> Union(%, "failed")
          ++ recip(x) computes the multiplicative inverse of x or "failed"
          ++ if x is not invertible.
 
    Impl ==> add
        Qeelist :=  [Q unitVector(i::PositiveInteger) for i in 1..n]
        dim     :=  2**n
 
        Rep     := PrimitiveArray K
 
        New     ==> new(dim, 0$K)$Rep
 
        x, y, z: %
        c: K
        m: Integer
 
        characteristic   == characteristic$K
        dimension()      == dim::CardinalNumber
 
        x = y ==
            for i in 0..dim-1 repeat
                if x.i ~= y.i then return false
            true
 
        x + y == (z := New; for i in 0..dim-1 repeat z.i := x.i + y.i; z)
        x - y == (z := New; for i in 0..dim-1 repeat z.i := x.i - y.i; z)
        - x   == (z := New; for i in 0..dim-1 repeat z.i := - x.i; z)
        m * x == (z := New; for i in 0..dim-1 repeat z.i := m*x.i; z)
        c * x == (z := New; for i in 0..dim-1 repeat z.i := c*x.i; z)
 
        0            == New
        1            == (z := New; z.0 := 1; z)
        coerce(m): % == (z := New; z.0 := m::K; z)
        coerce(c): % == (z := New; z.0 := c; z)
 
        e b ==
            b::NNI > n => error "No such basis element"
            iz := 2**((b-1)::NNI)
            z := New; z.iz := 1; z
 
        -- The ei*ej products could instead be precomputed in
        -- a (2**n)**2 multiplication table.
        addMonomProd(c1: K, b1: NNI, c2: K, b2: NNI, z: %): % ==
            c  := c1 * c2
            bz := b2
            for i in 0..n-1 | bit?(b1,i) repeat
                -- Apply rule  ei*ej = -ej*ei for i~=j
                k := 0
                for j in i+1..n-1 | bit?(b1, j) repeat k := k+1
                for j in 0..i-1   | bit?(bz, j) repeat k := k+1
                if odd? k then c := -c
                -- Apply rule  ei**2 = Q(ei)
                if bit?(bz,i) then
                    c := c * Qeelist.(i+1)
                    bz:= (bz - 2**i)::NNI
                else
                    bz:= bz + 2**i
            z.bz := z.bz + c
            z
 
        x * y ==
            z := New
            for ix in 0..dim-1 repeat
                if x.ix ~= 0 then for iy in 0..dim-1 repeat
                    if y.iy ~= 0 then addMonomProd(x.ix,ix,y.iy,iy,z)
            z
 
        canonMonom(c: K, lb: List PI): Record(coef: K, basel: NNI) ==
            -- 0. Check input
            for b in lb repeat b > n => error "No such basis element"
 
            -- 1. Apply identity ei*ej = -ej*ei, i~=j.
            -- The Rep assumes n is small so bubble sort is ok.
            -- Using bubble sort keeps the exchange info obvious.
            wasordered   := false
            exchanges := 0
            while not wasordered repeat
                wasordered := true
                for i in 1..#lb-1 repeat
                    if lb.i > lb.(i+1) then
                        t := lb.i; lb.i := lb.(i+1); lb.(i+1) := t
                        exchanges := exchanges + 1
                        wasordered := false
            if odd? exchanges then c := -c
 
            -- 2. Prepare the basis element
            -- Apply identity ei*ei = Q(ei).
            bz := 0
            for b in lb repeat
                bn := (b-1)::NNI
                if bit?(bz, bn) then
                    c := c * Qeelist bn
                    bz:= ( bz - 2**bn )::NNI
                else
                    bz:= bz + 2**bn
            [c, bz::NNI]
 
        monomial(c, lb) ==
            r := canonMonom(c, lb)
            z := New
            z r.basel := r.coef
            z
        coefficient(z, lb) ==
            r := canonMonom(1, lb)
            r.coef = 0 => error "Cannot take coef of 0"
            z r.basel/r.coef
 
        Ex ==> OutputForm
 
        coerceMonom(c: K, b: NNI): Ex ==
            b = 0 => c::Ex
            ml := [sub("e"::Ex, i::Ex) for i in 1..n | bit?(b,i-1)]
            be := reduce("*", ml)
            c = 1 => be
            c::Ex * be
        coerce(x): Ex ==
            tl := [coerceMonom(x.i,i) for i in 0..dim-1 | x.i~=0]
            null tl => "0"::Ex
            reduce("+", tl)


	localPowerSets(j:NNI): List(List(PI)) ==
	  l: List List PI := list []
	  j = 0 => l
	  Sm := localPowerSets((j-1)::NNI)
          Sn: List List PI := []
	  for x in Sm repeat Sn := cons(cons(j pretend PI, x),Sn)
	  append(Sn, Sm)

	powerSets(j:NNI):List List PI == map(reverse, localPowerSets j)

	Pn:List List PI := powerSets(n)

	recip(x: %): Union(%, "failed") ==
	  one:% := 1
	  -- tmp:c := x*yC - 1$C
	  rhsEqs : List K := []
	  lhsEqs: List List K := []
	  lhsEqi: List K
	  for pi in Pn repeat
	    rhsEqs := cons(coefficient(one, pi), rhsEqs)

	    lhsEqi := []
	    for pj in Pn repeat
		lhsEqi := cons(coefficient(x*monomial(1,pj),pi),lhsEqi)
	    lhsEqs := cons(reverse(lhsEqi),lhsEqs)
	  ans := particularSolution(matrix(lhsEqs),
            vector(rhsEqs))$LinearSystemMatrixPackage(K, Vector K, Vector K, Matrix K)
          ans case "failed" => "failed"
	  ansP := parts(ans)
	  ansC:% := 0
	  for pj in Pn repeat
	    cj:= first ansP
	    ansP := rest ansP
	    ansC := ansC + cj*monomial(1,pj)
	  ansC

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<domain QFORM QuadraticForm>> 
<<domain CLIF CliffordAlgebra>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} Lounesto, P.
"Clifford algebras and spinors",
2nd edition, Cambridge University Press (2001)
\bibitem{2} Porteous, I.,
"Clifford algebras and the classical groups",
Cambridge University Press (1995)
Van Nostrand Reinhold, (1969)
\bibitem{3} Bergdolt, G.
"Orthonormal basis sets in Clifford algebras",
in \cite{16} (1996)
\bibitem{4} Dorst, Leo, 
"Honing geometric algebra for its use in the computer sciences",
pp127-152 from \cite{15} (2001)
\bibitem{5} Braden, H.W., 
"N-dimensional spinors: Their properties in terms of finite groups",
American Institute of Physics,
J. Math. Phys. 26(4), April 1985
\bibitem{6} Lam, T.Y. and Smith, Tara L.,
"On the Clifford-Littlewood-Eckmann groups: a new look at periodicity mod 8",
Rocky Mountains Journal of Mathematics, vol 19, no. 3, (Summer 1989)
\bibitem{7} Leopardi, Paul "Quick Introduction to Clifford Algebras"\\
{\bf http://web.maths.unsw.edu.au/~leopardi/clifford-2003-06-05.pdf}
\bibitem{8} Cartan, Elie and Study, Eduard
"Nombres Complexes",
Encyclopaedia Sciences Math\'ematique, \'edition fran\c caise, 15, (1908),
d'apr\`es l'article allemand de Eduard Study, pp329-468. Reproduced as
pp107-246 of \cite{17} 
\bibitem{9} Hestenes, David and Sobczyck, Garret
"Clifford algebra to geometric calculus: a unified language for 
mathematics and physics", D. Reidel, (1984)
\bibitem{10} Wene, G.P.,
"The Idempotent structure of an infinite dimensional Clifford algebra",
pp161-164 of \cite{13} (1995)
\bibitem{11} Ashdown, M. 
"GA Package for Maple V",\\
http://www.mrao.cam.ac.uk/~clifford/software/GA/GAhelp5.html
\bibitem{12} Doran, Chris and Lasenby, Anthony, 
"Geometric Algebra for Physicists" 
Cambridge University Press (2003) ISBN 0-521-48022-1
\bibitem{13} Micali, A., Boudet, R., Helmstetter, J. (eds),
"Clifford algebras and their applications in mathematical physics:
proceedings of second workshop held at Montpellier, France, 1989",
Kluwer Academic Publishers (1992)
\bibitem{14} Porteous, I.,
"Topological geometry"
Van Nostrand Reinhold, (1969)
\bibitem{15} Sommer, G. (editor),
"Geometric Computing with Clifford Algebras",
Springer, (2001)
\bibitem{16} Ablamowicz, R., Lounesto, P., Parra, J.M. (eds)
"Clifford algebras with numeric and symbolic computations",
Birkh\"auser (1996)
\bibitem{17} Cartan, Elie and Montel, P. (eds), 
"\OE uvres Compl\`etes" Gauthier-Villars, (1953)
\end{thebibliography}
\end{document}