You are currently browsing the monthly archive for March 2009.

A few years ago, during undergrad days, myself and  friend Ramani during our lazy 75 paise mini canteen tea outing, were discussing a small riddle. It was motivated from a real world experience from our computer center in NIT Calicut (REC Calicut). In REC those days, we students almost exclusively used rubber slippers (Yes, those Paraqon brand which used to cost 20 rupees or so), usually called by the name ‘chappels’. With that, we were not only comfortable while walking and running around, but we’re equally at ease playing cricket and badminton with the very same foot support; and many other things too, including jogging. Those thin hard rubber slippers used to last an year or more without giving much trouble, other than perhaps an occasional tearing of the rubber tie. In all, we were at peace with that.

But there was an issue, not exclusively for this brand, but for chappals in general (shoes were a luxury of sort in the campus;atleast it wasnt very common). Not for everyone though! If and only if you were fancied of visiting the computer center! Well, computer center wasn’t all that fanciful then, since we were provided with only graphics less Unix terminals (no colour monitors!). You might wonder, huh! what age am I talking about? Besides, Internet and Emails were only taking shape then. Chats and browsing were not quite there yet;Unless you felt a touch inferior to the computer wizkid around, that was not a compelling centre de visite. As, ‘would be‘ electronics and communication engineers we had that occasional inferiority complex!. Computer center was air conditioned and was strictly slippers free. We were expected to keep our valuable slippers outside (no clock room luxury! well that was not a necessity either) before entering to that cooler room, filled with monochromatic terminals. Since most of the chappals dropped outside were alike (in size and also sometimes color) there was a good chance that at the time return, we ended up with a different pair of slippers (Some folks found happy for themselves by a visit to the computer center, just for a pair change, often to an improved lot!).  Sometimes, we ended up having differently colored ones, say left foot white and right foot blue. That wasn’t a problem socially either, as long as you stayed within the campus. It was socially accepted within the walls!

Anyway, coming back to the riddle we were busy conjecturing on. We wanted to automate a clock room. The idea then would be to just deposit the chappals there at random. The clock room work automatically. Upon asking (at the time of return, say) it will select a pair at random and give it to you. Sorry, you cant have a choice. Just accept and hope for the best. We asked the questions:

1) What is the probability that everyone gets their own chappals

2) What is the probability that none of them get their submitted pairs

Assume n number of  people (and hence n pairs). We can assume that, a pair is a single entity (say both left and right slippers are tied and submitted as one) . This simplified the problem to n people n slipper scenario. A simplistic model assumeed that all n people submit their slippers at the same time. We wanted to build that great randomized clocker machine! And we wanted that to work for any n, which means, the algorithm had to be implementable and to work well in expectation!

We had thought and pondered about it for a while, then. In the end, we had found that the first one is easy, but the second one a little harder to generalize for beyond n=10 or something.  As busy undergrads, we left the problem after an hour of discussion, probably until we had finished sipping the tea. Aside, we were busy with many other extra curricular activities including a 3 hour daily cricket match at the lush green international hostel ground. The megadeth team, as we proudly grouped ourselves, the electronics and communication batch hardly missed those cricket matches. We were electronics engineers and had taken pride in ourselves by not really bothered to ask any fellow discrete math or combinatorics folks! That perhaps helped in some sense.  Ramani found management more interesting than those technical details of counting. I am sure he took the right career. Anyway…too much digressing already!

Now, it turns out that, the very same problem is akin to a well known problem in combinatorics. It is called the Hatcheck lady problem. It is fairly easy to solve it using the inclusion exclusion principle. The proof outline is shown below. As I type, memory fetches that discussion,  sitting leg-folded on the cement bench at the REC mini-canteen, perhaps an occasional cool breeze around too. 

The inclusion exclusion principle is the following:

\lvert \bigcup_{i=1}^{n} A_{i} \rvert=\displaystyle\sum_{i=1}^{n}{\lvert A_{i}\rvert}-\displaystyle\sum_{1\le i_{1}<i_{2}\le n}^{n}{\lvert A_{i1}\cap A_{i2} \rvert}+\displaystyle\sum_{1\le i_{1}<i_{2}\le n}^{n}{\lvert A_{i1}\cap A_{i2}\cap A_{i3} \rvert}

                 +\displaystyle\sum_{1\le i_{1}<i_{2}\le n}^{n}{\lvert A_{i1}\cap A_{i2}\cap A_{i3} \rvert}+\ldots+

                 +(-1)^{n-1}{\lvert A_{1}\cap A_{2}\cap A_{3}\cap\ldots\cap A_{n} \rvert}

The Hatchek lady problem can be stated with a similar story as the random clocker machine. (From Harris, Mossinghoff, Hirst’s book on Combinatorics and Graph Theory)

A lazy professor gives a quiz to a class of n students, then collects the papers, shuffles them, and redistribute them randomly to the class for grading. The professor would prefer that no student receives his or her own paper to grade. What is the probability that this occurs? This indeed is an equivalent statement of the well known Hatcheck lady problem (I guess the exact name come from a hatcheck lady who collects hats and absentmindedly return them)

