I almost made a (potentially) very expensive mistake today. I have been hoping to buy a digital SLR for a while now and in the past few weeks that seems to be the only thing that on my mind. Most people around me are a little wary getting into a conversation with me these days because the only thing I could talk about was the camera I was hoping to buy.

 

After a lot of ruminations between going Canon or Nikon I finally decided to go with the Canon EOS 350d a.k.a. the Canon Digital Rebel XT. Now I cant really afford this stuff, and it a rather tight stretch to get myself one of these considering my present status of un-rich grad student.

 

I am also no novice to using the web and to using computers, so I was so stumped by how I forgot the cardinal rule of doing anything on the web – never believe a webpage. Unless you know the entities behind the webpage and you trust their reputation to serve your purpose – never ever ever trust a webpage.

 

Case in point, this is what you see when you Google for the Digital Rebel XT:

 

I took a walk down to the nearest camera shop and I mentioned to the friendly gentleman there about how the website prices are about 450$ when he is charging me about 800$. Here came the first piece of news – he says that if you have a Canon USA warranty, in other words if something happens and you want Canon to fix it for you, then there is no way that the camera can cost so less. It must be some international warranty which you may have to ship back to the country of origin.

 

So I take a look at the website again and the website says that it has a USA warranty – very explicitly. So I feel considerably relieved. I however wanted to check out one or two of the lenses I was interested in getting and so I visited the shop again and I mentioned this fact to the person there. He stuck by what he said – he said that yes they might offer a warranty to you in the US, but it will not be Canon’s warranty. It will be someone else’s.

 

What? Now I was going to spend what is presently a non trivial amount of money for me so I put things together and I decided to call the online store I was planning to buy from.

 

I was feeling a little pressurized into getting this purchase done because Canon is offering some interesting mail in rebates which multiply when you get multiple items in combination and so I was planning to through in a decent lens with image stabilization and such.

 

So I call the store and I had to hold onto the line for a whole 20+ mins. Hmm hmm… what are these guys an airline booking service? And finally I get a most disinterested sounding guy. I ask about the warranty and yes, the shopkeeper I had been talking to was right. This was not a Canon warranty. ‘If something happens, who will be fixing the camera?’ ‘My technicians will work on it’ and that gets me thinking – gee, if I have to hold so long to just speak to one of them how hard will it be for me to get them to fix something for free? And then he says it – ‘my technicians have been fixing these for the last 50 years’. What??? And then a sentence or two later he hangs up while I was in mid sentence. Nice.

 

So the whole conversation was a little like being hit buy a snowball when you are busy picking your nose. I kind of snapped out of my self hypnotized state of mind and I did what I should have done first – search for reviews on the seller.

 

Every website I could find had people expressing very strong negative opinions about these guys. I search for some of the other sellers offering similar prices – they all had similar comments. What???

 

I remember the shopkeeper I was talking to mention that they cant be authorized Canon dealers because there is no way that they could get the cameras so much cheaper from Canon.

 

So finally, let me point some fingers –

This is the seller I was looking at and the one that I called up –

http://www.infinitiphoto.com/

(Yes they have a reasonably nice looking webpage).

 

Here are some others -

http://www.bestpricecameras.com

http://www.geniuscameras.com

http://www.usaphotonation.com/

 

Here are some seller review pages –

http://www.reviewcentre.com/reviews87615.html

http://forums.photographyreview.com/showthread.php?t=10678

http://www.dcresource.com/forums/archive/index.php/t-7031.html

http://www.dcresource.com/forums/archive/index.php/t-72.html

http://www.price.com/vendor_review_display.html?vid=-2147483120

http://forums.photographyreview.com/showthread.php?t=10918

and so on, there are many pages out there that tell similar stories.

 

Well this was a clincher –

http://www.resellerratings.com/seller9662.html

 

Moral of the story – make sure that you search for the seller when buying online always. If in doubt call them up, maybe even multiple times. This is a handy website that gives you seller information –

http://www.resellerratings.com/

More practically, simply search the web for “review <seller name>”.

 

Ensure that you are not going for opinion bases of 5 or 6 reviews. Averaging over 100s of reviews is decent. Another thing that you could do, is use resellerratings.com or similar to search for the product to see which sellers give you a good price.

 

