For sometime in the last semester I had an interesting problem to work on. One approach that we expected would help us solve the larger problem was to search for XOR ordered matrices that were unitary. (A unitary matrix is one whose complex conjugate is also its inverse).

A xor ordered matrix is simply one that could be generated by the following code snippet:

syms = %w(a b c d e f g h i j k l m n o p q r s t)

v = 8

v.times{|m|

      v.times{|n|

            printf("%s ", syms[n^m])

      }

      puts ""

}

Here are 2x2, 4x4, 8x8 and 16x16 XOR matrices (obtained by changing the value of v) -

a b

b a

a b c d

b a d c

c d a b

d c b a

a b c d e f g h

b a d c f e h g

c d a b g h e f

d c b a h g f e

e f g h a b c d

f e h g b a d c

g h e f c d a b

h g f e d c b a

a b c d e f g h i j k l m n o p

b a d c f e h g j i l k n m p o

c d a b g h e f k l i j o p m n

d c b a h g f e l k j i p o n m

e f g h a b c d m n o p i j k l

f e h g b a d c n m p o j i l k

g h e f c d a b o p m n k l i j

h g f e d c b a p o n m l k j i

i j k l m n o p a b c d e f g h

j i l k n m p o b a d c f e h g

k l i j o p m n c d a b g h e f

l k j i p o n m d c b a h g f e

m n o p i j k l e f g h a b c d

n m p o j i l k f e h g b a d c

o p m n k l i j g h e f c d a b

p o n m l k j i h g f e d c b a

The challenge was to find some assignment of +ve and –ve signs to each row of the matrix such that the resultant matrices would be unitary, irrespective of what values a, b,c etc were.

This general pursuit took up several days of my life and spilled over into other people’s life as well. It was also fun to be working with Prof Amr Sabry on some aspects of this problem. Those days it seemed that finding a good solution to the problem was well worth the time spent on it.

While the solution to the 2x2 problem was obvious, one for the 4x4 case seemed really hard. After several iterations the first solution that I knew of was pulled out of the air by Prof Sabry in a most mysterious fashion.

Later that day evening I could generate all possible 4x4 solutions and all possible 8x8 solutions, with lots of help from my colleague Michael Adams. We figured out a handy little property that helped us brute force it.

Here are the solutions for the 2x2, 4x4 and 8x8 matrices.

++

-+

++++

-+-+

-++-

--++

++++++++

-+-+-+-+

-++--++-

--++++--

-++-+--+

----++++

-+-++-+-

--++--++

However for a while I could not find a 16x16 solution. I believed initially that my program was buggy. And so I looked for other ways of expressing the problem. For the 2x2 case there were exactly two possible assignment of +ve and negative signs that would yield unitary matrices. For the 4x4 case there were 16 solutions. For the 8x8 case there were 2048 solutions. For the 16x16 case, there seemed to be none!

As an example, here is another 4x4 solution:

++++

-+-+

+--+

++--

I eventually expressed the problem in the MIniKanren logic system and in the FooGroup algebra which I created for this purpose. Once I chanced upon the FooGroup approach, I could explain the number of solutions as being the number of independent variables in the FooGroup expression for the matrix.  In the case of the 2x2 matrix there was one independent variable, in the case of 4x4 there were 4 independent variables and in the case of the 8x8 there were 11 independent variables.

The fact that the MiniKanren logic system also failed to show any valid solutions to the problems, caused us to stop searching for 16x16 unitary XOR matrices. Though it seemed that no such matrix existed, I could not see why that was so. Finally XOR matrices were dropped and the searched continued in other directions.

-- 

Today I was looking at Quaternions (because the final solution to the problem seemed to look a lot like a quaternion) when I chanced upon the Euler’s Four Square Identity.

I was stumped. Here was the 4x4 XOR matrix solution. To see more clearly what I mean, look at the indices of the ‘b’ values – you will find them to be in xor order. Further look at the signs assigned to these, this exactly the transpose of the sign matrix above. In other words the Euler Four Square identity expressed the adjoint of the 4x4 unitary XOR matrix.

What struck me immediately is that 2x2 case is merely the normal trigonometric square rule for 2 dimensional geometry. More importantly what struck me was that I had enough material for a Eight Square identity.

Before I go into that, a bit about what the Four Square identity means. The four square identity actually applies to a class of numbers called quaternions and in a hand wavy way you can think of them as the next level after complex numbers. A quaternion ‘x’ can be written as

x = a + bi + cj + dk

where a is a real component and i, j and k imaginary components. The conjugate of a quaternion is defined as 

x’ = a - bi - cj - dk

We know what the norm of a complex value is – it is sometimes know as its absolute value – and is often times calculated by applying the Pythagorean relation to the real and imaginary parts. The norm of the product of two complex numbers is equal to the product of the norms of each of those numbers. We all know this courtesy of his school geometry/number theory.

The Euler Four Square identity is the same principle as applied to quaternions. The norm of the product of two quaternions is equal to the product of the norms of each of them. This is exactly what Euler’s Identity expressed. (The norm of quaternion x is x.x’).

That said, the 8x8 unitary XOR matrix implied that I had a Eight Square Identity. It also meant that I had an 8 dimensional number system which supported multiplication of norms similar to complex numbers and quaternions. This was a thrilling realization so I decided to look it up.

I did search and I found octonions and Degen’s Eight Square Identity. It seemed like I had chanced up on something, but was beaten to it by about 162 years by John T Graves who found octonions in 1843. Degen’s Indentity is strangely the conjugate transpose of the 8x8 matrix above.

This brings me to the final piece of the puzzle as of now. If there is a 16x16 matrix, there should be a 16-dimensional algebra/geometry that satisfies the multiplication of norms. I found an interesting mention in math world that there exists apparently a proof by Clayley that no higher systems exist.

As of now the known set of normed division algebras are the real numbers, the complex numbers, the quaternions and the octonions.

More on octonions here. http://math.ucr.edu/home/baez/octonions/node1.html

The last I know is that there exists a 16-dimensional number system called octonions. True to my suspicions the 16 dimensional system, called Sedenions are not a composition algebra (or in other words they don’t respect the multiplication of norms in the same way 8 and lower dimensional systems do). Sedenions have been recently studied. Some material is available here: http://www.geocities.com/zerodivisor/sbasicalgebra.html

And here: http://en.wikipedia.org/wiki/Sedenion

While I have intuitions about how many of the open ended ideas here are related, I think there is quiet a lot of reading I have to do before I can see all the relationships here.