For Hatcheck lady problem, the probability P(n)=\frac{D(n)}{n!}.

D(n)=n!-\lvert A_{1}\cup A_{2}\ldots\cup A_{n}\rvert=n!-\frac{n!}{1!}+\frac{n!}{2!}-\ldots+(-1)^{n}\frac{n!}{n!}

= n!-\displaystyle\sum_{k=1}^{n}{(-1)^{k-1}\binom{n}{k}(n-k)!}=n!-\displaystyle\sum_{k=1}^{n}{(-1)^{k-1}\frac{n!}{k!}}

P(n)= 1-\displaystyle\sum_{k=1}^{n}{(-1)^{k-1}\frac{1}{k!}}

When n gets larger and larger it converges asymptotically to a constant!

\displaystyle\lim_{n\to\infty} P(n)=\displaystyle\lim_{n\to\infty}{\displaystyle \sum_{k=1}^{n}{\frac{1}{k!}}}=\frac{1}{e}

While the talk and boom about multimode multiband phone in CMOS is turning greener, there should be a natural question around it.  How about doing all these in software? Rather add a level of programmability such that a great deal of issues from a  hardwired implementation are shifted to more flexible firmware.  Without contention, pros and cons with the idea of programmability still prevail. Clearly, one definite advantage I see with programmable design is the significant cost reduction and reuse.  Additionally a migration or upgrade, which is imminent from a future gadget design point of view, can get done with relative ease with a programmable multimode chip. Building a suitable processor architecture to suit the modulations schemes (say an OFDM based scheme can have an inbuilt FFT engine or a WCDMA can have a correlator engine). Aren’t anyone working seriously in these directions? I am sure there are many, atleast startup ventures.  Vaanu and Icera indeed are two things coming to my mind.  How about the big boys? There were lot of furies about software programmable baseband chips being developed. Not quite sure what is the latest in that front.  Isn’t it the next big thing in the offing? I am sure the EDA big houses have thought ahead for building tools for a heavily software oriented design, at least for years ahead. Or is it that, I am jumping the gun a little too far? However,  I see some top level bottlenecks in making this programmable multimode chips realizable at an easier pace than a textbook concept. One of them is difficulty in getting away the analog front end. As a matter of fact, now I feel that, analog is going to stay.

So where are we heading to? Clearly, an all CMOS multiband multimode single chip (baseband and analog) with a near perfect RF and a software architecture would be the ultimate holy grail of cellular chip design. How many bands and how many modes to be incorporated becomes less important, if the programmability aspect is assured. Challenges within a single chip concept are themselves many.  Clearly the RF portion is expected to take up lesser share of the overall chip size. An all digital front end is aimed in that direction. While a direct digitization of radio signal of high frequency eliminates analog life process significantly, there are several practical bottlenecks with this Utopian design model.  We are not quite there to say good bye to analog entirely. Analog signal processing is still critical and inevitable, even for a programmable multimode dream.  I will give you some numerical facts to substantiate my claim:

Suppose we decide to build  programmable all digital zero if receiver for a 2GHz system (around the UMTS band). Then,  Shannon Nyqusit sampling would demand at-least 4 G samples/second.  Even with  a processor which clocks 4Ghz and say 8 operations per cycle, our full steam purchase is going to be a maximum 32000000 operations per second. This theoretical figure is based on the assumption that processor memory is fully utilized. At the sampling rate of 4G samples/second, we only are going to get \frac{32 \times 10^{9}}{4\times 10^{9}}=8 operations per sample. How are we going to have all the fancy radio algorithms shape life with this? Even to implement realistic functionality of a typical modern radio, this is inadequate. Another important thing is the imminent power dissipation to run a processor at 4 GHz. For a portable gadget, where  these chip are targeted for, we still need more and more hand in hand optimization and integration with analog processing, software as well as digital processing, in addition to an optimized system architecture. My feeling is that, the analog front end is going to stay for some more time, if not for ever. At least on the immediate future, we need more inroads from analog processing, to realize the small size, cost effective multiband multi mode chip dream.

From this blog piece, I came to know that the smart MIT theoretical computer scientist Madhu Sudan is making a move from MIT to industry. He is set to take up a research position with Microsoft. At this economy troubled days, lesser mortals would take the conservative route that ensure stability and so on. They would say a move from a tenured professorship to a more volatile industry is risky. But then one of the smartest mind in the world can have a world revolve around him, if need be. So no surprises here. On the positive side it is a gain for industry, while it is a big loss for MIT, if Madhu decides to stay away from academia for too long.

Interestingly, on the very same blog, someone commented about other famous moves. Apparently, Venkatesan Guruswami, Madhu’s celebrated student is also making a permanent move from UWash to CMU.  In industry, we are often associated with frequent hops. Academia is not too immune to attrition either. However, I see no harm in making smart moves. It is going to help the world, atleast  in expectation.