And before I change the topic, some good information. I have heard good opinions by word of mouth and in terms of reviews about B&H. They are on the average a little higher in cost than the cheapest semi-reputable seller you can find.

http://www.bhphotovideo.com/

I have heard good things about Adorama.com as well.

 

If you are looking for Canon EOS lenses to buy, take a look at this link (thank you Deepak for pointing at this). This is a good starting point for a beginner in digital SLR photography and is a beginners guide to lenses for the Canon EOS series –

http://bobatkins.com/photography/digital/10d300dlenses.html

 

 

Finally, now that I have broken free of my obsession (for a while) I was trying to think of why I got so convinced into buying this, without doubting the seller and other things. The last time I bought a camera online I was very careful. I have two ideas in this regard and they are a little touchy, but here they are –

 

What changed since the last time I bought my Sony P150 that caused me not to scrutinize the seller as much? One answer – Google. See people form an emotional bond with their search engine – it is their bringer of information, of right information, of truth. It is not an intellectual bond, it is bond formed out of the force of habit. So when something shows up ‘on top’ on google – I think that that information is credible (for some values of credible). If any of the shoddy sellers above were ranked first or second on Google, that would be true. But, they were sponsored links and they were right on top on Google.

 

When a link is on top by paying for it, of course its not credible. Of course, Google never does vouch for the credibility of the people who it sells ad space to as well. While all of that is correct, the point is that being on top on Google is a powerful selling force. It can slip past the best of us. The same goes for Google’s Froogle – I don’t think any form of paid advertising is involved there though.

 

Can Google do something about this? Should they check credibility of the ads they host – I don’t think they can if they want to sell ads in bulk the way they do now. I think this is hard for anyone on top – be it Google or MSN or anyone else. But if they don’t, there will be more like me who trust Google ranking and information finding abilities to magically lend credibility to their sponsored links.

 

However, here is an opinion – if you plan to be a popular website on which resellers can rely on to sell their goods, then you need to have a credibility system in place. Something like Amazon’s seller feedback and buyer assurance. How much do you think I am going to value sponsored links on Google in the future? Maybe on the whole, advertising on websites would take a big boost, if there was a credibility system.

 

 

The second point I wanted to make is one that is best described using Ken Thompson’s ‘Trusting Trust’. How can you trust or mistrust one website based on another? What if the review site you are looking at is faking it? What if someone is trying to make one of the above sites look bad by posting fake reviews? Or is someone trying to make their own site look good?

 

There is, in my understanding, no way out of this. One almost always ends up implicitly or explicitly trusting one system to make a judgment about another, like KT demonstrated in his Turing award lecture.

http://www.acm.org/classics/sep95/

 

The only thing you can do is mitigate the possibility of being cheated is by looking at several review sites and by calling up your potential sellers. I can’t think of very much else.

 

 

Finally, if you are from one of the sort sellers this is what I have to say - get smarter. If I were you and I still wanted to defraud an occasional gullible customer, I would minimally do the following –

- Have more fake reviews in my support

- Sound more endearing on the phone

(despite the bad reviews, a good phone conversation and the price would have got me). You see going on top on google gives you a much larger window of opportunity to get at customers than you realize. Think a little bit – there are many many things you can do. Of course, you will eventually get caught or get sued – but I am assuming you are willing to entail that risk considering some of the reviews I read.

 

As of now I am not buying my Rebel XT, it a little outside of my budget. But I guess the prices will come down and my budget will go up, in time.

I had been to Chicago the last week of 2005. This visit, being my first trip outside of Bloomington to see the ‘the real US’ as some people tell me. Considering that I had pretty much flown into Indianapolis in the middle of the night and that I had stayed at Bloomington all semester I pretty much had not seen any more of the US than most Indians had in the movies.

 

One of the many reasons that I was looking forward to seeing Chicago was that I was looking forward to seeing some of what was considered ‘big’ in American terms. I don’t know if this is easy to understand, but back in India what most people who visit US for the first time tell me is that the thing they notice most is how much larger everything is. Larger stores, larger roads, larger people, larger potatoes etc etc

 

