\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} <>= )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 ==> Join(AbelianGroup, Eltable(V(n,K),K)) 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. 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} <>= )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 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. Impl ==> add Qeelist := [Q unitVector(i::PositiveInteger) for i in 1..n] dim := 2**n Rep := PrimitiveArray K New ==> new(dim, 0$K)$Rep 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: Integer * x: % == (z := New; for i in 0..dim-1 repeat z.i := m*x.i; z) c: K * 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: Integer): % == (z := New; z.0 := m::K; z) coerce(c: K): % == (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: NNI := 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: NNI := 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: NNI := 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] 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 | not zero? x.i] 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 == 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 := members(ans) ansC:% := 0 for pj in Pn repeat cj:= first ansP ansP := rest ansP ansC := ansC + cj*monomial(1,pj) ansC @ \section{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. @ <<*>>= <> <> <> @ \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}