As in EPFL too, there is imminent big fish attrition(s). Tom Henzinger and his wife Monika Henzinger are about to leave EPFL to take up a permanent position in Austria. The awesome twosome will be missed in EPFL.

I wonder how this song found itself a way to the drains!  I remember listening to this audio in All India Radio chalachithraganangal program during childhood. It is a little slow but I have enjoyed the  rhythm. Never seen this video before. Now, the video brings more nostalgia about those paddy fields and picturesque Kerala, my home land.  Missing Kerala!

Hope you guys enjoy this music. (For information the music is in malayalam)

Today, there appeared an interestng (and perhaps general) question posted on the Linkedin Analog RFmixed signal group. The question was this “Regarding multi-mode multiband RF transmitters for handsets (CMOS), what do you think are the hot issues (besides PA)?” I have given a short overview of the challenges that I could see when a multi mode phone is to be designed on CMOS: The phone has to support a wide range of frequency bands as well as multiple standards/technologies/modulation/air interface. Here is what I wrote.  I am not sure whether the discussion is accessible to public. Hence I repost here. 

Integrating the RF transmitter and receiver circuits is a challenging thing since we have to support multiple bands (within a single mode. Say GSM/EDGE should support GSM900 to 1900 bands) as well as support for multiple phone modes. For instance a natural multi mode multi band phone supporting GSM/GPRS/EDGE/WCDMA/LTE will have to consider a wide frequency ranges from 850MHz to over 2GHz. If we were to consider incorporating GPS and WLAN, add that extra consideration. Not just the transceiver circuitry, but also other components such as oscillators, filters, passive components, frequency synthesizers and power amplifiers. Another thing is that, for multi mode, the sensitivity requirements are much more stringent than a single mode, multi band design. 

Since CMOS offers low cost, better performance and better scaling, to me that is the way forward. The natural choice of transceiver in CMOS would be the direct conversion/Zero IF, since it eliminates the costly SAW filters, and also reduce the number of on chip oscillators and mixers. Now, there would be several key design issues to be considered now with direct conversion architecture. Most notable ones are the well known ghost “DC offset” and the 1/f noise. Designers will have the task cut out to get a cleaner front end and as well as near ideal oscillators. 

Now I see another problem with multi mode, depending on what level of flexibility we prefer on this integration. Do we need the phone to operate in multiple modes simultaneously? Say a voice call on GSM and at the same time a multimedia streaming on LTE. In such a case, the question of sharing components are completely ruled out. If not, say some components such as synthesizers and mixers (if in the same band for multiple modes) can be shared. Clearly, simultaneous mode operation will ask for increased silicon die size as well as cost. Challenges may be there for circuit isolation for different modes as well. 