Well Bloomington, didn’t spook me out in that way – it was all too beautiful to be scary. Bloomington seems like it has sprung straight out of an Enid Blyton novel, for those of us who grew up reading Enid Blyton novels (no I didn’t, I just happened to make certain observations about those who did. So there.).

 

Chicago was well, uummhh… large. I was kind of spooky to be surrounded by all there large buildings and one was walking along the streets staring up at a partitioned sky. I also remember noticing how on the average people looked more harangued than folk back at Bloomington. And also how everything was so much more hurried. People seemed also seemed more necessitated to fend for themselves instead of the ‘you first, no you first’ courtesy of Bloomington. I also remember thinking that with buildings like that the only thing that the place lacks is Godzilla to go tearing between – just to complete the picture. Many things were more expensive, or at least it was considerably easier to find yourself more expensive things that it was in Bloomington where most college students would not have much use of finding themselves lots of expensive things. There were also many poor people on the streets, many holding up signs that said something like “I am just Hungry”.

 

But anyway, that’s not what this post is about. This post is about the St Pauli Girl. Chicago can wait, I didn’t know I’d have much to say about it.

 

Of all the pictures I took in Chicago, the one that seemed to catch my attention the most is this random picture I took of a neon sign in a shop window. The St Pauli Girl:

 

 

I don’t know what it is, but that picture held a certain inexplicable appeal. It even stayed my wallpaper for sometime. See, I am not much of beer person, then why? I do have googd friends who really like beer, but not me. Not yet.

 

I finally decided to google for it and sure enough, I found my explanation. Now for the benefit of my below 18 readers who are trying to understand the true nature of all of computer science from reading my blog, I shall not quote these here, instead I shall provide the links here.

 

Scroll down and read the section titled Don't Fear the Reaper

http://www.purpleroom.com/travel/kenn6.htm

 

and

http://beer.emptyfree.com/index.php?p=7

 

Cheers! Hic!

 

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.

It always used to bother me, how mind-bogglingly complex my life was, from a lot of aspects. Sometimes, the complexity was too much to handle and it would affect the way I think and act in totally unconnected aspects of my life. Its strange how no one knew or could know all the pieces at once.

 

I have always found movie characters shallow – they are always clichéd in some way – never seemed to reflect the complexity of real life in any non trivial way. Very rarely could I allow myself to see the connection between movie characters and the way I see the ‘real’ world.

 

I just finished watching Stanley Kubrick’s ‘Eyes Wide Shut’ and I have to pretty much surrender to the genius of this film. Its something that captured an aspect of the complexity of life, in a very real way. I don’t have a word or a phrase to describe that part of life – but it is real for me. And it scared me that someone could express it as clearly as that. Scared and amazed me. It’s a wonderful movie and one that is very hard to appreciate in all its layers.

 

I am beginning to realize that I have developed in myself a healthy though-style in the constructive culture of doubt that we often call science. I can think scientifically – though saying that does not mean very much because there many interpretations of what ‘thinking scientifically’ is. However I cannot think very clearly in terms of people - the way behavior of individuals is affected by interaction with other individuals even though I can presume to understand the individuals in isolation. It always amazes me when someone can do that or at least portray that in a way that I that I find interesting.

 

 

The Christmas break has started and Bloomington is beautiful these days. Snow all around – my first time with snow. I guess saying that Bloomington is beautiful these days is not saying much at all because Bloomington is always beautiful.

 

 

 

I got my copy of Douglas Hofstadter’s ‘Godel Escher Bach’ the other day. I think it is going to say many things that I know intuitively but may never be able to express as beautifully as Hofstadter. And that, in some sense, is the whole point.

 

 

I have also got interested in physics again after many many years. I don’t know if I will have the luxury to study it – but the interest is back. This time however it looks like I may focus more rationally and more thoroughly on quantum mechanics and the quantum field theory.

 

 

I am also beginning to be of the opinion that computer science is a foundational science in the study of the universe as is mathematics and physics. Actually computer science is probably an incorrect description of this foundational science and it should be more of a science of automata – such that it can be described separately from mathematics, though the line is blurry in many places. Its doesn’t really matter – there seems to be little value in the effort of compartmentalizing computer science and mathematics.

 

 

