# CliffordAlgebra and PauliMatrix domains

11 views

### Martin Baker

Feb 13, 2010, 11:15:44 AM2/13/10
to FriCAS - computer algebra system
I am stuck in implementing a PauliMatrix domain, The issues are mostly
with the mathematics involved but I also have some issues with how to
implement in FriCAS. I would appreciate any pointers you could give
me. I will explain the issues below (sorry it is so long).

http://github.com/martinbaker/multivector/
All the code and documentation is there.

The changes to the CliffordAlgebra code itself are reasonably minor
(some additional coercions and formatting changes). The main change is
the addition of a new domain called PauliMatrix.

The main reason for the domain PauliMatrix is to prepare to make
recip(), which is the Clifford multiplication inverse, work correctly
for non-diagonal forms.

The Clifford multiplication inverse is important for geometric
applications so I am very keen to find a way to do this.

In addition to this I think the PauliMatrix domain is worthwhile in
its own right, because,
* It gives a different way to calculate the Clifford multiplication
and so the two domains can check each other.
* Some textbooks use the PauliMatrix notation.
* It may help people like me, who are trying to learn the subject, to
be able to approach the topic from two different directions.

The main issue is that, although I can coerce between representations
of CliffordAlgebra, PauliMatrix and back again, I cannot generate a
CliffordAlgebra type from a PauliMatrix type or generate a PauliMatrix
type from a CliffordAlgebra type. That is I cannot generate the matrix
bases from the bilinear form or visa-versa.

From what I can make out the Rafal Ablamowicz method (Also see Pertti
Lounesto 2nd ed P225) is that matrix will itself satisfy the
characteristic polynomial equation obeyed by its own eigenvalues and
that therefore the equivalent Clifford number (multivector) will also
obey the same characteristic equation. Unfortunately I can't work out
how to use this.

I think the best way to explain the other issues involved is in the
following session:

-- First we will create a Clifford algebra and its corresponding
-- Pauli matrix. The Clifford algebra is created from the bilinear
form
-- and the Pauli matrix is created from basis matrices. At this stage,
-- we have to know the equivalents already, since I don't yet know an
-- algorithm to convert between bilinear form and basis matrices.
)library CLIF

CliffordAlgebra is now explicitly exposed in frame frame1
CliffordAlgebra will be automatically loaded when needed from
/home/martin/CLIF.NRLIB/CLIF
)library PAULI

PauliMatrix is now explicitly exposed in frame frame1
PauliMatrix will be automatically loaded when needed from
/home/martin/PAULI.NRLIB/PAULI
K := Fraction(Integer)

(1) Fraction(Integer)

Type: Type
CA := CliffordAlgebra(2,K,[[1,0],[0,1]])

(2) CliffordAlgebra(2,Fraction(Integer),[[1,0],[0,1]])

Type: Type
PM := PauliMatrix(2,false,2,K,[matrix[[1,0],[0,-1]],matrix[[0,1],
[1,0]]])

(3) PauliMatrix(2,false,2,Fraction(Integer),[MATRIX,MATRIX])

Type: Type
--
-- we can get confidence that these two are equivalent by checking
that
-- their multiplication tables are equivalent:
toTable(*)$CA + 1 e e e e + | 1 2 1 2| | | | e 1 e e e | | 1 1 2 2 | (4) | | | e - e e 1 - e | | 2 1 2 1| | | |e e - e e - 1 | + 1 2 2 1 + Type: Matrix(CliffordAlgebra(2,Fraction(Integer),[[1,0], [0,1]])) toTable()$PM

+ +1 0+ +1 0 + +0 1+ + 0 1+ +
| | | | | | | | | |
| +0 1+ +0 - 1+ +1 0+ +- 1 0+ |
| |
|+1 0 + +1 0+ + 0 1+ +0 1+ |
|| | | | | | | | |
|+0 - 1+ +0 1+ +- 1 0+ +1 0+ |
(5) | |
| +0 1+ +0 - 1+ +1 0+ +- 1 0+ |
| | | | | | | | | |
| +1 0+ +1 0 + +0 1+ + 0 1+ |
| |
|+ 0 1+ + 0 - 1+ +1 0 + +- 1 0 +|
|| | | | | | | ||
++- 1 0+ +- 1 0 + +0 - 1+ + 0 - 1++
Type: Matrix(PauliMatrix(2,false,2,Fraction(Integer),
[MATRIX,MATRIX]))
--
-- we can coerce both ways between these domains but we have to coerce
via
-- List. I can't write a direct coercion because, at compile time, the
-- Clifford algebra does not know the exact signature of Pauli matrix
and
-- Pauli matrix does not know the exact signature of Clifford algebra.
-- Is there a way round this?
-- However we can see here that the round trip c1 -> p1 -> c2 gets us
-- back to where we started.
c1 := [1::K,2::K,3::K,4::K]::CA

(6) 1 + 2e + 3e + 4e e
1 2 1 2
Type: CliffordAlgebra(2,Fraction(Integer),[[1,0],
[0,1]])
p1 := c1::List K::PM

+ 3 7 +
(7) | |
+- 1 - 1+
Type: PauliMatrix(2,false,2,Fraction(Integer),
[MATRIX,MATRIX])
p1 := c1::PM

Cannot convert from type CliffordAlgebra(2,Fraction(Integer),
[[1,0],
[0,1]]) to PauliMatrix(2,false,2,Fraction(Integer),
[MATRIX,MATRIX
]) for value
1 + 2e + 3e + 4e e
1 2 1 2