In all, depending on the level of sophistication (and of course all these things will have to be scaled economically too) the design,partitioning, architecture challenges are aplenty. Now the choice between a single chip (containing both analog baseband and digital baseband) versus two chips (analog and digital partitioned) will get a little more trickier with multiple modes. With multiple antennas (MIMO), add another dimension to this whole thing:-(.

The latest edition of The Economist reported this shocking fact based on Amnesty international study on capital punishment: our civilized governments have executed close to 2400 people in the last one year alone; all in the form of capital punishment.  Over 70% of these numbers are coming from China.  Perhaps more revealing is the fact that Saudi Arabia and Iran took the percentage share (per population) when it comes to executing supreme order, all to its people. 

Now, there may be a stronger story to defend these killings, because some of those criminals may indeed have done heinous crimes. But that, simply cannot justify capital punishment, Can it? To me, killing a human on any count is unjustified. By doing so, we are exhibiting more insanity. Why killing? We could rather put them in jail and let them be forced to work extra hard and learn the hardship of life. 

The other day, couple of my Iranian friends and I were discussing about the sort of criminal law practiced in our respective countries (here India as in my case and Iran for them). One of them asked me about the kind of punishments that would be given for instance to a guy who accidentally injures someone on the road.  I had to tell him, in India, a capital punishment is usually given only in rarest or rare crimes.  Even then, there would be widespread opposition to the hanging.  On the other hand, I was shocked to hear that in Iran, some crimes are dealt with a ‘blood for blood’ response. Apparently in Iran, for a recent case wherein a husband poured acid to permanently disable his wife’s eyes, the judge ruled a replica punishment so that the culprit get to feel the pain and agony that his victim had gone through.  To me, this sounded too uncivilized a punishment, even though the victim deserve no mercy. He surely does not deserve rights  for any decent public life for the heinous crime he carried out.  The best way to punish such barbaric people is to put them through the most rigorous hardship over a prolonged period. That way, they get to experience the bitterness of life. Killing someone to compensate the loss of innocent people  is simply no justification: At least I find no solace to accept it as a civilized way of dealing crime and criminals. 

In a way, by killing the criminals we are giving an easy escape to those in-humans.

The popular documentary on this fascinating mathematical prodigy of 20th century is now available on you tube. Personally, while watching the video, the cam river and the row boat brought a touch of nostalgia! I have heard mountains of stories about Paul Erdős. This documentary is a must watch for not only mathematicians and mathematically curious guys (or guys like me who are just curious about mathematics, mathematicians and mathematical minds or for that matter about anything in this world!), but for everyone interested to know about such an extra ordinary mind of our times.  What a fascinating experience it would have been to listen to one of his lectures live. Now this youtube brought the gap down to finite length/time reality.

I have never seen Erdős. Now that he is no more warrants any thoughts anyway.  In a away I am lucky this semester to attend courses of another prolific mathematician of this era Janos Pach. Interestingly, Janos Pach is one of the few living mathematicians with Erdős number 1.  His lectures on Graph theory as well as the one on geometrical graph theory are truly fascinating. 

Anyway, if you have not seen the documentary yet, here is the link. It is a must watch. I bet, you wouldnt miss the time. On many occasions, the Cam river and its slow movement etches something in the backdrop of those days.  Didnt I like that place?

It appears that, both the LDF and UDF have overcome the usual uneasiness in coming out with the candidate lists to the coming Loksabha elections. Quite strangely, LDF candidate selection meetings turned out to be much like the usual UDF fights.  LDF known for their discipline and ideologies, had to face a lot of mudslinging exercise, not only from opponents, but as well from their allies. However, largely, their candidate list showed some sense of vibrancy by fielding young and cheerful candidates. After all, people need their MPs to talk and present their woes; more importantly present and represent them well in the Parliament.  Personally, I am not too inclined and happy with these Ponnani episode. Nor am I happy with these religious mongers having a big say in these elections.  Sadly, the sense of reality hastens that, even the religious outfits have their agendas waiting to be exploited by one of these two fronts, namely LDF and UDFs.  

Now, what do we have from the UDF list? Quite frankly,  all but two are hopeless. Among the UDF list, I would like Shashi Tharoor to get elected, even though he will have to sweat it out from Thiruvananthapuram. I am not enthused by the religious agenda dominated constituencies like Ponnani and Malappuram, partly because I am ignorant of the real scene there and partly because of my uneasiness in mixing religion and politics.  In the remaining 16 seats, I would rather prefer LDF candidates to win, simply because the opponent candidates stay no chance of being effective representatives. Congress has been lacking smart leaders.  Their usual choices are drawn from the pool of factions and castes.  LDF, in spite of all their hodgepodge alliances, fielded some decent candidates.  It will not be easy, I reckon even for LDF, because the unpleasantness among allies and even within the members of major party CPI(M) is looming large.  Going by the corruption history and ability to stand up and speak, many of the LDF nominees deserve to get elected over the UDF counterparts.  For sure, I would really think Shashi tharoor is an appropriate candidate to represent Kerala.  If elected he can perhaps be a very vocal MP for not only Thiruvananthapuram, but Kerala as a whole. To be honest UDF inspite of the minor opposition from within Congress party, got a good candidate to contest from the state. You can argue that he is not a big wig politician, but he knows more about India and is an exemplary policy maker, which will help in the parliament. 

As a footnote, it is appalling that Rajdeep Sardesai cant even say the word Thiruvanathapuram, not in one, but four or five trials.   Quite pity that, a leading national  reporter cant get this right. I don’t mind a little change in accent, but he seem to care little to get the name correct. Horrible. At least a sense of respect? Anyway, their credibility tag is lost long ago, with their sensational reporting.  Sad thing is that, they seem to continuously relish on that ideology. And they are sort of ridiculing Mallika Sarabhai, by asking something like “You, urban English speaking candidate fielding from Ahmadabad?” It was (and still is) so stupid a question that, Mallika replied in Gujarati to create more splines and wrinkles on their face (Suhasini Hyder the other news anchor in this case). Weren’t they expecting it? Or do they think that, everything in this world revolve around their concept of Indianness? Being a broadcast medium one thing is that, they can say any nonsense, but being responsible is entirely another.  Over the years, Rajdeep who had been such a fine journalist, now all confined to being one among the many, new era sensationalizing breed. It saddens people like me, who had enjoyed their good piece of reporting; all when sensibility prevailed!  She is standing in an election from a constituency where she lives. How ignorant are these urban news reporters on her ability to speak her mother tongue? They fielded similar question to Shashi tharoor as well. For their information, he can speak Malayalam, pretty decently.

Oh boy! Didn’t this five foot five inches little big fella make us feel a little better today? Didn’t those back foot cover drives served our eyes as little soothing gels? Didnt the rolling of the leather ball deflected from middle of that MRF stickered famous bat, on to a lush green turfs to the boundary boards of the beautiful Hamilton cricket ground, fetched moisture to our eyes, even while gluing to the live stream on the LCD screen, all  in the darkness of the midnight hours?  I had stayed awake into the wee hours of a cold Lausanne night, to see his masterful show in the first innings of first test at Hamilton. As  Mark Richardson commentating remarked,  the innings of Tendulkar had been an absolute batting clinic. There were quite a few stamp shots of class, which included a few front foot cover drives, couple of back foot cover drives, the cut shots and the impeccable straight drive which separated the trace of the ball  epsilon inches away from the stumps at the non striker’s position.

The latest talk/demo at TED opened up a fresh life to the possibility of a sixth sense.  The MIT Media labs now have unveiled a prototype of the sixth sense setup. The whole thing is  reasonably economical already and all indications are that this is going to rock some day. Incredible idea which went all the way to realization. Kudos to Pranav Mistry, Pattie Meas and their team.  One thing I am really hoping out of it is that, this paving way to assist disabled people. For instance a blind, deaf or dumb person finding avenues to get a sixth sense aid would be really helpful.

Video Link

An interesting bound (problem from Rudi’s  Modern coding theory book) regarding the chromatic number of a random graph.  I first attempted it during the course.  Here is the problem statement:

C.5 (Concentration of the Chromatic Number – Spencer and Shamir). Consider a graph G on n vertices.  The chromatic number of a graph G, denoted by \chi(G), is the smallest number of colors needed to color all vertices so that no two vertices which are joined by an edge have the same color. Consider the standard ensemble of random graphs on n vertices with parameter p: to sample from this ensemble, pick n vertices and connect each of the \binom{n}{2}Ž ordered pairs of vertices independently from all other connections with probability p. Show that for this ensemble 

\mathbb{P}\left(\lvert \chi(G)-\mathbb{E}\left[\chi(G)\right] \rvert >\lambda \sqrt{n-1}\right) \le 2e^{\frac{-\lambda^2}{2}}.

My solution is as folllows: (PDF typeset as single file is available here. Look for problem 3)

Let G is a random graph with n vertices.  If p is the probability that a given edge is in G. The probability space be G(n,p).  Let \chi be a filter on the set of all such random graphs. We can define a Martingale as follows:


X_{i}=\mathbb{E}[X(G)\lvert 1_{1},1_{2},\ldots,1_{i}],\forall 1\le i\le \binom{n}{2}


1_{i}=\begin{cases}1,&\text{if edge} \quad e_{i}\in G\\ 0, &\text{if edge} \quad e_{i}\notin G\end{cases}

and \chi(G) is the Chromatic number of G. Chromatic number changes at most by one , when the information about the new edge comes in. Clearly, \chi satisfies the conditions for Azuma’s inequality. \{X_i\}_{i\ge 0}

is a Martingale, with \lvert X_i-X_0\rvert \le 1).  Let Z_i=X_i-E[X_i]. Clearly 