I have also, in the past few days, got interested in this board game called GO. It has simpler rules that chess. However it leads to very complex patterns and different notions of strategy compared to chess or many other board games that I know of.

http://en.wikipedia.org/wiki/Go_board_game 

 

And finally I have an update to my Enc (file encryption program). The last version was buggy because it would drop files sometimes. For some reason I cant seem to write this program well at all. I always end up writing this one badly and keep getting unhappy with it. Even this version isn’t very good. It certainly isn’t good in terms of doing good exception handling and all – but even on other aesthetic levels I don’t like it. I wonder what it is about the nature of this program that causes that. Of course, if you are afraid of using it for protection – it is rather usable, so don’t worry, too much. The protected files that are generated are atleast as strong or weak as the protection that is guaranteed for 128bit Rijndael (AES) encryption.

Download Enc v0.3 (src and binary)

 

 

Marvin: "I am at a rough estimate thirty billion times more intelligent than you. Let me give you an example. Think of a number, any number."

Zem: "Er, five."

Marvin: "Wrong. You see?"

The mattress was much impressed by this and realised that it was in the presence of a not unremarkable mind.

-- Douglas Adams, Life, the Universe and Everything

 

LIFF (n.)

A book, the contents of which are totally belied by its cover. For instance, any book the dust jacket of which bears the words. 'This book will change your life'.

 

FooGroup Algebra is a little ‘algebra’ that I created while trying to solve a problem. It seemed sufficiently interesting to describe by itself. I would have liked to call it group algebra, but it seemd like the name would already have been taken, and it also seemed like that’s too nice a name to dedicate to something like this :)

 

FooGroup Algebra

 

A term in this algebra consists of one or more symbols enclosed in [] or (). An expression is a set of terms. The enclosing [] or () are called the type of the term. The symbols the enclose are called base of the term. The ordering of symbols inside a term is of no significance. The ordering of terms in an expression is of no significance.

 

Here are some expressions:

(a b c)[c d]

(a b)(c d)(a d)

 

An expression is said to be solved, if all the terms in the expression have only one symbol. The following is a solved expression:

(a)[b](c)(d)

The value of each symbol is the type of the term that it is held.

 

An expression is invalid or is a contradiction is there atleast two terms of different type but same base. The following expressions are contradictions:

(a b)[a b]

(a)(b c d)[a]

 

Term Reduction and Solving: One can solve and expression by reducing each term in the expression until every terms contains only one symbol. Terms can be reduced as follows –

(X Y) => (X)[Y] and [X](Y)

[X Y] => [X][Y] and (X)(Y)

Where X and Y are any set of terms.

 

Since a term can be reduced in two ways, there maybe more that one solution for a given expression. A valid solution cannot have a contradiction. Here are some example reductions –

(a b c)[c d]

(a)[b c][c d]

(a)(b)(c)(d)

 

This is another solution for the same –

(a b c)[c d]

(a)[b c][c d]

(a)[b][c][d]

 

This is another solution for the same –

(a b c)[c d]

[a](b c)[c d]

[a](b)[c][d]

 

This is another solution for the same –

(a b c)[c d]

[a](b c)[c d]

[a](b)[c][d]

Independent Variables: When reducing a term we select one variable and assign it both type values. The values of other symbols/variables might be get fixed as a consequence of this. Such variables are referred to as independent variables. In the general case, the maximum number of solutions than an expression can generate is 2^n where n is the number of independent variables. Since one or both choices of type assignment may result in a contradiction the number of actual solutions maybe lesser than this.

 

In the above example, there were two independent variables a and b. c and d values were fixed by the selection of values for a and b. Hence there were 4 solutions.

 

Ex:

(a b)(b c)(c a)

(a)[b](c)[a] <-- contradiction

[a](b)[c](a) <-- contradiction

This expression has no solutions.

 

(a b)(a c)(a d)[b c d]

(a)[b][c][d] <-- this is one solution

[a](b)(c)(d) <-- this is a contradiction.

The above expression has only one solution

 

End.

 

That’s it. That’s all I know about this thing. I would like to create a method to predict how many solutions an expression may have. I don’t know how to do that.

 