c2 := p1::List K::CA

(8) 1 + 2e + 3e + 4e e
1 2 1 2
Type: CliffordAlgebra(2,Fraction(Integer),[[1,0],
[0,1]])
--
-- we can check that multiplication is the same for non-basis values:
c3 := [5::K,6::K,7::K,8::K]::CA

(9) 5 + 6e + 7e + 8e e
1 2 1 2
Type: CliffordAlgebra(2,Fraction(Integer),[[1,0],
[0,1]])
p3 := c3::List K::PM

+11 15 +
(10) | |
+- 1 - 1+
Type: PauliMatrix(2,false,2,Fraction(Integer),
[MATRIX,MATRIX])
c1*c3

(11) 6 + 20e + 14e + 24e e
1 2 1 2
Type: CliffordAlgebra(2,Fraction(Integer),[[1,0],
[0,1]])
p4 := p1*p3

+ 26 38 +
(12) | |
+- 10 - 14+
Type: PauliMatrix(2,false,2,Fraction(Integer),
[MATRIX,MATRIX])
c4 := p4::List K::CA

(13) 6 + 20e + 14e + 24e e
1 2 1 2
Type: CliffordAlgebra(2,Fraction(Integer),[[1,0],
[0,1]])
--
-- we can also check that division is the same (at least for
orthogonal basis)
p5 := [3/10::K,0::K,0::K,2/5::K]::PM

+ 3 2 +
|-- - |
|10 5 |
(14) | |
| 2 3|
|- - --|
+ 5 10+
Type: PauliMatrix(2,false,2,Fraction(Integer),
[MATRIX,MATRIX])
p6 := inverse(p5)$PM +6 8+ |- - -| |5 5| (15) | | |8 6 | |- - | +5 5 + Type: Union(PauliMatrix(2,false,2,Fraction(Integer), [MATRIX,MATRIX]),...) c5 := p5::List K::CA 3 2 (16) -- + - e e 10 5 1 2 Type: CliffordAlgebra(2,Fraction(Integer),[[1,0], [0,1]]) c6 := recip(c5)$CA

6 8
(17) - - - e e
5 5 1 2
Type: Union(CliffordAlgebra(2,Fraction(Integer),[[1,0],
[0,1]]),...)
c6 := p6::List K::CA

6 8
(18) - - - e e
5 5 1 2
Type: CliffordAlgebra(2,Fraction(Integer),[[1,0],
[0,1]])
(19) ->

So far we have only considered an algebra based on a 2D space. In this
case
the dimension of the multivector is 2^2 and the dimension of the Pauli
matrix
is 2 by 2. Although the code is written for the 'n' dimensional case I
don't
know if this is valid for 'n' dimensional space? Can we
always represent an 2^n dimensional multivector by a nxn dimensional
Pauli
matrix? Usually 3D space is represented by a matrix of complex
numbers, so
we have a multivector of dimension 2^3 represented by a 2x2 Pauli
matrix
containing complex numbers. In what circumstances can we represent an
2^n
dimensional multivector by a (n-1)x(n-1) dimensional Pauli matrix?

How can I allow for both possibilities in the same domain? My first
thought
was to specify the type and dimension of the multivector and matrix
desperately in the constructor. However, even if they are both of type
Field,
we can't coerce or even 'pretend' between them. So then I thought of
having a
boolean value cmplx in the constructor and then defining the types
like this:

K : Field -- type of multivector
C ==> (if cmplx then Complex K else K) -- type of elements of matrix

but I can't use C as if it were were a type? I thought of using:

if cmplx then C : Complex K else C : K

but cmplx is only known at runtime so this won't compile. I even
thought of
defining something like this:

C : Union(K,Complex K)

but I can't work how to use it?

Sorry again this message is so long but I would appreciate any ideas.

Martin B.

### Waldek Hebisch

Feb 13, 2010, 1:19:06 PM2/13/10
Martin Baker wrote:
> I am stuck in implementing a PauliMatrix domain, The issues are mostly
> with the mathematics involved but I also have some issues with how to
> implement in FriCAS. I would appreciate any pointers you could give
> me. I will explain the issues below (sorry it is so long).
>
> http://github.com/martinbaker/multivector/
> All the code and documentation is there.
>
> The changes to the CliffordAlgebra code itself are reasonably minor
> (some additional coercions and formatting changes). The main change is
> the addition of a new domain called PauliMatrix.
>
> The main reason for the domain PauliMatrix is to prepare to make
> recip(), which is the Clifford multiplication inverse, work correctly
> for non-diagonal forms.
>
> The Clifford multiplication inverse is important for geometric
> applications so I am very keen to find a way to do this.
>
> In addition to this I think the PauliMatrix domain is worthwhile in
> its own right, because,
> * It gives a different way to calculate the Clifford multiplication
> and so the two domains can check each other.
> * Some textbooks use the PauliMatrix notation.
> * It may help people like me, who are trying to learn the subject, to
> be able to approach the topic from two different directions.
>

I wonder if you really need a domain like PauliMatrix. Namely, your
PauliMatrix matrix bundles matrices with with transformation between
ClifforAlgebra and matrices. That is rather heavy and I wonder if
you gain something compared to having a package which converts
between CliffordAlgebra and matrices. Even if really want
PauliMatrix it makes sense to create package fist and use domain
just as a nicer wraper.

