Eigen Vectors and Basis!

Looks like, I'm on a roll with Dr. Maths. He's explained Eigen vectors this time, and trust me this is the best one, so far I have come across.

Source: http://mathforum.org/library/drmath/view/51971.html

I will give you a physical description, i.e. using 2 or 3 dimensions
only, though the ideas can be extended to n dimensions where n is as
big as you please.

You will be aware that if say a (2x2) matrix M operates on a two-
dimensional column vector v, then that vector is transformed in
magnitude or direction or both to the vector v'.

    So   M.v = v'

Now for the general (2x2) matrix M there are 2 eigenvalues k1 and k2
with associated eigenvectors u1 and u2 with the property that:

        M.u1 = k1.u1

        M.u2 = k2.u2

So any point on the vector u1 is transformed to k1.u1 when operated
upon by M, and similarly any point on u2 will move to k2.u2 after
transformation by M.  In some problems where M is to transform a
complicated figure or we wish to describe the transformation clearly,
it is convenient to use u1 and u2 as the base vectors - i.e. give
coordinates of all points in terms of u1 and u2 rather than the usual
(x,y) coordinates, and the transformation matrix then becomes

        |k1    0|
        |0    k2|

We can find powers of matrices very conveniently using eigenvalues and
eigenvectors.  It is easy to show that

  M = (u1 u2)|k1   0|(u1 u2)^(-1)
             |0   k2|

where (u1 u2) is the 2x2 matrix P formed by the columns of u1 and u2.

 Then M^n = P|k1   0|^n P^(-1)
             |0   k2|

      M^n = P|k1^n    0|P^(-1)
             |0    k2^n|

In probability theory, powers of matrices are frequently required,
sometimes infinite powers, so some device for handling such a problem
is clearly very important.

Again, mind-blowing view of something that we hear daily. In short, if you choose your basis to represent a vector as the eigen vectors of the transformation (or Matrix) then working with the new transformation (or matrix) and new vector is simple and straight forward!

What actually is a Determinant of a Matrix? Two views!

From the way(s) it is calculated to the uses of finding it after doing such mystical calculations. , Determinant of a matrix has always been a mystery for me (except for few things like finding the rank of matrix). Today, I stumbled upon this link on Dr. Math:

http://mathforum.org/library/drmath/view/51440.html

 He has given two very different sounding yet equivalent definitions of the Determinant. Here I reproduced it in his own words:

The first is geometric. I assume you've plotted things in an x-y
coordinate system, right? I assume you can imagine doing the same
thing in three dimensions with an x-y-z coordinate system as well.

In 2-D, when you talk about the point (2, 4), you can think of the
"2" and "4" as directions to get from the origin to the point -
"move 2 units in the x direction and 4 in the y direction."  In
a 3-D system, the same idea holds - (1, 3, 7) means start at the
origin (0,0,0), go 1 unit in the x direction, 3 in the y direction,
and 7 in the z direction.

Similarly, you could have coordinates in one dimension, but there's
just one number.

The determinant of a 1x1 matrix is the signed length of the line from
the origin to the point. It's positive if the point is in the positive
x direction, negative if in the other direction.

In 2-D, look at the matrix as two 2-dimensional points on the plane,
and complete the parallelogram that includes those two points and the
origin. The (signed) area of this parallelogram is the determinant.
If you sweep clockwise from the first to the second, the determinant
is negative; otherwise, positive.

In 3-D, look at the matrix as 3 3-dimensional points in space.
Complete the parallepiped that includes these points and the origin,
and the determinant is the (signed) volume of the parallelepiped.

The same idea works in any number of dimensions.  The determinant
is just the (signed) volume of the n-dimensional parallelepiped.

Notice that length, area, volume are the "volumes" in 1-, 2-, and
3-dimensional spaces.  A similar concept of volume exists for
Euclidean space of any dimensionality.

Okay. That's the geometric definition. I like it because I can make a
mental picture of it. Here's the algebraic definition:

I'll do it in 3 dimensions, but exactly the same idea works in any
number of dimensions.  Let's look at the determinant of this matrix:

  | a11 a12 a13 |
  | a21 a22 a23 |
  | a31 a32 a33 |

The numbers after the "a" are the row and column numbers.

A permutation of a set of numbers is a re-arrangement.

For example, there are 6 permutations of the list (1 2 3), including
the "re-arrangement" that leaves everything unchanged). Ignore for the
moment the "+1" and "-1" after each one:

(1 2 3) -> (1 2 3)   +1
(1 2 3) -> (1 3 2)   -1
(1 2 3) -> (2 1 3)   -1
(1 2 3) -> (2 3 1)   +1
(1 2 3) -> (3 1 2)   +1
(1 2 3) -> (3 2 1)   -1

Now imagine that you start with three objects labelled 1, 2, and 3
arranged as they are on the left, and need to convert them to the
order on the right, but you're only allowed to swap one pair at a
time. To get to the final arrangement, you'll find that there are lots
of ways to do it, but every way (for a particular rearrangement)
always requires an even number of swaps or always requires an odd
number of swaps. I've labelled those that always need an even number
of swaps with +1 and those needing an odd number as -1 above.

Now write down 6 products of the "a" terms, where the first number
for each term is 1, 2, 3 and the second number is the rearrangement
above for each of the six rearrangements.

Here's what they are, in the same order as above.  Be sure you
understand this step:

a11*a22*a33
a11*a23*a32
a12*a21*a33
a12*a23*a31
a13*a21*a32
a13*a22*a31

The determinant is just the sum of all 6 terms, but put a "+" in
front if the rearrangement is even, and a "-" in front if the
rearrangement required an odd number of swaps.

Here's the answer:

+a11*a22*a33 -a11*a23*a32 -a12*a21*a33
+a12*a23*a31 +a13*a21*a32 -a13*a22*a31

For a 4x4 matrix, there will be 24 rearrangments, like this:

(1 2 3 4) -> (3 2 4 1) +1
...

so there will be 24 terms in the expression of the determinant.

For a 5x5 matrix there are 120 rearrangements, so there will be 120
terms in the determinant, and so on.

For an NxN matrix, there will be N! (N factorial) terms, where
factorial means you multiply together all the terms from N down to 1.
For example, 5! = "5 factorial" = 5x4x3x2x1 = 120.

 Seriously, this gyaan is totally refreshing and an eye-opener!

Unary Subset Sum: myth or reality?

Subset Sum problem [SUBSET SUM ]:
Given a list of n numbers and a number k, is there a subset of the numbers that
adds to exactly k? For example, the answer is yes for  <(3, 4, 12, 7, 4), 20> and no
for <(3, 4, 12, 7, 4), 6>.

When the input is expressed in binary (or any other base except unary), it takes exponential time to solve this problem. But hang on!

Unary Subset Sum problem [UNARY SSUM]:
Same problem but the input is expressed in unary!

Result: UNARY SSUM is in P!

Here are the details, that are taken from http://www.cs.virginia.edu/~evans/cs3102-s10/ps/ps6/ps6-comments.pdf

• Why does the NP-completeness proof for SUBSET SUM fail to show UNARY SSUM is NP-complete?
  Answer. The crux of the question is that we measure complexity as a function from the size of the input to the number of steps required to run the decided on that input. When the input is represented in unary, the size of the input is equal to the value (that is, it takes x squares to represent the input value x). When the input is represented in binary (or any higher base), it takes log x squares to represent the input value x. Hence, the if size of the input in binary is N, the size of the same input in unary is 2^N. This, the size of the input increases exponentially, even though the problem is of the same difficulty as it would be for the corresponding binary input. The reduction proof fails because the reduction from 3SAT to UNARY SSUM requires more than polynomial time. The input size increases exponentially, so the transformation to generate the corresponding input for UNARY SSUM requires a number of steps that is exponential in the size of the input.
• Show that UNARY SSUM ∈ P.
  Answer. To show a language is in P, we need to show there is a polynomial-time algorithm that decides it. Note the we can simulate a nondeterministic TM in exponential time using a deterministic TM. Hence, if SUBSET SUM is in NP, we know UNARY SSUM (the same problem, but with exponentially larger input size) is in P, since we can solve it by first converting the input to binary representation (which can be done in polynomial time) and shrinks the input size to log N. Then, we can simulate the nondeterministic polynomial-time TM running on this input (which has size log N) in time that is exponential in its input size, which is polynomial in log N.

the sorted Array and the scanner problem continued…