I also would like to explore extensions to the algebra in terms of adding more types to the algebra.

 

Adding More Types: Right now I have only two types () and []. One can think of the relation between these as that of the relation between –ve and +ve, or as odd and even.

 

()() = [] or odd odd = even or - - = +

()[] = () or odd even = odd or - + = -

 

One can consider adding three types (), [] and {} such that

() = []{} and {}[]

[] = (){} and {}()

{} = []() and ()[]

I don’t know what sorts of types map to.

 

One can consider +, -, +i and –i as four types as well and so on.

 

What is this useful for?

I was working on solving another problem and the search space for that was too large. I was looking for a way of reducing the search space and for compactly representing this search operation when I realized that I could express the problem like this.

 

The original problem was that I had a matrix like the one below. I could assign and + or negative sign to any variable such that the matrix when multiplied by its transpose would generate the identity matrix. (The transpose of a matrix is the matrix you get when you flip it along its diagonal).

a b c d

b a d c

c d a b

d c b a

 

Then I had to solve the problem for the larger 8x8 version of the same matrix –

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

 

These matrices are generated as a consequence of simple XOR order, that can be easily expressed by the following ruby program –

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 ""

}

 

The fact is that I had to solve the problem for matrices of any dimension that is a power of two and I couldn’t see any pattern that would help me automagically generate the signs for matrices of higher dimensions.

 

So I though about how to search the space of all possible sign assignment and then realised that I can group elements into groups of four such that each group would have 4 variables and would be of type (). As an example here is the expression in FooGroup algebra which when solved would give all the solutions possible.

(r1c0,r1c1,r0c0,r0c1)(r1c2,r1c3,r0c2,r0c3)(r2c0,r2c2,r0c0,r0c2)(r2c1,r2c3,r0c1,r0c3)(r2c0,r2c3,r1c0,r1c3)(r2c1,r2c2,r1c1,r1c2)(r3c0,r3c3,r0c0,r0c3)(r3c1,r3c2,r0c1,r0c2)(r3c0,r3c2,r1c0,r1c2)(r3c1,r3c3,r1c1,r1c3)(r3c0,r3c1,r2c0,r2c1)(r3c2,r3c3,r2c2,r2c3)

Where r0c1 is the symbol for the sign that should be given to element at row 0 column 1. (I further go on to fix my first row to be all positive numbers. )

 

Finally, if you are interested I have a .Net library to solve expressions in the algebra. I also have a ruby program that generates C# programs which get the library to solve the above matrix problem.  The build command takes as parameter the dimensions of the matrix that you wish to solve (this should be a power of 2).

Download FooGroup Algebra and the Matrix Solver

 

Running the solver on a 4x4 matrix generates 16 solutions. 2048 solutions for a 8x8 matrix.

Solving :(r1c0 r1c1)(r1c2 r1c3)(r2c0 r2c2)(r2c1 r2c3)(r1c0 r1c3 r2c0 r2c3)(r1c1 r1c2 r2c1 r2c2)(r3c0 r3c3)(r3c1 r3c2)(r1c0 r1c2 r3c0 r3c2)(r1c1 r1c3 r3c1 r3c3)(r2c0 r2c1 r3c0 r3c1)(r2c2 r2c3 r3c2 r3c3)

Solution 1 : (r1c1)(r1c3)(r2c2)(r2c1)[r2c3](r2c1)(r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0][r1c2][r2c0][r3c0]

Solution 2 : (r1c1)(r1c3)(r2c2)(r2c1)[r2c3](r2c1)[r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0][r1c2][r2c0](r3c0)

Solution 3 : (r1c1)(r1c3)[r2c2][r2c1](r2c3)[r2c1](r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0][r1c2](r2c0)[r3c0]

Solution 4 : (r1c1)(r1c3)[r2c2][r2c1](r2c3)[r2c1][r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0][r1c2](r2c0)(r3c0)

Solution 5 : (r1c1)[r1c3](r2c2)[r2c1](r2c3)[r2c1](r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0](r1c2)[r2c0][r3c0]

Solution 6 : (r1c1)[r1c3](r2c2)[r2c1](r2c3)[r2c1][r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0](r1c2)[r2c0](r3c0)

