A Clifford algebra is an algebra with real coefficients times basis elements that are square roots of +1 or-1. The algebra Cl(P,N) is generated by P+N anticommuting generators, P square roots of +1 and N square roots of-1. There are 2P+N basis elements, each one the product of some number of generating elements. The generators must have the property that none of them can be written as a product of the others. Every Clifford algebra has a representation by matrices of a particular type, which depends on P-N, the signature of the algebra (mod 8). These types are:
Signature 8k 8k+1 8k+2 8k+3 Type R 2R R C Bits(B) (P+N)/2 (P+N-1)/2 (P+N)/2 (P+N-1)/2 Signature 8k+4 8k+5 8k+6 8k+7 Type H 2H H C Bits(B) (P+N-2)/2 (P+N-3)/2 (P+N-2)/2 (P+N-1)/2
Where R signifies matrices of real numbers, C matrices of complex numbers, and H matrices of quaternions. 2R is the direct sum R+R of two real matrices, and 2H is the direct sum H+H of two quaternionic matrices. Bits B indicates that there are 2B rows and columns in the nonzero blocks of the matrix.
Since the number of basis elements is a power of 2, the basis elements are representable by a string of P+N bits. It turns out that there is a reasonably simple encoding that translates the bit string into the full matrix. First let us concentrate on the basis elements of R. The basis elements of all others can be easily derived from the ones for R. There are 2B bits in the bit string, B pattern bits and B sign bits, explained below.
Each basis element can be written as the direct product of B basis elements of R(2). There are four basis elements of R(2):
1 0 1 0 0 1 0 -1
T = Z = X = Y =
0 1 0 -1 1 0 1 0
Note: T is the identity matrix, which is usually called I, but I am using T because I is difficult to distinguish from the numeral 1.
T and Z have nonzero elements on the diagonal, which I call pattern 0.
X and Y have nonzero elements on the off-diagonal which is pattern 1.
T and X have both ones positive, which is sign 0.
Z and Y have a -1 in the second column, which is sign 1.
So I assign bits strings to these elements:
T(00), Z(01), X(10), and Y(l 1), putting the pattern bit before the sign bit.
Here is the multiplication table for T, Z, X, Y:
L\R T Z X Y T T Z X Y Z Z T -Y -X X X Y T Z Y Y X -Z -T
Notice that the multiplication is carried out by taking the bitwise XOR of the two bit strings, up to a minus sign, and that the sign is negative if the sign bit of the left multiplier and the pattern bit of the right multiplier are both 1. The ability to carry out multiplication of basis elements using only simple bit operations is what makes the bit string representation so useful.
A quick reminder about the properties of direct products:
(AxBxCx ... ) (DxExFx ... ) = (AD)x(BE)x(CF)x ...
This means that in order to compute the ith pattern and sign bits of the product, we only need to know the ith pattern and sign bits of the elements being multiplied. In fact the bit string of the product (except for a possible minus sign) is the bitwise XOR of the bit strings for the multipliers. Every time we have a sign bit set on the left multiplier and the corresponding pattern bit set on the right multiplier, it introduces another factor of -1. So if we take the bitwise AND of the left sign bits and the right pattern bits, the result will have an even number of bits set if the factor is +1 and an odd number of bits set if the factor is -1.
In symbolic notation:
Let parity(X) = +1 if an even number of bits of X are set, and -I if an odd number of bits of X are set.
Let F be a basis element with B pattern bits PF and B sign bits SF
Let G be a basis element with B pattern bits PG and B sign bits SG.
Let H be the product of F and G with pattern bits PH and sign bits SH and factor m.
FG = mH
PH = PF XOR PG
SH = SF XOR SG
m = parity(SF AND PG)
This easily tells us which basis elements are square roots of +1 and which are square roots of -1. If P AND S has even parity it is a square root of +1 and if odd parity it is a square root of -1. The number of bits set in P AND S is just the number of factors of Y that appear in the direct product.
I prefer to write all the pattern bits to the left of all the sign bits in the bit string representation because it easier on a computer to perform operations on consecutive bits. So the bit representation of an element with 3 pattern bits and 3 sign bits is:
P2 P1 P0 S2 Sl S0
Now, how can we get the 2^B x 2^B matrix representation of a basis element from its bit string?
Note that in a basis element each row and column contains a single nonzero element which is either a +1 or a -1. The pattern bits tell us which elements are nonzero and the sign bits tell us which columns contain a +1 and which columns contain a -1. Suppose we are interested in the element at row I and column J. There are 2B rows and 2B columns, so I and J are B-bit numbers. The rule is this:
the (I,J) element is nonzero if J = I XOR P, and
if it is nonzero, then it is a +1 if J AND S has even parity and a -1 if J AND S has odd parity.
Where did this rule come from?
The easiest way to see this is by recursion, that is, look at the product at each step in the outer product.
First notice that the rule is definitely true for the 2x2 basis matrices of R(2).
Let A be the outer product of the rightmost n factors.
Now if the (I,J) element of A is nonzero and equal to U (which is +1), then:
TxA will have elements (I, J) = U and (I', J") = (2^n + I, 2^n + J) = U.ZxA will have elements (I, J) = U and (I', J") = (2^n + I, 2^n + J) = -U.
XxA will have elements (I', J') = (2^n + I, J) = U and (I", J") = (I, 2^n + J) = U.
YxA will have elements (I', J') = (2^n + I, J) = U and (I", J") = (I, 2^n +J ) = -U.
For T and Z, the new pattern bit is 0, so P' = I' XOR J" = I XOR J = P.
For X and Y,the new pattern bit is l, so P' = I' XOR J' = I" XOR J" = 2^n + I XOR J = 2^n + P.
So the relationship I XOR J = P is maintained as we add factors to the direct product.
For T and X, the new sign bit is 0, so J' AND S = J" AND S = J AND S.
So J' AND S and J" AND S have the same parity as J AND S.
For Z and Y, the new sign bit is 1, so J' AND S' = J AND S, but J" AND S' = 2^n + (J AND S).
So J" AND S has opposite parity to J' AND S and J AND S, introducing a minus sign on U in the right hand column.
Now, how about the other four types of matrices?
For 2R, there is an extra outer product with T or Z, so I add one bit on the left, a 0 for T and a 1 for Z.For C, there is an extra multiplication by either 1 or i. If multiplied by 1, append a 0 bit on the left of the bit string, if multiplied by i, append a 1.
For H, there is an extra multiplication by either 1, i, j, or k. Append two bits on the left of the bit string 1 (00), i(01), j(10), or k(11).
For 2H, append three bits to the bit string, the leftmost two for 1, i, j, k, and the other for outer product with T or Z.
Note that in all cases, multiplication is still accomplished by an XOR of the bit strings. However the rule for determining the sign must be changed slightly to reflect the facts that: ii=jj=kk=-l, ji=-k, ik=j, kj=-i. There is no simple bit operation that does this, so just check for these cases explicitly in C, H, and 2H.
Given a set of P+N generators and a basis element A, all represented as bit strings, how do you determine which generators must be multiplied together to give A? Suppose you knew the combination of generators that had to be multiplied together to get the basis element whose bit representation consisted of a single set bit in the ith position for each bit position i. Create a string of bits Vj for each i such that the jth bit of Vj is set if the jth generator is part of the product which yields the bit string with only the ith bit set. Because multiplication of basis elements is just an XOR operation except for a possible minus sign, you would just XOR the Vj together for each bit i that was set in A. (As always, bits and generators are numbered starting at 0, and bit 0 of a bit string is on the right.)
Here is an example from Cl(2,2) = R(4), which may make things a bit clearer:
G0 = (0001) G0^2 = +1 G1 = (0100) G1^2 = +1 G2 = (0111) G2^2 = -1 G3 = (1101) G3^2 = -1 Basis(0001) = G0 => V0 = (O001) Basis(0010) = G0 G1 G2 => V1 = (0111) Basis(0100) = G2 => V2 = (0010) Basis(1000) = G0 G1 G3 => V3 = (1011)
The set of Vs are what I call the inverse generators of the algebra. Suppose we want to know the breakdown of Basis(1011) as a product of generators.
Bits 0, 1, and 3 are set, so XOR together
V0 XOR V1 XOR V3 = (0001) XOR (0111) XOR (1011) = (1101).
This implies that Basis(1011) = +/- G0 G2 G3
Now what about the plus or minus sign?
The answer is, of course, it depends on the order in which you decide to multiply the generators.
Ascending indices left to right?
The reverse?
Or some other scheme altogether?
The easiest way to deal with this is just to multiply the generators you get in the order you choose and see which sign is appropriate. Since this only involves a few bitwise ANDs and parity counts, it is pretty quick to compute. Below I use a colon to separate the pattern bits from the sign bits for clarity (P:S). I am only showing the computation of the sign since we already know what the product is.
In this case, G0 G2 G3 = (00 : 01) (01 : 11) (11 : 01) = parity(01 AND 01) x parity(11 AND 11) =
= parity(01) x parity(11) = -1 x 1 = -1, so the sign is negative: Basis(1011) = - G0 G2 G3
This leaves the problem of how to determine the Vs given a set of generators. This is exactly a matrix inverse problem where multiplication is replaced by AND and addition is replaced by XOR. Using any standard matrix inversion routine with this replacement works fine.
Lastly, suppose you are faced with a basis element in the form of a 2BX2B matrix.
How do you determine the bit string that goes with this matrix?
Basically we invert the rules for constructing a matrix from a bit string.
First, the nonzero element in column 0 is always +1 for a basis element. If your matrix has a -1 in this column it is the negative of a basis element. If this is the case, remember this sign and multiply the entire matrix by -1. The nonzero elements of the matrix will fall where I XOR J = P. Specifically, if you look in the first row (I=0), then P = J (the column number). Remember that column 0 is the first column on the left, and row 0 is the top row.
Now look at the sign of the nonzero element in columns 1, 2, 4, 8, ... , 2^(B-1).
If the nonzero element in column 2k is negative then bit k of S is set.
If the matrix is of the form 2R or 2H, then
if the lower half is the same as the upper half, append a 0 bit to the left of the pattern bits.If the lower half is the negative of the upper half, append a 1.
For C, if the nonzero elements are +/- 1, append a 0 on the left. If the nonzero elements are +/- i, append a 1.
For H and 2H, if the nonzero elements are +/- 1, +/- i , +/- j, or +/- k, append the bits (00), (01), (10), (11), respectively, to the left of the others.
As an example, let us take a basis element from Cl(6, 1 ) = 2H(4) and determine its bit string (B=2).
0 0 k 0 0 0 0 0 0 0 0 -k 0 0 0 0 k 0 0 0 0 0 0 0 0 -k 0 0 0 0 0 0 0 0 0 0 0 0 k 0 0 0 0 0 0 0 0 -k 0 0 0 0 k 0 0 0 0 0 0 0 0 -k 0 0
First, the nonzero element in the top row occurs in column 2, so P=(10). Considering only the upper left 4x4 block because we are in 2H, column 1 has a negative element and column 2 has a positive element. Therefore the sign bits are S=(01). So far we have a bit string of (1001). The upper left block is equal to the lower right block, so append a 0 on the left. The bit string is now (01001). The nonzero elements are +/- k, so now append (11) on the left. The final bit string for this basis element is (1101001) which has 7 bits because P+N = 6+1 = 7.
While there is a general rule for creating generators for some signatures, I found the generators for P<8, N<8 by brute force.
Combined with a set of generators for Cl(8,0) and Cl(0,8), this is aufficient to create generators for any P and N.
Here is a set of generators and inverse generators for Cl(8,0).
These generators all anticommute with the pseudoscalar
which has bit string (11111111). Note that (p+)^2 = +1.
G0+ (0000 0001) V0+ (00000001) G1+ (0001 0000) V1+ (10101011) G2+ (0011 1011) V2+ (01100111) G3+ (0101 0111) V3+ (00011111) G4+ (0111 0101) V4+ (00000010) G5+ (1001 1101) V5+ (10110011) G6+ (1011 0011) V6+ (11000111) G7+ (1101 1001) V7+ (01011011)
Here is a set of generators and inverse generators for Cl(0,8).
These generators all anticommute with the pseudoscalar
which has bit string (11111111).
G0- (0001 0011) V0- (00101010) G1- (0010 0110) V1- (00011001) G2- (0011 0001) V2- (00000111) G3- (0100 0101) V3- (01111111) G4- (0101 0100) V4- (00110010) G5- (0110 0010) V5- (00011100) G6- (0111 1111) V6- (00100101) G7- (1111 0111) V7- (10111111)
Notation: 0(B) is a bit string with B zeroes, likewise 1(4) = (1111), etc. Mi, Pi, Si are the modifier, pattern, and sign bits of the generators of Cl(P,N): Gi = (Mi : Pi : Si). If bit strings are written next to each other, concatenate the strings, e.g., 1(4) 0(3) = (1111OOO). If the generators of Cl(P,N) are Gi (i = 0, 1, ... , P+N-1) then the generators of Cl(P+8,N) are: Gi+ x 1 (O < i < 8) bit string ( 0(P+N-2B) : Pi+ O(B) : Si+ O(B) ) and p+ x Gj (O < j < P+N) bit string ( Mi : 1(4) Pj: 1(4) Sj ) and the generators of Cl(P,N+8) are: Gi- x 1 (O < i < 8) bit string ( 0(P+N-2B) : Pi- O(B) : Si- O(B) ) and p- x Gj (O < j < P+N) bit string ( Mi : 1(4) Pj : 1(4) Sj ) It is easy to verify that all the generators in these sets anticommute. Michael Gibbs demonstrates that they span the basis by explicitly constructing the inverse generators. Let the inverse generators of Cl(P,N) be Vj . The inverse generators of Cl(P+8,N) are: Inverse generators j = 0, ... ,B-1 are: Wj = Vj O(8) if parity(Vj) = +1 and Wj = Vj 1(8) if parity(Vj) = -1 Inverse generators j = B, ... ,B+3 are: Wj = 0(P+N) V(j-B)+ Inverse generators j = B+4, ... ,2B+3 are: Wj = V(j-4) 0(8) if parity(Vj) = +1 and Wj = V(j-4) 1(8) if parity(Vj) = -1 Inverse generators j = 2B+8, ... ,P+N-1 are: Wj = V(j-8) O(8) if parity(Vj) = +1 and Wj = V(j-8) 1(8) if parity(Vj) = -1 Inverse generators j=2B+4, ... ,2B+7 are: Wj = 0(P+N) V(j-2B)+ The inverse generators of Cl(P,N+8) are the same expressions, replacing the + superscripts on the Vs with - superscripts. If P or N is greater than 7, this procedure can be iterated as many times as necessary to create a set of generators and inverse generators.
......