> The main issue is that, although I can coerce between representations
> of CliffordAlgebra, PauliMatrix and back again, I cannot generate a
> CliffordAlgebra type from a PauliMatrix type or generate a PauliMatrix
> type from a CliffordAlgebra type. That is I cannot generate the matrix
> bases from the bilinear form or visa-versa.

something different). FriCAS allows you to computation on types,
but for that you need apropriate categories. There is a significant
limitation: officially you can not "deconstruct" a type to learn
about its parameters. One can work around this problem in two
ways. One is to add aproproate accessor functions to give you
back parameters, another way is to use Lisp level functions
to access parameters. Also, currently there
is limitation that in interpreter type valued functions have to
return 'Type' (and not an arbitrary category). So (assuming we
added aproproate accessors) you need something like:

CliffordAlgebra_from_PauliMatrix(A : Type, K : Type) : Type ==
if A has PauliMatrixCategory then
K := baseField(A)
ml := basesList(A)
-- compute quadratic form and n
-- ...
return CliffordAlgebra(n, qf)
else
error "Not a PauliMatrix"

Another issue is how to compute quadratic form from Pauli
matrices, or matrices form quadratic form. Well, as long as
we forget about non-symmeric forms getting form is easy:

M(i)*M(j) + M(j)*M(i) = qf(i, j)*I

(where M(i) is i-th Pauli matrix), so you compute M(i)*M(j) + M(j)*M(i),
check that the result is scalar multiple of identity matrix and use
the scalar as i,j entry in the form. AFAICS Pauli matrices contain
no information about non-symmetric part of the form.

Going from algebra to matrices is not a function: you can apply any
authmorphizm of ring of matrices to one set of Pauli matrices and
get another one (usually different) which is as good as original.

> -- we can coerce both ways between these domains but we have to coerce
> via
> -- List. I can't write a direct coercion because, at compile time, the
> -- Clifford algebra does not know the exact signature of Pauli matrix
> and
> -- Pauli matrix does not know the exact signature of Clifford algebra.
> -- Is there a way round this?

Such coercions are normally defined in packages. You have package
like:

CliffordPauliCoercion(Ca : CliffordAlgebra(...), Pm : PauliMatrix(...),
...) with
coerce: Pm -> Ca
coerce: Ca -> Pm
-- here you need to implement them
-- ...

>
> So far we have only considered an algebra based on a 2D space. In this
> case
> the dimension of the multivector is 2^2 and the dimension of the Pauli
> matrix
> is 2 by 2.

It is a bit more tricky: two dimensional Clifford algebra over
rational numbers may allow only four dimensonal matrices over
rational numbers (or complex rational numbers). Pauli constriction
over complex numbers is enough only because complex numbers are
algebraically closed and consequently there is only one
(up to isomorphizm) Clifford algebra on space of dimension 2 over
complex numbers.

> Although the code is written for the 'n' dimensional case I
> don't
> know if this is valid for 'n' dimensional space? Can we
> always represent an 2^n dimensional multivector by a nxn dimensional
> Pauli
> matrix?

No, you need higher dimension. For standard form over real or complex
numbers representations of Clifford algebra are classified, you get
things like real matrices, complex matrices or matrices over
quaternions. There is pattern of perid 2 over complex numbers
and perid 8 over real numbers. Non-standard form should give
you only trivial changes, but for examples Clifford algebras
over rational numbers are more "interesting".

BTW: Even if you think that only real/complex numbers are
of physical/geometrical significance, remember that computer
can directly handle only rationals and algebraic extensions,
so rationals are very relevant to computations.

--
Waldek Hebisch
heb...@math.uni.wroc.pl

### Martin Baker

Feb 15, 2010, 11:12:57 AM2/15/10
Thanks, this is very interesting but there are some things I don't understand:

On Saturday 13 Feb 2010 18:19:06 Waldek Hebisch wrote:
> I wonder if you really need a domain like PauliMatrix. Namely, your
> PauliMatrix matrix bundles matrices with with transformation between
> ClifforAlgebra and matrices. That is rather heavy and I wonder if
> you gain something compared to having a package which converts
> between CliffordAlgebra and matrices. Even if really want
> PauliMatrix it makes sense to create package fist and use domain
> just as a nicer wraper.

The algorithms and code that I have used to convert representations of
PauliMatrix to CliffordAlgebra are heavy (I would welcome a better algorithm).
However I can't work out whats wrong with the overall architecture and why
having a separate package for converting would be more efficient? Every way
that I can think of to do it the way you suggest seems less efficient, I can't
see the benefit of starting another process? PauliMatrix inherits all the
matrix code from SquareMatrixCategory so its similar to SquareMatrix domain
except that it has extra functions and variables defined, I can't work out
what is to be gained by putting these functions and variables into a separate
package? Would you suggest starting up the package, creating all the linear
equations and then shutting it down for every single conversion?

Also I like the idea of PauliMatrix and CliffordAlgebra having the same
interface (called say CliffordAlgebraCategory?). Not only would this be easier
for users but also higher level compiled code could be defined in terms of
CliffordAlgebraCategory, it could then be quickly switched between the two
implementations to keep the same functionality but fine tune the speed and
memory usage.

> Another issue is how to compute quadratic form from Pauli
> matrices, or matrices form quadratic form. Well, as long as
> we forget about non-symmeric forms getting form is easy:
>
> M(i)*M(j) + M(j)*M(i) = qf(i, j)*I

I guess you mean: M(i)*M(j) - M(j)*M(i) = qf(i, j)*I
This makes sense as they both represent the inner product of two vectors.
I will implement this.
I will have to think about how to go from CliffordAlgebra to PauliMatrix as
this seems to involve, starting with a multiplication table and then working
out what matrices would produce it.