Now we can use the Azuma’s inequality on \{Z_i\} to get,

\mathbb{P}\left(\lvert Z_n-Z_0\rvert \ge \lambda \sqrt{n}\right)=\mathbb{P}\left(\lvert \chi(G)-\mathbb{E}[\chi(G)] \rvert \ge \lambda \sqrt{n}\right)\le 2e^{\frac{-\lambda^2}{2}}.

Since \mathbb{P}\left(\lvert \chi(G)-\mathbb{E}[\chi(G)] \rvert \ge \lambda \sqrt{n}\right)=\mathbb{P}\left(\lvert \chi(G)-\mathbb{E}[\chi(G)] \rvert > \lambda \sqrt{n-1}\right), the result 

\mathbb{P}\left(\lvert \chi(G)-\mathbb{E}\left[\chi(G)\right] \rvert >\lambda \sqrt{n-1}\right) \le 2e^{\frac{-\lambda^2}{2}} 


Here is an interesting riddle on random matrices.  

(Rank of Random Binary Matrix). Let R(l,m,k) denote the number of binary matrices of dimension l \times m and rank k, so that by symmetry R(l,m,k)=R(m,l,k).  This is a repost of the solution that I have arrived at (certainly not the first!) and submitted as part of a homework (9) problem from the doctoral course  Modern coding theory (by Rudiger Urbanke) at  EPFL.  The sumbitted solution in PDF is available here.

Rank of a matrix G is essentially the number of nonzero rows when the matrix G is expressed in echelon form. So, we just need to compute the ways these matrices can be created with k non zero rows. Since the elements of the matrix are binary (from \mathbb{F}_{q=2}), we can simply do a counting.

It is trivial to compute R(l,m,k) for k=0 and k>l. For  k=0, only all zero matrix possible, and only one such matrix exist. Hence R(l,m,0)=1. For  l>k>0, since  k>\min(l,m), no matrix exist, which means R(l,m,k)=0 . 