Solution 7 : (r1c1)[r1c3][r2c2](r2c1)[r2c3](r2c1)(r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2][r1c0](r1c2)(r2c0)[r3c0]

Solution 8 : (r1c1)[r1c3][r2c2](r2c1)[r2c3](r2c1)[r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)[r1c0](r1c2)(r2c0)(r3c0)

Solution 9 : [r1c1](r1c3)(r2c2)[r2c1](r2c3)[r2c1](r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)[r1c2][r2c0][r3c0]

Solution 10 : [r1c1](r1c3)(r2c2)[r2c1](r2c3)[r2c1][r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)[r1c2][r2c0](r3c0)

Solution 11 : [r1c1](r1c3)[r2c2](r2c1)[r2c3](r2c1)(r3c3)(r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)[r1c2](r2c0)[r3c0]

Solution 12 : [r1c1](r1c3)[r2c2](r2c1)[r2c3](r2c1)[r3c3][r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)[r1c2](r2c0)(r3c0)

Solution 13 : [r1c1][r1c3](r2c2)(r2c1)[r2c3](r2c1)(r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)(r1c2)[r2c0][r3c0]

Solution 14 : [r1c1][r1c3](r2c2)(r2c1)[r2c3](r2c1)[r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)(r1c2)[r2c0](r3c0)

Solution 15 : [r1c1][r1c3][r2c2][r2c1](r2c3)[r2c1](r3c3)[r3c1](r3c2)[r3c1][r3c1](r3c2)(r1c0)(r1c2)(r2c0)[r3c0]

Solution 16 : [r1c1][r1c3][r2c2][r2c1](r2c3)[r2c1][r3c3](r3c1)[r3c2](r3c1)(r3c1)[r3c2](r1c0)(r1c2)(r2c0)(r3c0)

 

 

First principles, Roshan. Read Marcus Aurelius. Of each particular thing ask this: what is it in itself? What is its nature? What does it do, this matrix you seek?

 

A faceless Marcus Aurelius with the voice of Anthony Hopkins and the intensity of Hannibal Lector kept repeating this to me most of this week.

 

Last Sunday night something interesting happened – I believed I had a solution to something – a problem in quantum computing - a way by which I can take any arbitrary quantum function that takes ‘m’ bits and produces a superposition of ‘n’ bits and construct an equivalent reversible function. The interesting thing that happened was that I realized was wrong – when I started looking at the matrices that my solution generated, I realized it would not work for any function that produced more than one output bit.

 

After some amount of thinking about it, the problem was narrowed down to looking for a matrix that was involuntary, the first row of which was decided by the function I was trying to model. Though the problem could be stated in a simple way, it was surprisingly hard to solve.

 

It kept running in my head everyday, all the time, for a major part of this week and it just didn’t make sense. I could look at the problem from many angles but the matrix kept eluding me. What is the nature of this matrix? it is involuntary. But that did not help me solve the problem.

 

The idea that finally helped me solve it came from a friend, Abhijit Mahabal, one of the smartest people I know in the department. Abhijit got me to look at the involution represented by a matrix as the reflection of a point about an ‘n-1’ dimensional hyper-plane in an ‘n’ dimensional space. I knew that given a function that produces ‘n’ bits, the matrix would be a ‘(2^n)x(2^n)’ square matrix and hence I was looking for the reflection of a point about a ‘(2^n)-1’ dimensional hyper-plane. That was the true nature of the matrix, the fact that it is useful to construct a reversible function was only incidental.

 

Of course, when Abhijit first explained this to me and did the math in 2-dimensional geometry, it was a little too much for me to get my head around. I refrained from this approach for two days since the math seemed too hard. But after looking at the problem in several different ways, I went back to asking myself about the nature of the matrix – then it was simple. I worked out the math for the multi-dimensional geometry and coded it up and ran it - and it worked at the first go. Ah, the pleasure of first principles.

 

Yesterday I had a chance to look at my Professor Amr Sabry’s, approach to the problem and I was stumped. I was used to being stumped by the things he did (after knowing him for about a semester) and I was often reeling from the effects of what a few well thought out lines in Haskell can express. However this time I was stumped because I thought this was something I understood and yet he had a very different solution - one that wasn’t even an involution!

 