> > -- we can coerce both ways between these domains but we have to coerce
> > via
> > -- List. I can't write a direct coercion because, at compile time, the
> > -- Clifford algebra does not know the exact signature of Pauli matrix
> > and
> > -- Pauli matrix does not know the exact signature of Clifford algebra.
> > -- Is there a way round this?
>
> Such coercions are normally defined in packages. You have package
> like:
>
> CliffordPauliCoercion(Ca : CliffordAlgebra(...), Pm : PauliMatrix(...),
> ...) with
> coerce: Pm -> Ca
> coerce: Ca -> Pm
> -- here you need to implement them
> -- ...

When you write '...' in CliffordAlgebra(...) does that mean the full signature
has to be inserted (which I don't know at compile time) or is '...' an actual
keyword which the compiler will accept?

Martin

### Ralf Hemmecke

Feb 15, 2010, 4:41:00 PM2/15/10
>> Such coercions are normally defined in packages. You have package
>> like:
>>
>> CliffordPauliCoercion(Ca : CliffordAlgebra(...), Pm : PauliMatrix(...),
>> ...) with
>> coerce: Pm -> Ca
>> coerce: Ca -> Pm
>> -- here you need to implement them
>> -- ...
>
> When you write '...' in CliffordAlgebra(...) does that mean the full signature
> has to be inserted (which I don't know at compile time) or is '...' an actual
> keyword which the compiler will accept?

No, '...' is not a keyword. you have to be explicit.

Look at your definition of CliffordAlgebra. You have:

CliffordAlgebra(n, K, bLin)

and similar for PauliMatrix

Now, of course, you must tell CliffordPauliCoercion about these
parameters, i.e. you start by

CliffordPauliCoercion(
n: PositiveInteger,
K: Field,
bLin: SquareMatrix(n, K),
-- Here come additional parameters for PauliMatrix.
-- Maybe you can reuse n and K.
-- With what I'v used here in Pm, you would have
-- to declare cmplx and Bases.
Ca: CliffordAlgebra(n, K, blin),
Pm: PauliMatrix(2, cmplx, n, K, Bases)): with

coerce: Pm -> Ca
coerce: Ca -> Pm

-- here you need to implement the coerce functions.

Is this a bit clearer?

Ralf

PS: The parameter "cmplx" in your PauliMatrix definition looks
superfluous to me.

PS2: And (others might disagree) any function code that does not specify
the argument types and return type is frown upon (at least by me).

Something like
coerce(mv:List(K)): % == ...
is OK. Something half specified like
monomial(c, lb) ==
is not. I even don't like it although you have declared
c: K
further above. (lb is undeclared, though.)

### Martin Baker

Feb 16, 2010, 4:02:25 AM2/16/10
Ralf,

On Monday 15 Feb 2010 21:41:00 Ralf Hemmecke wrote:
> CliffordPauliCoercion(
> n: PositiveInteger,
> K: Field,
> bLin: SquareMatrix(n, K),
> -- Here come additional parameters for PauliMatrix.
> -- Maybe you can reuse n and K.
> -- With what I'v used here in Pm, you would have
> -- to declare cmplx and Bases.
> Ca: CliffordAlgebra(n, K, blin),
> Pm: PauliMatrix(2, cmplx, n, K, Bases)): with
> coerce: Pm -> Ca
> coerce: Ca -> Pm
> -- here you need to implement the coerce functions.
>
> Is this a bit clearer?

Yes thanks, this makes it clearer, I will experiment with creating a package
like this.

> PS: The parameter "cmplx" in your PauliMatrix definition looks
> superfluous to me.

Yes it is superfluous in the current code, but the current code only works
when both CliffordAlgebra and PauliMatrix are defined over K (or both over
Complex K) but not when CliffordAlgebra is defined over K and PauliMatrix is
defined over Complex K.

I am still working through the detail of Waldek s reply so hopefully I will
find a way to do it.

Even better if it will allow a further option of CliffordAlgebra defined over
K and PauliMatrix is defined over Quaternian K.

> PS2: And (others might disagree) any function code that does not specify
> the argument types and return type is frown upon (at least by me).

I am used to languages like java where function declarations and definitions
are combined and also where there is less type inference. Having said that I
often tend to duplicate everything, including the comments, in both the
declaration and definition.

Martin

### Ralf Hemmecke

Feb 16, 2010, 4:39:12 AM2/16/10
> I wonder if you really need a domain like PauliMatrix.

probably something more than just providing 4 matricies as described at
http://mathworld.wolfram.com/PauliMatrices.html .

Pauli matrices.

As I understand it, if one haves a set of "Pauli matrices", then they
can basically be seen as basis elements of a Clifford algebra, i.e.
multiplication is implicitly given, you wouldn't have a need of a bLin
parameter as in the definition of your CliffordAlgebra domain.

The first thing you should think about is what operations should be
exported from a PauliMatrix domain. Can you provide that?

According to what you have currently implemented, any square matrix can
be considered (i.e. coerced to) a Pauli matrix.
Maybe I am wrong, but I would call the elements of what you have called
Bases the Pauli matrices

and the domain that you called PauliMatrix, you should perhaps call
PauliAlgebra. I don't know if that is already a well established name.
Most probably, the algebra you get is a clifford algebra, no? But, if
your domain then claims to export all operations that CliffordAlgebra
exports, you must make a thorough test that the given 'Bases' really
leads to something well-behaving. Otherwise a user could create a
PauliAlgebra (ehm, Clifford algebra), that does not behave as claimed by
you, because, the user just gives completely useless parameters.

I'm really not sure whether your Pauli concept makes any sense. So what
is it that you want to express?

Ralf

### Ralf Hemmecke

Feb 16, 2010, 4:54:16 AM2/16/10
Martin,

>> Is this a bit clearer?
>
> Yes thanks, this makes it clearer, I will experiment with creating a package
> like this.

perhaps it would make more sense to further work directly in the FriCAS
tree. Just clone FriCAS as described at

http://axiom-portal.newsynthesis.org/Members/hemmecke/use-github-mirror-of-fricas-svn-repository

Tell me if you find anything that is unclear to you.

repository and do further work there.

Whether and how your code gets eventually integrated into fricas at
sourceforge is another question. But use git freely and create branches
at your will to try out certain ideas. And throw away branches if you
find out that your idea did not lead to anything you really like.

>> PS: The parameter "cmplx" in your PauliMatrix definition looks
>> superfluous to me.

> Yes it is superfluous in the current code, but the current code only works
> when both CliffordAlgebra and PauliMatrix are defined over K (or both over
> Complex K) but not when CliffordAlgebra is defined over K and PauliMatrix is
> defined over Complex K.

As I wrote in my previous mail, the whole PauliMatrix concept is
currently questionable to me.

> Even better if it will allow a further option of CliffordAlgebra defined over
> K and PauliMatrix is defined over Quaternian K.

Well, why must the K of CliffordAlgebra have anything to do with the K
of PauliMatrix. I don't understand this and thus any options there make
no sense to me. Can you first explain, what your PauliMatrix concept is?

Ralf

### Martin Baker

Feb 16, 2010, 11:10:50 AM2/16/10
to FriCAS - computer algebra system
I agree I have misused Pauli's name and that his name should really be
restricted to Spin(3) or SU(2) groups (quaternions). I just can't
think of a snappy name for an 'n' dimensional square matrix with a
variable containing the bases and functions to convert to and from
multivectors.

The main thing that concerns me is to find a way to calculate the
Clifford inverse (current implementation is wrong for non-orthogonal
bases) although even if there is a way to implement this within the
CliffordAlgebra domain I still think the PauliMatrix (until we think
of a better name) has educational and (in a few special cases)

I have looked at the arXiv documents that Bertfried Fauser mentioned
but I can't find information about the Clifford inverse (I may have
missed it?). I don't have access to a book library to check the other
references.

The best information I can find online is this paper by Dr John P.
Fletcher of Aston
University:
http://www.ceac.aston.ac.uk/research/staff/jpf/papers/paper24/index.php

I get the impression, from this paper, that the conversion from
CliffordAlgebra to matrix is computationally intensive and that at the
very least we would want to cache the eigenvalues. Even so, if we were
doing multiple calculations (such as a sequence of transforms), would
it really make sense to convert to and from matrices repeatedly?

It is quite hard for me to try to work out an architecture that does
these things from the bottom up. Ideally I suppose that it would be
nice if someone who knows the big picture, like Bertfried Fauser if
he were not so busy, had the time to define a set of domains in such a
way that they all interworked together rather than being isolated
domains. I am thinking about related classes of algebras like:
Spinors, Hopf Algebras, Clifford Algebras and so on. Are they all
derived from tensors? Do they form some sort of hierarchy? For
performance reasons I guess you would not want to implement them by
inheriting from tensors but in some other way that allowed them to
interwork. This would give a structure to relate new domains to and
might also help with a consistent naming structure.

I probably don't know what I'm talking about here but I would be
interested to hear what your views are about where FriCAS should be
headed regarding these algebras and do you have any structure in mind?

Martin

### Ralf Hemmecke

Feb 16, 2010, 12:28:20 PM2/16/10
Martin,

> I probably don't know what I'm talking about here but I would be
> interested to hear what your views are about where FriCAS should be
> headed regarding these algebras and do you have any structure in mind?

I think in order to implement all these mathematical concepts you should
get more familiar with programming ins SPAD. In particular you should
understand that there are categories, domains, and packages.

From your last mail I get the impression that you only think in terms
of domains. But if you want to implement a hierarchy of structures in
FriCAS, you should rather first think about categories, i.e. what
functions and properties should a particular algebra export in order to
be useful. A category is the type of a domain. So there might be several
domains that implement the same category. (In fact, in simple terms a
Fricas-category is nothing else than what is known in Java by the name
Interface --- only that SPAD does not lose type information.)
For example, you can implement all operations of univariate polynomials
using a dense or sparse representation, i.e. there is one category of
univariate polynomials and two domains (sparse and dense) that implement
this category/interface.

Similarly, your PauliMatrix (or however you will call it---you migth
call it FooBar and rename later), looks just like another way (i.e.
another domain) to implement the interface (ehm the category) of a
clifford algebra. It's only that you have not yet separated the category
of CliffordAlgebra into a separately named category.

In fact, just extract the T from

put it outside CliffordAlgebra and say something like

CliffordAlgebraCategory(K: Field): Category == T where
T ==> Join(Ring, Algebra(K)) with ...

then you could say

CliffordAlgebra(n, K, bLin): CliffordAlgebraCategory(K) == Impl where
...

You see, I have not given an n in the arguments of
CliffordAlgebraCategory. Think about it. Does that make sense? I don't
know, but if I look at the actual list of exports, I don't see any n
involved, so there would be no need.

Ralf

### Waldek Hebisch

Feb 18, 2010, 9:31:44 AM2/18/10
Martin Baker wrote:
>
> On Saturday 13 Feb 2010 18:19:06 Waldek Hebisch wrote:
> > I wonder if you really need a domain like PauliMatrix. Namely, your
> > PauliMatrix matrix bundles matrices with with transformation between
> > ClifforAlgebra and matrices. That is rather heavy and I wonder if
> > you gain something compared to having a package which converts
> > between CliffordAlgebra and matrices. Even if really want
> > PauliMatrix it makes sense to create package fist and use domain
> > just as a nicer wraper.
>
> The algorithms and code that I have used to convert representations of
> PauliMatrix to CliffordAlgebra are heavy (I would welcome a better algorithm).
> However I can't work out whats wrong with the overall architecture and why
> having a separate package for converting would be more efficient?

I am not talking about efficiency. Using separate domain is an
"abstraction barrier": you inherit operation from SquareMatrix,
but other operations on square matrices are unavailable. This
makes sense if you think of PauliMatrix as something quite
different than SquareMatrix. But mathematically what matters
is mapping between CliffordAlgebra and matrices. Once you
get a matrix it is just a square matrix, behaving exactly
like any other square matrix.

Having a package for conversion means that you can naturally
use both points of view. Starting from PauliMatrix domain
means makes the other point of view more clumsy.

On related thing: Pauli matrices are really an example of
representation of Clifford algebra. It make sense to consider
domain consiting of all (possibly with some equivalences)
representaions of given Clifford algebra. In diagonal case
such domain is not very interesing (there is one base representaion
and a well-known way to produce all other from it). But
in more general cases studying representations may be of
some interst (for example your search for general "Pauli matrices"
is more or less equvalent to computing basic representation).

> Also I like the idea of PauliMatrix and CliffordAlgebra having the same
> interface (called say CliffordAlgebraCategory?). Not only would this be easier
> for users but also higher level compiled code could be defined in terms of
> CliffordAlgebraCategory, it could then be quickly switched between the two
> implementations to keep the same functionality but fine tune the speed and
> memory usage.

OK, you can have that. My point is that it makes sense to separate
definition of a domain from actual functionality, because then it
is easer to reuse functionality.

>
> > Another issue is how to compute quadratic form from Pauli
> > matrices, or matrices form quadratic form. Well, as long as
> > we forget about non-symmeric forms getting form is easy:
> >
> > M(i)*M(j) + M(j)*M(i) = qf(i, j)*I
>
> I guess you mean: M(i)*M(j) - M(j)*M(i) = qf(i, j)*I

I mean '+' (check what your formula gives for i = j). I forgot
factor of 2: M(i)*M(j) + M(j)*M(i) = 2*qf(i, j)*I

> This makes sense as they both represent the inner product of two vectors.
> I will implement this.
> I will have to think about how to go from CliffordAlgebra to PauliMatrix as
> this seems to involve, starting with a multiplication table and then working
> out what matrices would produce it.
>

That is coverd by "representation theory". It is easy to get one
representation. Nameley, CliffordAlgebra is a vector space of
dimension 2^n. Any linear operator on this space gives you
2^n by 2^n matrix. In particular, put:

M(i)(x) = e(i)*x

This is a family of n operators which gives you representation of
the CliffordAlgebra. This representation is somewhat wasteful, because
2^(n/2) by 2^(n/2) (possibly rounded up) should already do. But
it it possible to use it to find other representations (FriCAS
contains "Meat Axe" procedure which should be able to do this).

And certainly you can use the representation above to compute
inverses. While using high-dimensional matrix looks inefficient,
a priori it hard to tell which procedure for computing inverses
gives more possibility for optimization.

--
Waldek Hebisch
heb...@math.uni.wroc.pl

### Martin Baker

Feb 18, 2010, 1:21:47 PM2/18/10
On Thursday 18 Feb 2010 14:31:44 Waldek Hebisch wrote:
> That is coverd by "representation theory". It is easy to get one
> representation. Nameley, CliffordAlgebra is a vector space of
> dimension 2^n. Any linear operator on this space gives you
> 2^n by 2^n matrix. In particular, put:
>
> M(i)(x) = e(i)*x
>
> This is a family of n operators which gives you representation of
> the CliffordAlgebra. This representation is somewhat wasteful, because
> 2^(n/2) by 2^(n/2) (possibly rounded up) should already do. But
> it it possible to use it to find other representations (FriCAS
> contains "Meat Axe" procedure which should be able to do this).

Thank you very much, this is very interesting, before I do anything else I
think I need to take plenty of time to learn what I can about representation
theory.

I have just done a quick web search on the term and I get the impression that
"Clifford Module" is the more general term for what I have been calling "Pauli
Matrix"?

> And certainly you can use the representation above to compute
> inverses. While using high-dimensional matrix looks inefficient,
> a priori it hard to tell which procedure for computing inverses
> gives more possibility for optimization.

On my searches on the web, matrix inversion is the only method that I have
found. I think I did see mention of a method that did not involve conversion
to matrices, but I can't remember where I saw it now, I think it was more of a
research topic than an established method?

I get the impression that its not the matrix itself that is the problem but
the higher dimensional matrix required to decompose it back into a
multivector.

Even if this is the only method there may be some optimisations that can be
done in special cases, for example if the conjugate exists so that multiplying
by the conjugate gives a scalar divider.

Anyway I'm off to try to learn about representation theory.

Martin Baker

### Bertfried Fauser

Mar 13, 2010, 9:58:26 AM3/13/10
Hi Martin,

sorry for being quiet, but I was not well and burried in work....

May I comment a bit on the relation between abstract Clifford algebra
and concrete matrix examples...

* Let K=C be the algebraic closed field of complex numbers and
consider Clifford alegbras CL_n
over V~=C^n, and n-dim vector space, of course equipped with a
(symmetric) bilinear form B
stemming from a quadratic form on V.
You will find two types of Clifford algebras, simple and semisimple
ones. The semisimples turn out to
be a direct sum of two simple ones.
If you look for a (matrix) representation of such Clifford algebras,
you want a faithful representation, which
does not loose any information about CL_n. Minimal such
representations are spinor representations. An
easy way to construct such representations is by constructing a
minimal left (right) ideal in CL_n, which
can be done by picking a minimal idempotent element. Construct it
as follows. Pick an element e_1 in
CL_n which squares to 1 (over C you always can achieve this by
multiplying with a complex number).
Find another element e_2 which commutes with e_1 and squares also to
1 and proceed to find mutually
commuting elements squaring to 1, say {e_i}_i=1^m (m will be n or
n-1 in the complex case), form
f = \prod (1/2(1+e_i), then f is a minimal idempotent.
Consider the spinor space S(f) = CL_nf, seen as left ideal in CL_n.
This space has an action of the
Clifford algebra by left multiplication, hence carries a
representation. If n is odd (n=2m+1) then the
volume element w=e1/\.../\en will be central and you find two such
spinor spaces which are not
equivalent, hence the Clifford algebra is not simple, so let n be even (n=2m).

Pick a basis in V, construct f as above and study the stabilizer
group G_n of f in the group of conjugations
on CL_n leaving V invariant G_n = { x \in CL_n | x^-1 exists and
xvx^{-1} \in V for all v in V }, the
transversal in G_n will provide you with elements {m_i} such that
{m_if} form a basis of the spinor
space S(f).

Now, any element in CL_n can be expanded into the Grassmann basis,
and if we choose a basis such that
the bilinear form is diagonal the Clifford and Grassmann basis are
equivalent, setwise. A matrix spinor
representation is then given by constructing the representing
matrices for the basis {e_i} of V as
e_i S(f) --> e_i m_jf = c_{ij}^k m_kf
and [e_i] ~= [ c_{ij}^k ] provides the matrix (for fixed i)
representing e_i. This is a homomorphism, so that
[e_i e_j] = [e_i] [e_j] where the hight hand side is matrix
multiplication (due to the implicit usage of the
dual basis for the index k and evaluation V^*x V - > C)
Note: when you chose a non-orthonormal/gonal basis then the matrices
will look very different, if the
bilinear form is not symmetric, then the whole theory looks
different andyou get exotic spinor
spaces.

A Clifford module should be seen as a bundle formed over the
Clifford bundle over the (co)tangent space
over a complex manifold (orientable, with spin structure). Naively a
Clifford module provides you with
'matrix representations' where the entries of the matrixes are
functions (in a coordnate sytem in a patch
of the manifolds atlas).

In the semi simple case you get two matrices on the two spinor
spaces and take their direct sum as
representation.

Note: Complex Clifford algebras have complex matrix representations.

* The real case is way more complicated. Suppose you have a real
Clifford algebra over R^n, with a
quadratic form normalized to Q_p,q with p plus signs q minus signs
(no zeros, we assume its non
degenerate). Searching as above for commuting elements will run
possibly short, since you may find
elements which commute but square to minus one. Since no complex 'i'
is available, you cannot use
these to form the primitive idem potent element f and the result is
that you may gather up a center.
The center is a possibly skew double filed of the following type
L = {R , C , H, R+R, H+H } R=reals, C=complex, H=quaternions, R+R
double reals, H+H
double quaternions. In case Cl_p,q is simple, K \in L is a (skew)
field R,C,H and your spinor space
will be a right module over this skew field, hence S(f) has a left
CL_p,q action and a right K action.
CL_p,q x K x S(f) --> S(f) :: (x,\lambda,\psi) |---> x\psi\lambda
of course in the case K=R,C left and right actions coincide.

Note: A _real_ Cliffordagebra may have real, complex or quaternionic
spinor representations.

Example: Pauli matrices.
Consider R^3 with the Euclidean quadratic form R_{3,0}, and the
basis of R^3 as {e_1,e_2,e_3}, the
basis of the Clifford algebra is (wedge or Clifford does not matter
for orthonormal bases)
B = { 1, e1, e2, e12, e3, e13, e23, e123 } and is 8 dim. We find say
e1^2=1 and the only elements
in B commuting with e1 are e23 and e123 (besides 1 which we ignore
as trivial element). Now observe
that e23^2=-1 is not central, but e123^2=-1 is central. So we get a
center spanned by {1,e123} isomorphic
to the complex numbers. Our idempotent element is f=1/2(1+e1) and
the transversal of m_i's is given by
{1,e2} so S(f) has a spinor basis {f,e2f} and the representing
matrices will be 2x2, but having a complex
right action, so matrix entries will be in {1,e123=i}, hende the
matrix representation is 2x2 over the
complex(!) numbers, but these complex numbers are modelled inside of
the real Clifford algebra.

What is the matrix of e_1 itself: Compute

e1 f = f, and e1 e2f = -e2f, so
[e1] = [ 1 0 ]
[ 0 -1]
and we identify [e1] = \sigma_3 (with the usual definition of the
Pauli matrices, one could rename the
ei so that [ei] = \sigma_i though)

e2f = e2f and e2e2f = f, so we get

[e2] = [0 1] and [e2] = \sigma_1
[1 0]

while e3f = -e12 e123 f = -e12 f e123 = e2 e1 f e123 etc hence with
e123=i we have
[e3] = [e2][e1]i =
= [ 0 -i ] = \sigma_2
[ i 0 ]
this was easy since CL_3,0 is simple, in the semi simple case you get
even two such matrices which have
to be combined in a direct sum. The maximal number of commuting
elements is called the
Radon-Hurwitz number, which allows you to see what the center has to
look like since we know the algeba
module has to be of real(!) dimension 2^n with n=p+q. And in the
above example you find Mat(2x2,R)
has 4 real dimensions while the centre C has 2 real dimensions which
multiply together to give 8 real dim.

* Computational aspects.
I do not see that using matrix multiplication has any benefit over a
direct computation of the Grassmann
or Clifford product. Unless you don't have a real need to look into
the spinor spaces, It is not necessary
to construct them and it will be in general (for real Cifford
algebra) also not be easy. Moreover, the
construction of a matrix representation has to select several
things, such as a basis for the Clifford algebra,
a minima idem potent elements (there are several such isomorphic
idempotents) a transversal to form the
spinor basis and an identification with the (skew double) ring
underlying the spinor space. All this has to be
done in a consitent manner. Still, see example above, the resulting
matrices will not be what you expect
[e_i] = \sigma_\pi(i) for some permutation \pi, so you need to
identify them somehow.

Good sources to look at these things are:

Paolo Budinich, Andrej Trautman, The spinorial chessboard
Perrti Lounesto, Clifford agebras ad spinors
Ian Porteous, Clifford algebras and the classical groups

there are more advanced books looking into spin geometry and manfifolds...

Hope this helps a bit (to confuse you?)
Cheers
BF.

--
% PD Dr Bertfried Fauser
% Research Fellow, School of Computer Science, Univ. of Birmingham
% Honorary Associate, University of Tasmania
% Privat Docent: University of Konstanz, Physics Dept
<http://www.uni-konstanz.de>
% contact |-> URL : http://www.cs.bham.ac.uk/~fauserb/
% Phone : +44-121-41-42795

### Martin Baker

Mar 13, 2010, 11:49:58 AM3/13/10
Hi Bertfried,

Thank you very much for this, it is very helpful, as usual it will take me a
long time to absorb this.

I do have one quick question so far, you say:

> * Computational aspects.
> I do not see that using matrix multiplication has any benefit over a
> direct computation of the Grassmann
> or Clifford product. Unless you don't have a real need to look into

> the spinor spaces, It is not necessary<snip>

Does this also apply to finding the Clifford inverse? (if it exists)

Regardless of the answer to this I do like the idea of being able to compute
the matrix representation if only to check results independently and for
educational use.

I have written some FriCAS/Axiom code to convert from a Clifford
multiplication table into a finite group domain and then from this to a
permutation group. this can then use the built in code to generate a
representation and also use meatAxe to find subgroups. I have put an example
here:
http://www.euclideanspace.com/maths/algebra/clifford/algebra/representation/
(I have not posted the code as I don't think there much interest from others
here)

This may not be very practical but I find it helps my understanding if there
is a rich set of links between all these mathematical structures.

Basically this replaces a positive entries in the Clifford multiplication
table by:

1 0
0 1

and a negative entries by:

0 1
1 0

So the group table is twice the number of rows and columns as the Clifford
table. Currently this only works on orthogonal Clifford algebras but If the
Clifford algebra was over complex numbers then I guess I could replace 'i'
with

1 0
0 -1

Anyway I will work though your message in detail now, thanks again,

Martin

### Bertfried Fauser

Mar 13, 2010, 12:33:26 PM3/13/10
Dear Martin,

> Does this also apply to finding the Clifford inverse? (if it exists)

Yes, as fare as I know. CLIFFORD (for maple) computes the Clifford
inverse without
(but I have to check this) using matrix representations. However, if I
remember correctly
CLIFFORD uses the solve command from the linalg package. In general:
* computing inverses is usually costrly
* for geometric applications you do not use inverses in general, but
only those inverses
which emerg from the Cliffrd-Lipschitz group. Those inverses are
computed by the reversion.
Hence for spin transformations (orthogonal transformations) you will
_not_ use general inverses at all.
* A method to compute the inverse would be as follows:
given an element u in CL construct an arbitrary element v in CL and
produce the equation
u*v-Id=0 (right inverse). Since the equation has to be fulfilled
for any basis element and these
are independent, you can transform this into the system of equations
[using [e_I](x) as 'coefficient
of e_I in x, where I is a multiindex] then you get the numerical
system of equations
[ [e_i](u*v-Id)=0 ]
solve for the v_I and then re-substitute the v_i in v, et voila.
Clifford uses such techniques to provide a command clisolve to solve
general (not only linear)
equations in a Clifford algebra.

> Regardless of the answer to this I do like the idea of being able to compute
> the matrix representation if only to check results independently and for
> educational use.

It may be nice ;-) but its lots of work either... quite a bit of
functionality in Clifford is due to establish such results, but you
may face the fact to construct matrices which are matrices over
Clifford elements (making up the right skew field K), hence you need a
matrix algebra over a Clifford (sub) algebra.

I have to look this up ;-))