Wherein the previous post gave the efficient step size for this problem, but there is still a scope of improvement.  Suppose the array size is 100, with our approach the maximum number of comparisons required would be 10+9 = 19. Could we beat this? Yes, I suppose. What if rather than having a fixed step size of sqrt(n) throughout the algorithm, we opt for dynamic step size. Let’s start with step size 18 and see if we could beat our previous answer of 19. The first comparison will happen at 18^th element and if the search element lies in this group then we need another 17 linear comparisons in worst case to find the element in that group making a total of 18 comparisons. Now if the search element is greater than 18^th element then we have to consider the next group. And here lies the secret.  We decide to shrink the next group size by 1, so that this group has 17 elements rather than 18. The reason for this is, we want the total comparisons to be strictly 18 in worst case and since we have already used up one comparison at 18^th element, we have only 17 remaining. Thus to search the element in the second group we need 16 more comparisons and hence making the total comparisons equal to 16+1+1=18 in worst case. Now what we really have to do is to continue this idea until all 100 elements are exhausted. So the group size continues to reduce by 1 at each stage. Hence the third group would have 16, fourth would have 15, fifth would have 14 and so on and so forth.

This algorithm makes sure that we won’t cross the count of 18 comparisons at any cost. But why is it only the number 18? Why not 17? Yes 17 would just do fine. Even the number 16 does remarkably well. But again, as with the previous post what’s the ideal value to start with, since we cannot go forever reducing the number. The only cue we have at this point is whatever count we start with, it should assure us that it covers all the 100 elements. Suppose we start with step size equal to 10 and at each successive group we reduce the group size by 1 to maintain the count. But all the groups so formed doesn’t cover all the 100 elements since the total elements covered in all groups is

10 + 9 + 8 + . . . . . . + 3 + 2  + 1 = (10*11)/2 = 55

So step size 10 covers only 55 elements. Though it failed to be an ideal answer it did give us an insight to find the one. If we start with step size equal to x then the total number of elements covered by the groups formed by x is

x + (x-1) + (x-2) + . . . . . . + 3 + 2 + 1

=∑ x 

Thus the only condition that makes x the ideal choice is that the above summation should cover all the n elements in the array. Hence we have a new equation –

∑ x ≥ n

(x*(x+1))/2 ≥ n

=>  x² + x ≥ 2n

i.e.  x² + x  - 2n ≥ 0

Since we are looking for least value of x,

x² + x  - 2n = 0

And the solution for this is

x = (-1 ± √ (–1 – 8n))/2

For integer value,

x = ceil ((√ (8n + 1) -1)/2)

Thus for n = 100, x comes to be 14 and I bet you can’t beat this!

That awesome feeling when IISc shortlists you!

That was the sweetest shock of my life. Life had never been so harsh before this shock. After deciding to study further in Computer Science, I had a rigorous schedule for nearly 4 months; mainly because I was from Electronics and Communication background. Though my 5+ year experience had helped me a bit, but its impact was almost negligible to be noticed, given the syllabus for GATE CS. Keeping my passion up and perseverance locked, I never gave up till the day of the exam. Obviously, so much pressure had made me feel nervous. All my effort for days, weeks and months was set up for evaluation in just three hours on that day. All that mattered were those three hours and nothing else. Voiding all the bumpy thoughts, I tried concentrating on the question paper. After the battle of three hours, I was completely shattered and discontented. It was the most hopeless paper I had ever given with such strong preparations. Even in mocks, I had performed way better. Bygones were bygones! I didn’t give a damn and went to Goa.

 

After 2 weeks, my curiosity arose. I started researching on internet only to find out that it was the most difficult paper ever. That pacified me. But the guilt feeling continued, as I had made several silly mistakes, which I shouldn’t have made even in dreams. But those got complemented with the questions that I had solved which were very tricky and tough. Keeping my feeling to myself, I waited for the results and when the site displayed AIR 273, I was on cloud nine. That was only but unbelievable.

Being in top 300 across the country, I was completely sure of getting into at least one IIT. Checking with previous year trend, all IITs except B, M and IISc had open heart to accept me. But destiny had something else to say. Things turned very different. This year scores were very low compared to last year’s. With my score, last year students had got AIR around 400-450. And those students spoiled my dessert. Then a day came where I was waitlisted for IITG and R. And worse more, it was not sure whether I could make it to any of them! And the next best option was NITs, which I despised. And there were few private universities like IIITH which lacked ‘the tag’.  Disappointed with all the happenings around me, I had no option to take a seat in NIT Surathkal otherwise I would also be debarred from NIT counseling. After taking admission, I set my journey back to home. 

Flashback:

All this while, there was an interview whose result was yet to come. And I never had hopes on it. The reason was simple – IITs were reluctant to accept me; why would, their god father, IISc would be in mood. That was the interview for MSc (Engg) aka MS for Computer Science I had given in IISc. And there was a big reason why I attended that interview. Being in top 300, I didn’t opt for any MS course in any IIT. Though I had applied everywhere, I didn’t take the pain to attend them. But this one was lucky. I had my flight to New Delhi for IIT Roorkee from Bangalore on 6^th June and luckily IISc had scheduled my interview on 4^th June. So I thought of giving it a try since what I had to do was just reach Bangalore one day before and that was not too much to ask for. Facing disappointments one after another, I went to IISc without any thorough preparation. I just revised the 10-page concise notes that I had prepared for GATE. I knew I had lost half war before entering IISc itself. Another disappointment from SERC pushed me down to depression zone. I couldn’t even clear SERC written test that was scheduled on the same day but in morning session. To keep me fresh for CSA interview that was in the afternoon session, I started solving few questions from SERC test which I couldn’t solve.

After having a Dosa for lunch I went to the CSA department for the test. This was the time I was at my lowest since I started preparing for GATE. It was all but GATE success I had with me to flaunt and nothing else. And destiny had screwed up that also. Hopelessly I sat for the written. And for a change it was a good attempt. I could solve as much problems I could and without any silly mistakes. It all made sure that I was shortlisted for interview. With feeling of nothing-to-lose anymore, I faced the interview. The affair lasted for around 40 minutes before they allowed me to leave. By that time, I was sure that it wasn’t a smooth affair. I knew I had enough talent to answer them for all their questions, but the feeling of nervousness kept popping off sporadically. Trying to justify my talent, I asked them for one more chance to a question to which I had responded haphazardly. But they didn’t allow, I guess they had predefined time for each student. But the reply they gave was inspiring and motivating. It was indeed my silver lining. They said that they were already happy with my performance and I had done very well. Gosh! I was again on cloud nine with silver lining. I left the hall hurriedly and so did I leave IISc. Finally, after a fortnight SERC published their results. That indicated CSA was also on the way. But having no worthy offer in my hand, I had no option but to accept NIT Surathkal VLSI offer. CSA site only mentioned, they would announce the results soon. But that soon never came soon. I took the admission and set my journey back to home.

Back to present:

During the journey I kept refreshing CSA webpage repeatedly on my cellphone to find out if they had realized that their soon had overshot the deadline allotted to the term ‘soon’. But all in vain, they preferred their own definition of ‘soon’. Disappointedly, I switched off my cellphone and went into a deep sleep. Finally when I opened my eyes, I was still more than an hour away from my hometown.  My heart requested my brain to check CSA website but my brain turned it down rudely.  With request turned down, I had nothing but to gaze the serenity outside the bus. After a long journey with open eyes and nothing to do, I reached my hometown. I caught a local bus to my home. Finally, during that time I got permission from my brain to check the site. Actually, the curiosity had turned into formality. With no hopes, I opened the CSA page and was shocked; they had declared the shortlisted candidate names. Desperately, I clicked the link as if it opened the door of some mummy’s cave that had treasures. Indeed they had declared the results. They first mentioned PhD students and I failed to find my name there. I had applied for both PhD and MS. With shattered dreams, I scrolled down to the list of MS students. As soon as it showed the caption MSc (Engg) students, my browser crashed. Wow, what else I could expect at such a low point in life. Few things, which were close to my heart, also betrayed me at such stage. Not succumbing to pressure, I gathered all courage in the world to open the browser again. It took time to load the CSA web page and all that seemed like years. And then again it took years to open the shortlisted site. Finally I was on the same page which I was years ago. Thanks to technology; time travel to past was possible now. 

With all the gathered courage, I scrolled down to the MSc (Engg) list and there, stood my name written in golden words. It was as if destiny had written it. It did indeed open the doors of my destiny. My eyes refused to move away and brain did hundreds of parallel calculations to ensure that it was but my name. I was still for few seconds or perhaps for minutes which seemed like seconds. That was the moment of my life. It’s difficult if I could face any such moment in future because it was rarest of the rare. Immediately I opened my laptop and rechecked on CSA site. My name was still sparkling there. That feeling took time to sink in. I took a print screen of that page and preserved it for coming years. Yes! it was a life time achievement. Even in my farthest dreams I had not dreamt of getting into IISc. All the way, I always thought of IITs and never thought beyond them. To me, IISc was always special and meant for few specially gifted students. And luckily, I was one of them; I was an IIScian now. As they say, destiny gives you what you deserve, not what you want. True it is.