For a major part of last night and today it bothered me that I spent all that time trying to solve the wrong problem. It annoyed me a lot – what was the point in putting in all that energy to solve a problem if it was the wrong one?

 

Thinking about this caused me to realize something important – in research, unlike in the commercial software world where I spent the last several years – it is equally important to understand why the problem exists and to question to nature of that which causes the problem to exist, as it is important to solve the problem itself.

 

This should have been obvious, but it was not. The world of commercial software or in general the world that practices software engineering in a way that is not research oriented has certain rules of problem solving that are different  from those of research. The more creative and intellectually challenging of those environments let you take your problems and solve them in any way you want. The lamer environments put too many bounds on how you solve your problems. Very rarely, almost never, in commercial software do we get the freedom to ask the following question in a non-trivial way ‘why is this the problem that we need to solve? why is this its nature?’. If you are not in a position to make decisions about the nature of the business, you are not in a position to question the nature of the problem. 

 

This will be tricky lesson to unlearn when I go back to an environment that doesn’t give me this freedom.

This article is relevant in the context of

Search for Yield the Magnificent

Yielding to Magnificence

 

Other relevant articles include:

Iterators that listen (for Python, by Sidharth Kuruvila)

Implementing a generator in Ruby (by Sidharth Kuruvila)

Implementation of Iterators in C# 2.0

 

I finally got down to ironing out the issues in the previous (rather hasty) entry about scheme iterators. I have code that is a little better tested.

 

To sell any idea, you have to demonstrate the value that believers in the idea get, before you discuss the cost. So here is the value –

 

Iterators support a style of programming where you separate producers of streams of data from consumers of these streams. For example you want to do a certain something on strings of text, irrespective of where the text comes from. In a more general case, iterators are a more powerful programming device, they can be thought of call-tree walkers, they can be thought of the notion of structured programming as applied to continuations. (Refer: Warming up to Iterators, Ruby: Containers, Blocks and Iterators, C#: Create Elegant Code with Anonymous Methods, Iterators, and Partial Classes)

 

The following is a demonstration of yield (similar to yield in Ruby, C# or Py) as a device to create iterators in scheme. There are some extensions to the idea, so the yield implementation here can do more things than the any of the other implementations can do (refer here for details). The implementation below is however useful in a functional context (its easy to see the use of yield in a imperative context). All of the code snippets below are functional in nature, the actual implementation of iterators need not be, but these internal details are abstracted away from you.

 

lambda-iter, yield, foreach

Iterators (functions that use yield) are defined using lambda-iter

 

(define even

  (lambda-iter ()

        (let loop ((i 0))

          (printf "even recieved ~a ~n" (yield i))

          (loop (+ i 2)))))

 

; Using foreach

(foreach (even)

         (printf "it = ~a ~n" it) ; ‘it’ is the yielded value

         (if (> it 20)

             (break 0)) ;break out if we has enough

         it) ;return the yielded value to yield

 

The even above is an produces an infinite stream of even numbers. The parameter to break is the return value of the foreach. ‘it’ is the value of the value that has been yielded. This common to many languages (Groovy, COmega etc). Everything else should be easy to understand.

 

coroutine, co-move-next, co-value, co-return, co-finished?, co-not-finished?

Iterators can be turned into first class entities as follows –

 

; Using coroutines explicitely

; Here the control flow mechanism is something we control

(let loop ((co (coroutine (even)))) ;create the corotuine object

  (let ((co (co-move-next co))) ; start/advance the execution

    (printf "Yielded ~a ~n" (co-value co)) ; print the yielded value

    (loop (co-return (co-value co) co)))) ;return the yielded value

 

There, that’s said, you have all the devices that you need for a yield the magnificent implementation for scheme. There are more things in this implementation to make it useful for general purpose programming, but this much covers all the intellectual content. What follows is some essential documentation after which we have some of the extra forms.

 

Documentation

lambda-iter

(lambda-iter <params> <body>)

Same as lambda, except that you can do a yield in its body

 

yield

(yield <value>)

Yields a value to the caller

 

foreach

(foreach <iterator> <body>)