Now we consider l=k>0.  How many ways? We have l=k  non zero rows of the l\times m  matrix, which means all rows must be nonzero. Without loss of generality, for counting, we could assume that, the rows are ordered. The last row (l^{th} row can be be done in 2^{m}-1,  since there anything other than all 0 vector (of size m) is allowed. On (l-1)-th row, anything other than that of row l is allowed. There are 2^{m}-2 ways here. l-2-th row can have anything except any linear combination of the rows l and l-1. This is nothing but 2^m-\left({\binom{2}{0}+\binom{2}{1}+\binom{2}{2}}\right)=2^m-2^2. Row l-3 then have 2^m-\left(\binom{3}{0}+\binom{3}{1}+\binom{3}{2}\right)=2^m-2^3 and so on. In all, Following the same procedure, we can have a total of  

= \left(2^m-1\right) \left(2^m-2^1\right)\left(2^m-2^2\right)\ldots \left(2^m-2^{l-1}\right)

=\left(2^m-1\right) 2^{1} \left(2^{m-1}-1\right) 2^{2} \left(2^{m-2}-1\right) \ldots 2^{l-1}\left(2^{m-l+1}-1\right)

=2^{0} 2^{1} 2^{2} \ldots 2^{l-1}\left(2^m-1\right)\left(2^{m-1}-1\right)\left(2^{m-2}-1\right)\ldots\left(2^{m-l+1}-1\right)



=\prod_{i=0}^{l-1}{2^m \left(1-2^{i-m}\right)}

=2^{ml} \prod_{i=0}^{l-1}{ \left(1-2^{i-m}\right)}

 ways.  For l>k>0, we can construct a rank k matrix of size l \times m in any of the following ways:

  1.  Take a rank k-1 matrix of size (l-1) \times m and add an independent row.
  2.  Take a rank k matrix of size (l-1) \times m and add a dependent row.

For every (l-1) \times m matrix, 

2^{m}-1+\binom{k-1}{1}+\binom{k-1}{2}+\ldots +\binom{k-1}{k-1}=\left(2^m-2^{k-1}\right)

and hence,

R(l-1,m,k-1) \left(2^m-2^{k-1}\right)= R_{1}(l,m,k)

ways. (Essentially avoid all possible linear combinations of existing k-1 rows).  Using the second (item 2 above) method, we can have 1+\binom{k}{1}+\binom{k}{2}+\ldots +\binom{k}{k} = 2^k and 

R_{2}(l,m,k)= 2^k R(l-1,m,k) 

different ways a rank k matrix can be formed. Where,the first term (=1) is when the all zero row is picked as the new row. In\binom{k}{1} ways we can pick any one of the exisiting row as a dependent (new row). In general for 0\le j\le k we can have combination of j existing rows  out of k in \binom{k}{j} different ways to make a dependent (new) row.

So using (1) and (2) we get,

R(l,m,k)=2^k R(l-1,m,k)+\left(2^m-2^{k-1}\right)R(l-1,m,k-1)

Putting everything together,

R(l,m,k) = \begin{cases} 1, & k=0, \\2^{ml} \displaystyle \prod_{i=0}^{l-1}{ \left(1-2^{i-m}\right)} , & l=k>0 \\ 2^k R(l-1,m,k) + \left(2^m-2^{k-1}\right) R(l-1,m,k-1) &l>k>0 \\ 0 & k>l>0 \end{cases}

In this post, I tried (for the first time) to write something in Malayalam, my mother tongue. My dear English only readers, please excuse! The pleasure of writing something in mother tongue is different.  Sadly and regrettably, I seem to have forgotten some of the alphabets of Malayalam. I feel ashamed. 

മലയാളത്തിലെഴുതാന്‍ ഇപ്പോള്‍ വളരെ എളുപ്പമായി. പണ്ട്  ഞാന്‍ മലയാളം LaTex malayalam ഉപയോഗിച്ചിരുന്നതോര്‍ക്കുന്നു (In 2000 or so, it was. Now, latex omega is pretty nice and easy too, especially while LaTexing). കുറച്ചതികം ബുദ്ധിമുട്ടിയാണ് അന്ന് കുറച്ചു വരികളെഴുതാന്‍ കഴിഞ്ഞത്. എന്നാല്‍ ഇപ്പോള്‍ എത്രയോ എളുപ്പമാണ് (all thanks to Google Transliteration). എന്തായാലും വേര്‍ഡ്പ്രെസ്സില്‍ ഒന്ന് എഴുതി നോക്കാമെന്ന് വച്ചു.

കഴിഞ്ഞ രണ്ട്  ദിവസ്സമായി ഞാന്‍ കേരളത്തിലെ രാഷ്ട്രിയ സംഭവ വികാസങ്ങള്‍ നിരീക്ഷിക്കുകയായിരുന്നു. ഇവിടെ യുറോപ്പില്‍ ഇന്റര്‍നെറ്റ് വഴി കിട്ടുന്ന വാര്‍ത്തകള്‍ മാത്രമാണ് ഒരു മാര്‍ഗം. പ്രധാനമായും വാര്‍ത്തകളെല്ലാം വരുന്ന ലോകസഭ തെരഞ്ഞെടുപ്പ് സ്ഥാനാര്‍ത്തികളെ ചുറ്റിപറ്റിയുളളതായിരുന്നു. സി പി ഐ എം, സി പി ഐ തമ്മില്‍ പൊന്നാനി സീറ്റ് സ്ഥാനാര്‍ഥി നിര്‍ണ്ണയം ചൊല്ലിയുള്ള വിവാദം ഒരു പക്ഷേ അനാവശ്യമായിരുന്നു. സി പി ഐ സെക്രടറി വെളിയം ഭാര്‍ഗവന്‍ തീര്‍ത്തും നിര്‍ഭാഗ്യകരമായ രീതിയിലാണ് പത്ര സമ്മേളനം നടത്തിയത്. ഒരു മുന്നണിയില്‍ പ്രവര്‍ത്തിക്കുമ്പോള്‍ ചില അഭിപ്രായ വിത്യസങ്ങളൊക്കെ ഉണ്ടാകുന്നതു സ്വാഭാവികം. പക്ഷേ അത് ജനങ്ങളുടെയും പ്രവര്‍ത്തകരുടെയും മുന്നില്‍ അവതരിപ്പിക്കുമ്പോള്‍ കുറച്ചു പക്വതയൊക്കെ ആകാമായിരുന്നു. ഇത് കോണ്‍ഗ്രസിലെ അടിപിടി പോലെയുള്ള ഒന്നായി മാറ്റിയതിനു വെളിയത്തിന്‍റെ കൊള്ളരുതായ്മ്മയായി മാത്രമേ കാണാന്‍ കഴിയു‌. ഇതില്‍ ഏറ്റവും വിചിത്രം പൊന്നാനി സി പി ഐയുടെ കൊട്ടയോന്നുമല്ല. മിക്കവാറും തോക്കാറുള്ള മുസ്‌ലിം പ്രാധിനിത്യം അത്യധികമുള്ള ഒരു മണ്ഡലം,അതില്‍ ഒരു പൊതു സമ്മതനെ അങ്ങീകരിക്കാന്‍ ചേര്‍ന്ന ഒരു മീറ്റിങ്ങില്‍ തങ്ങളുടെ ആഗ്രഹം അതെ പടി സാധിയ്ക്കാതത്തിന്റെ പേരില്‍ ഒരു പത്ര സമ്മേളനം നടത്തി ശകാര വര്‍ഷം ചൊരിഞ്ഞ് വെളിയം അദ്ദേഹത്തിന്റെ ഉള്ള വിലയും ഇല്ലാതാക്കി. ഒരു കണക്കിന് ഭര്‍ദ്ദനും വെളിയവും ഏകദേശം ഒരേ പോലെയുള്ള മൂക്കിന്‍റെ അറ്റത്ത്‌ ദേഷ്യം ഒട്ടിച്ച രണ്ടു നേതാക്കള്‍. നിര്‍ഭാഗ്യവശാല്‍ രണ്ടുപേരും ഒരേ പാര്‍ട്ടിയില്‍. അതോ ഭാഗ്യവശാലോ?

Inkscape has come off age. Creating vector graphics has now become pretty cool with inkscape. I too tried to make one.  The one I tried is an egg. Afterall, I am convinced that egg is first and then chicken (I mean on eating preference). The drawing is not that stellar neat, but then, I am a novice when it comes to inkscape. This simply is my first drawing and I will be excused, Won’t I? I am posting the scalable vector graphics (svg) file, just in case a random enthusiastic reader find it useful to make it better!

The inkscape source file (svg) is available from this link;

Wondering why I created this figure? Well, I was trying to illustrate the P versus NP. My idea was to say the yellow yolk is P and white outer one surrounding the yolk would represent NP. Anyway that is for another post!

eggs drawn using inkscape
eggs drawn using inkscape
A gallery of svg files are archived (various folks contributed their entries there) at the open clip art library website (you can search and find some)
Since you are my dear reader, it is my privilage to serve you something. Look, I took the extra pain to borrow these yummy stuffs (from here) for you. Enjoy this to get cooked.     

Egg ready to pan

Egg ready to pan

While waiting you can have a cheerful drink!
…and keep visiting me for more!

I am caught with a little trouble to figure out an easier way to set up and solve a  summation of a function of several variables.  I just realized that Mathematica doesnt allow me to add a constraint in the summation operation.  My problem  is that, the summation should be performed over  the ordered partition set of a number

An example, will illustrate the problem definition a lot better.  Suppose I want to compute the sum of a function of 3 variables over all variables such that, the sum of the index variables always equal to a constant n

\displaystyle \sum_{\underset{i+j+k=n}{i,j,k}}f(i,j,k)

Clearly, the indices here runs over all the ordered partitions of the number 3.  Since 3 is not that big a number, we can simply write these partitions by hand and somehow get the job done.  Let us say denote the ordered partitions and unordered partitions of the number n by P(n) and Q(n) respectively. 

Q(3) =( (3), (2, 1),(1, 1, 1)). The ordered partition will have the permutations of each of these on the three positions! So (0,0,3) and (0,3,0) are different sets of P(3) whereas, they are considered as one (3) in Q(3).  The summation needs to be carried over the ordered partition list P(n).  Since both Q(n)  and P(n) grow pretty big with even modest n, the job of manual summation is not that appealing. I really hoped mathematica to aid me here. Unfortunately, I don’t see a way out here, other than the painful individual partition sum.  Anyway, for the curious reader, the sum I attempt are of the following types:

\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }

\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1-n_2)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }

typical values for n is 20 and k is around 10. If any enthused reader finds a way/trick, I will be happy to sponsor a coffee 🙂 (Sorry at this recession time, nothing more 😦 sadly…).

In fact, the first one is easy (Interestingly, I just found a way, while typesetting the blog).  I can do a differential with respect to a_1 and then scale it to get the requisite sum.  It can be written as follows:

\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }

=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \frac{\partial}{\partial a_1}\left[a_1 \left(a_1+a_2+\ldots+a_k\right)^{n}\right]

=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \left[n a_1 \left(a_1+a_2+\ldots+a_k\right)^{n-1}+\left(a_1+a_2+\ldots+a_k\right)^{n}\right]

Second one is the trouble maker 😦

Oh man! power of a coffee.  As I am typing this on a moody Lausanne swiss weather, here comes the trick.  I just made a coffee and that seemed to have worked.  I guess I can apply a similar trick to the second one too.  Basically, we can split them into two expressions and then write each as differential versions of a multinomial sum. Here it is:

\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1-n_2)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }

=\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }

-\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_2)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }

=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \frac{\partial}{\partial a_1}\left[a_1 \left(a_1+a_2+\ldots+a_k\right)^{n}\right]

-\frac{a_1 a_2}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \frac{\partial}{\partial a_2}\left[\left(a_1+a_2+\ldots+a_k\right)^{n}\right]

=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \left[n a_1 \left(a_1+a_2+\ldots+a_k\right)^{n-1}+\left(a_1+a_2+\ldots+a_k\right)^{n}\right]

-\frac{a_1 a_2}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \left[n \left(a_1+a_2+\ldots+a_k\right)^{n-1}\right]

Amazingly, we can simplify both to get a simple looking expression. I am glad! Here is what I finally got:

\displaystyle \sum_{\sum_{j}{ n_j}=n}{\frac{n!(n_1+1)a_1}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }=\frac{a_1\left(na_1+\sum_{i}{a_i}\right)}{{\left(\sum_{i=1}^{k}{a_i}\right)^{2}}}

\displaystyle \sum_{\sum_{j}{ n_j}=n}{\frac{n!(n_1+1-n_2)a_1}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }=\frac{a_1\left(n(a_1-a_2) +\sum_{i}{a_i}\right)}{{\left(\sum_{i=1}^{k}{a_i}\right)^{2}}}

\displaystyle \sum_{\sum_{j}{ n_j}=n}{\frac{n!(n_l)a_1}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }=\frac{a_1 a_l n}{{\left(\sum_{i=1}^{k}{a_i}\right)^{2}}}

This content is password protected. To view it please enter your password below:

Dont these terrorists and such insane folks have no other job? They are much more than a migraine now.  What was considered to be a never ever target has now become the soft target of these terrorists. The latest dastardly attack on the touring Sri Lankan cricketers, near the Lahore stadium in Pakistan make us all the more worried about Pakistan. The horrific memories of Mumbai incident on 26/21/2008 are still ringing and now in the backdrop here is one which happened in the place it originated.  I am hurt and saddened to see and hear these incidents happening again and again.  By all means, these attacks are well planned operations and surely must have a background which cant be beyond the know hows of supporters and the territorial government. Will this be a wake up call to eliminate the terror network. They say cricket is a religion.  Which religion? Fanatics from all religion made a mess in the name of cricket and otherwise.  It is time for the  entire population of Pakistan to come out in public and express a solidarity and say, “you terrorists made a mess of this world and you have no support from us, whatsoever”. Same pledge should be made by everyone in India, Srilanka and even Bangladesh. Terrorism cannot be justified, whether it is internal or external. This applies to not only to Jihadis, but also to folks like Ram sena and LTTE. All the doctrines which insists killing innocent section of population are of the same colour and they don’t deserve a piece of sympathy.  The troubles of our times is getting worsened, ever so deeply. I am lost to get a feel of these fanatics. All these youth armed with AK47 should have been pillars of building a nation; alas! these very promising prodigies are sadly dragged, into those filthy cause in the name of religion and ethnic freedom! Terrible.

I feel sorry for Sri lanka who went ahead to express solidarity to a nation which was deprived of cricket by every other nation including India.  They were promised express security! yet, in the end caught in the fallacy. Same sympathy to Pakistan normal folks who, to their innocence are denied of watching an international cricket game in their land.  Now is the time to stand up and say, strongly against the doctrines which advocates terror. Act now, please…. Humanity is in danger at the hands of these cruel terrorists.  Nurturing a wicked terrorist to kill your enemy can bite you back.  So, never do that.


March 2009
« Jan   Apr »

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 86 other followers


%d bloggers like this: