Skip to main content

Posts

Showing posts from 2011

Mnemonic for π

All the following poems describe a number. 産医師異国に向こう.産後薬なく産に産婆四郎二郎死産.産婆さんに泣く.ご礼には早よ行くな. Yes, I have a number. How I want a drink, alcoholic of course, after the heavy lectures involving quantum mechanics. Sir, I send a rhyme excelling.In sacred truth and rigid spelling. Numerical spirits elucidate, For me, the lesson's dull weight. If Nature gain, Not you complain, Tho' Dr. Johnson fulminate. Que j'aime à faire apprendre un nombre utile aux sages! Immortel Archimède, artiste ingénieur, Qui de ton jugement peut priser la valeur? Pour moi, ton problème eut de pareils avantages. Wie, O dies π. Macht ernstlich so vielen viele Müh!  Lernt immerhin, Jünglinge, leichte Verselein.  Wie so zum Beispiel dies dürfte zu merken sein! The German version mentioned about the number --- π. These are all Mnemonic for π. Japanese uses sounds of numbers, but, other languages uses the number of words. From Yes(3), I(1) have(4) a(1) number(6), you can find 3.1416 (rounded). I fo

Geometric Multiplicity: eignvectors (2)

If eigenvectors of a matrix A are independent, it is a happy property. Because the matrix A can be diagonalized with a matrix S that column vectors are eigenvectors of A . For example, Why this is a happy property of A? Because I can find A's power easily. A^{10} is not a big deal. Because Λ is a diagonal matrix and power of a diagonal matrix is quite simple. A^{10} = SΛ^{10} S^{-1} Then, why if I want to compute power of A ? That is the same reason to find eigenvectors. Eigenvectors are a basis of a matrix. A matrix can be represented by a single scalar. I repeat this again. This is the happy point, a matrix becomes a scalar. What can be simpler than a scalar value. But, this is only possible when the matrix S's columns are independent. Because S^{-1} must be exist. Now I come back to my first question. Is the λ's multiplicity related with the number of eigenvectors? This time I found this has the name. Geometric multiplicity (GM): the number of in

Geometric Multiplicity: eignvectors (1)

I had a question regarding the relationship between multiplicity of eigenvalue and eigenvectors. I am more interested in eigenvalue's multiplicity than the value itself. Because if eigenvalue has multiplicity, the number of independent eigenvectors ``could'' decrease. My favorite property of eigen-analysis is that is a transformation to simpler  basis. Here, simpler  means a matrix became a scalar. I even have a problem to understand a 2x2 matrix, but a scalar has no problem, or there is no simpler thing than a scalar. A x = λ x  means the matrix A  equals λ, what a great simplification! My question is  If λ has multiplicity, are there still independent eigenvectors for the eigenvalue? My intuition said no. I can compute an eigenvector to a corresponding eigenvalue. But, I think I cannot compute the independent eigenvectors for one eigenvalue. For instance, assume 2x2 matrix that has λ = 1,1, how many eigenvectors? one? Recently I found this is related with di

Carpe diem for Billy

An author, Kilgore Trout, uses star system in his novels. Therefore, the same person shows up in the different stories. One of them are Billy. Billy's story is impressive for me, so I will write it here. In a certain Billy's story, Billy confronted a problem in his life. He lost the meaning of his life. He tried to re-invent it by reading science fictions. Since he tried other literatures, but they could not give him the meaning of his life. It was the last his hope.  But since his problem was in the fourth dimensional space in this world, he cannot recognize it. He asked for a help to a physiologist. One day, he saw a talk video of a famous person who recently passed away. He told people: every morning, he asked himself in the mirror, ``If today were the last day of my life, would I want to do what I am about to do today?'' and whenever the answer has been 'no' too many days in a row, he knew he needed a change.  Although Billy heard this idea before, he w

Rational shit by Kilgore Trout

One of the Kilgore Trout's story is called "Rational shit". Se-Cluger people are rational species, they are perfectionist and always act after think, although they don't have a time travel technology.  Each of them usually think about their comfortable houses and happiness. Everything is resolved by discussion, most of them are logical, therefore, there usually no objection to the conclusions. If the problem is not solved, some people just left to the other planets. Killing each other is not a rational solution for them. They can agree that point, that shows they are intelligent. They looked for the perfect rationality, they finally have a technology to change themselves. One day, they have perfect rationality. Energy of the planet is never wasted, all the disease were solved. The future is planned, they care their descendant. However,  they found out they will extinct one day because they are still a life form. The extinction day is far future, however, all the

Mutually exclusive events and independent events are not the same.

Mutually exclusive events and independent events are not the same, therefore don't mixed up [1].  Recently, I started to read a book about probability. In the second chapter of the book [2], I have already found my big misunderstood. I didn't know this for a long time. I am not good at probability. Maybe because I missed very fundamental things like this. I thought mutually exclusive and independent are the same thing. Here, I would like to explain they are completely different concepts. Mutually exclusive events are never happens at once. An example of mutually exclusive events are head of first toss of a coin tail of first toss of a coin One coin toss, head and tail at once never happened. But independent events can happens at once. The definition of independent events is This may not be 0. An example of independent events are head of first toss of a coin head of second toss of a coin These two events are independent. But, I also find this defin

Sample variance and Bessel's correction

The blog is about sample variance and Bessel's correction. What is sample variance? Why is that? Who cares? Are there any better way to choose beers? What is the answer to life, the universe, and everything? Introduction to Sample variance and Bessel's correction and Detailed explanation of sample variance and Bessel's correction

Column space and row space.

(Or how to see the 10,000 dimensional space.) Usually every mathematical area has the most important theorem, Fundamental theorem. In linear algebra, it is called Fundamental theorem of linear algebra. This is about the relationships between four subspaces: Column space, row space, null space, and left null space. But, I don't recall I heard them in my mathematics course in my university. Did I miss that? If I miss that, that is one of the most significant misses. Because I did not know the column space, I had so hard time to figure out high dimensional spaces. I know the row space (though I did not know it has a name), but this doesn't give me a high dimensional space image. I even can not imagine four dimensional space without the column space. But now, I know the column space and it is easy to imagine what is a 10,000 dimensional space. If you are interested in, please see my slides. Or you have more time, read the Gilbert Strang's Introduction to Linear Algebra. Colu

Why parallelogram area is |ad-bc|?

Here is my question. The area of parallelogram is the difference of these two rectangles (red rectangle - blue rectangle). This is not intuitive for me. If you also think it is not so intuitive, you might interested in my slides. I try to explain this for hight school students. Slides:  A bit intuitive (for me) explanation of area of parallelogram  (to my site, external link) . 

Unrealistischer Träumer (4/4): Murakami Haruki Rede zur Verleihung des International Catalunya Prize am 11. Juni 2011

Unrealistischer Träumer (4/4) Murakami Haruki Rede zur Verleihung des International Catalunya Prize am 11. Juni 2011 Wie ich bereits erwähnte, leben wir in einer vergänglichen, sich ständig verändernden "mujo" Welt. Gegen die Natur sind wir machtlos. Die Anerkennung solcher Vergänglichkeit ist eine der Grundlagen japanischer Kultur. Gleichzeitig müssen wir, selbst wenn wir in einer solch zerbrechlichen und gefährlichen Welt leben, fest entschlossen sein, munter zu leben. Wir sollten von diesem positiven Geist erfüllt sein. Ich bin zutiefst stolz, dass das katalanische Volk meine Arbeit schätzt und mich mit diesem Preis ehrt. Wir leben weit voneinander entfernt und sprechen unterschiedliche Sprachen. Selbst die Grundsätze unserer Kulturen sind verschieden. Aber wir haben doch ähnliche Probleme und ähnliche Gründe für Freude und Trauer -- wir sind alle Weltbürger. Deshalb werden so viele Geschichten japanischer Schriftsteller auf Katalan übersetzt. Ich bin sehr

Unrealistischer Träumer (3/4): Murakami Haruki Rede zur Verleihung des International Catalunya Prize am 11. Juni 2011

Unrealistischer Träumer (3/4) Murakami Haruki Rede zur Verleihung des International Catalunya Prize am 11. Juni 2011 In Angesicht der überwältigenden Atomkraft sind wir alle Opfer und Täter. Wir sind alle der Bedrohung durch Atomenergie ausgesetzt -- in diesem Sinne sind wir alle Opfer. Wir haben Atomenergie genutzt und wir können nicht aufhören, sie zu nutzen --  in diesem Sinne sind wir alle Täter. Es ist das zweite mal, dass wir so furchtbare atomare Schäden erleben. Aber diesmal hat keiner Atombomben abgeworfen. Wir Japaner haben diesen Unfall selbst verschuldet: wir haben einen Fehler gemacht, unser Land ruiniert und unser Leben zerstört. Wie konnte das passieren? Wo ist unsere Abneigung gegenüber Atomkraft hin? Dieses Gefühl hatten wir noch lange nach dem Krieg. Unser Ziel war immer eine wohlhabende und friedliche Gesellschaft. Was hat dieses Ziel verdorben und zerstört? Der Grund ist einfach. Es ist "Kouritu". Effizienz. Energieversorger beharren

Unrealistischer Träumer (2/4): Murakami Haruki Rede zur Verleihung des International Catalunya Prize am 11. Juni 2011

Unrealistischer Träumer (2/4) Murakami Haruki Rede zur Verleihung des International Catalunya Prize am 11. Juni 2011 Es liegt daran, dass die Kirschblüten, Glühwürmchen und farbigen Blätter ihre Schönheit binnen kurzer Zeit verlieren. Wir besuchen ferne Orte um Zeuge der Pracht des Momentes zu werden. Wir sehen nicht nur ihre Schönheit, sondern auch ihre Kurzlebigkeit, wir sehen, wie sie ihr Lichtlein verlieren, wir sehen die lebhaften Farben der Blätter verblassen. Wir spüren auch Entspannung bei diesem Anblick -- wir finden Frieden in der Hochzeit von vorübergehender und verschwindender Schönheit. Ich weiß nicht, ob Naturkatastrophen diese japanische Mentalität beeinflusst haben. Aber wir konnten die Reihe der Katastrophen mit einem Gefühl von "so ist es halt" ertragen. Wir überleben, indem wir all die Zerstörung als Gemeinschaft bewältigen. Vielleicht verändern diese Erlebnisse unseren ästhetischen Sinn. Fast alle Japaner sind von diesem gewaltigen Erdbeben

Unrealistischer Träumer (1/4): Murakami Haruki Rede zur Verleihung des International Catalunya Prize am 11. Juni 2011

Unrealistischer Träumer (1/4) Murakami Haruki Rede zur Verleihung des International Catalunya Prize am 11. Juni 2011 Ich war das letzte Mal im Frühling vor zwei Jahren in Barcelona. Ich hatte hier eine Autogrammstunde, zu der so viele Menschen kamen, dass ich die Sitzung nicht in anderthalb Stunden abschließen konnte. Warum es so lange gedauert hat? Weil viele weibliche Leser mich küssen wollten. Ich habe in vielen Ländern Autogrammstunden gehabt, aber nur in Barcelona haben mich Leserinnen um einen Kuss gebeten. Schon an diesem Beispiel erkennt man, wie toll die Stadt Barcelona ist. Ich bin sehr glücklich, dass ich in diese schöne Stadt zurückkommen kann, die so eine lange Geschichte hat und so reich an Kultur ist. Leider kann ich heute nicht über die Kussgeschichte reden. Ich über ein etwas ernsteres Thema sprechen. Wie Sie sicher wissen, gab es am 11. März um 14:46 ein schweres Erdbeben in der japanischen Region Tohoku. Das Erdbeben war so stark, dass es die Erdrotation e

As an unrealistic dreamer by Murakami Haruki (4/4) International Catalunya Prize speech at 2011-06-11

Here is a complete English translation of Murakami Haruki's International Catalunya Prize speech at 2011-06-11, part 4/4.  This is not an official translation.  Please tell me if you believe there are any legal issues in my distribution of a translation,  though I believe this is one of the stories that we all can share. Here is also related German article from Asienspiegel Guardian "As an unrealistic dreamer" Part 1/4  "As an unrealistic dreamer" Part 2/4 "As an unrealistic dreamer" Part 3/4 "As an unrealistic dreamer" Part 4/4 As I mentioned before, we are living in the ephemeral, always changing ``mujo'' world. In front of nature, we are powerless. Recognition of such transience is one of the fundamental ideas of Japanese culture. But at the same time, even if we are in such a fragile and dangerous world, we must have the silent determination to live vividly. We should be invested with this kind of positive spirit. I a

As an unrealistic dreamer by Murakami Haruki (3/4) International Catalunya Prize speech at 2011-06-11

Here is a complete English translation of Murakami Haruki's International Catalunya Prize speech at 2011-06-11, part 3/4.  This is not an official translation.  Please tell me if you believe there are any legal issues in my distribution of a translation, though I believe this is one of the stories that we all can share. Here is also related German article from Asienspiegel Guardian "As an unrealistic dreamer" Part 1/4  "As an unrealistic dreamer" Part 2/4 "As an unrealistic dreamer" Part 3/4 "As an unrealistic dreamer" Part 4/4 In the face of overwhelming nuclear power, we are all victims and assailants. We are all exposed to the threat of this power -- in this sense, we all victims. We extracted the nuclear power and we also could not stop using the power -- in this sense, we are all assailants. This is the second time in history such terrible damage caused by atomic power has been experienced by us. But this time, nobody dropped

As an unrealistic dreamer by Murakami Haruki (2/4) International Catalunya Prize speech at 2011-06-11

Here is a complete English translation of Murakami Haruki's International Catalunya Prize speech at 2011-06-11, part 2/4. This is not an official translation.  Please tell me if you believe there are any legal issues in my distribution of a translation, though I believe this is one of the stories that we all can share. Here is also related German article from Asienspiegel Guardian "As an unrealistic dreamer" Part 1/4  "As an unrealistic dreamer" Part 2/4 "As an unrealistic dreamer" Part 3/4 "As an unrealistic dreamer" Part 4/4 Because all cherry blossoms, fireflies, and colored leaves will lose their beauty in a short time. We visit faraway places to be a witness to the glory of the moment. We see not only that they are beautiful, but we also see them fall down ephemerally in front of us, we see them lose their small light, we see the vivid color of the leaves disappear. We also feel relief when we see this --- we find a peace in t

As an unrealistic dreamer by Murakami Haruki (1/4) International Catalunya Prize speech at 2011-06-11

Here is a complete English translation of Murakami Haruki's International Catalunya Prize speech at 2011-06-11, part 1/4. This is not an official translation .  Please tell me if you believe there are any legal issues in my distribution of a translation, though I believe this is one of the stories that we all can share. Here is also related German article from Asienspiegel Guardian "As an unrealistic dreamer" Part 1/4  "As an unrealistic dreamer" Part 2/4 "As an unrealistic dreamer" Part 3/4 "As an unrealistic dreamer" Part 4/4 The last time I visited Barcelona was spring two years ago. When I had an autograph session here, many people came and I could not finish the session in one and a half hours. Why did it take so long? Because many of the female readers asked me to kiss them. I have had autograph sessions in many countries, though it is only in Barcelona that female readers asked me for a kiss. Even from this one example, we

Poincare --- pi 1 but sphere

(10) Max determinant problem: Conclusion

Conclusion I and some of my colleagues think about max determinant problem in this article. I don't know there is a better method than combination method. But this algorithm is sufficient to answer the Strang's question, case n=6. In the deep mathematics, people know the max determinant up to 100, at least. The method I show here has nothing compare to them, my method is so primitive. These mathematicians researched on this problem around 1960. I assume they even don't use a computer. I use today's computer, but, I can not have n = 10 case. How they know n = 100? I do like, ``I see the answer is in the one of 10 million, then, I can just write a program to find it.'' I feel having a computer makes me dull. The following is the timing result on my computer (Core2 Duo P8400@2.26GHz, Linux 2.6.35, Windows Vista). Please note, Joachim's algorithm can reduce the n by 1. I measured Joachim's implementation with the time command on Linux, octave/matlab impl

(9) Max determinant problem: Joachim's improvement

Joachim's improvement Recently, I have an activity to support for recent Japanese disaster. I would like to continue this activity. On the other hand, I have not so much time for my Sunday research. Meantime, my colleague Joachim R. found a improved method of the combination solution. It's a nice method and I would like to introduce it here. The basic idea is the following. Determinant doesn't change by elimination, therefore, we can eliminate the first column of {1,-1} matrix. Without loss of generality, we can say a_{1,1} is 1. (Because if it is -1, we can multiply -1 to the first row and switch the sign. In this case, the determinant also altered the sign, but we could always exchange the row to switch back the sign.)  Also, from det(A) = det(A^{T}), we can apply the same operation to the first column. At the end, we could have all 1 row at the first row. Let's write down this procedure. Where, k is the number of -1 in the first row, j is the number of -1 i

(8) Max determinant problem: Algorithm 4, combination

Algorithm 4: combination Row exchange only changes the sign of determinant. Therefore, we don't need permutation, but only combination is necessary. The row of n by n matrix has n elements. The permutation of {-1,1} is 2^6 = 64.  The number of combination of these is _{2^6}C_{6} = 74974368. Because this is just around double of 2^{25}, I expected that this will take only five hours. The implementation of this idea is Program 4. Program 4 function MaxDeterminant = algo_04(matrix_rank) % Introduction to linear algebra Chapter 5. problem 33 % Algorithm 4: combination method % @author Hitoshi   if nargin ~= 1;     error('Usage: la_chapt5_33_comb_row(matrix_rank).')   end   MatrixRank = matrix_rank;   % generate all the row combination (simple permutation)   CombMat = gen_combinatorial_matrix(matrix_rank);   comb_mat_size = size(CombMat);   CombRowCount  = comb_mat_size(1);   curChoise = 1:MatrixRank;   global MaxDet MaxDetMat   MaxDet = 0;   MaxDetMat = [];   tic   whi

(6) Max determinant problem: Algorithm 3.5, another permutation

Algorithm 3.5: another permutation I often go to lunch with my colleagues. At this point, I started to talk about this problem. It seems, Leo, Joachim, and Marc are interested in this story. I thought minimal dot product method is a good idea, so, I was kind of proud of that I found this simple method. My friends also agreed that this might work. But, the result is complete failure as shown in the last article. Marc suggested me a geometrical approach. The max determinant of Hadamard matrix is If you think about this is a geometrical problem, it is simple. The distance from origin to (1,1,1, ..., 1) coordinate in n-dimensional space is (n-dimensional Pythagoras theorem). This is one of the longest distance edge. If these length edges are all perpendicular, then the volume of such object has \sqrt{n}^n. This is exactly the Hadamard's bound. The problem arises when these vectors can not be perpendicular. For example, this Strang's question. The problems in Strang's boo

(6) Max determinant problem: Algorithm 3, min dot product

Algorithm 3: minimal dot product I extended the geometry idea: if a pair of axes has minimal dot product, it could be a max determinant matrix. Minimal dot product means as perpendicular as possible. I implemented this idea in Program 3. Program 3 function algo_03(matrix_rank) % Introduction to linear algebra Chapter 5. problem 33 % Algorithm 3: find minimal dot product vector % @author Hitoshi   if nargin ~= 1;     error('Usage: algor_03(matrix_rank).')   end   global MatrixRank;   MatrixRank = matrix_rank;   global CombMat;   CombMat = gen_combinatorial_matrix(matrix_rank);   % initialize candidate matrix   cand_mat = zeros(matrix_rank, matrix_rank);   cand_mat(1,:) = CombMat(1,:);   comb_mat_size = size(CombMat);   global CombRowCount;   CombRowCount  = comb_mat_size(1);   for i = 2:matrix_rank     min_dotprod_row_idx = get_min_dotprod_row(cand_mat, i);     cand_mat(i,:) = CombMat(min_dotprod_row_idx, :);   end   cand_mat   det(cand_mat) end %%------------------------

(5) Max determinant problem: Algorithm 2, Orthogonality

Algorithm 2: using orthogonality First I looked into the matrix pattern in 2x2 and 4x4. I saw the rows are orthogonal. I thought, ``Aha, because the determinant is volume and when a simplex has the maximal volume when the edge vector length is fixed? Orthogonal vectors!'' This is quite intuitive for me. Therefore, I implemented a method that looked up the orthogonal vectors. This is program 2. Program 2 function algo_02(mat_rank) % Introduction to linear algebra Chapter 5. problem 33 % Algorithm 2: generate Hadamard matrix (each row is orthogonal), but % this only can gives me 1,2,4k matrices % @author Hitoshi   if nargin ~= 1;     error('Usage: algo_02(mat_rank).')   end   % possible element set A_i = {-1, 1}   SetA = [-1 1];   cand_mat = zeros(mat_rank, mat_rank);   cand_mat(1,:) = ones(1, mat_rank);   cand_row = zeros(1, mat_rank);   global MAXDET   global MAXDET_MAT   MAXDET = 0;   MAXDET_MAT = zeros(1, mat_rank * mat_rank);   cur_row_index = 2;   loopdep

(4) Max determinant problem: Algorithm 1, Permutation method

Now, I introduce the problem and explain how I have developed my last answer. My first solution is correct, but, it is practically useless.  In chapter five of Introduction to Linear Algebra, Strang asked us a question, what is max determinant value of 6x6 {-1, 1} matrix? (Problem 33) This is a matlab question, so we can use matlab/octave. My first answer is generate all the combination of {-1,1}. This is Algorithm 1: permutation method. Algorithm 1: permutation method Since the component of matrix is limited to -1 or 1, we can generate all the permutation of 6x6 matrix and compute their determinant, then find the max determinant value. Program 1 shows the implementation. Program 1 function algo_01(mat_rank) % Introduction to linear algebra Chapter 5. problem 33 % Algorithm 1: generate all the combination and test method. % @author Hitoshi if nargin ~= 1;     error('Usage: algo_01(mat_rank)') end % possible element set A_i = {-1, 1} SetA = [-1 1]; cand_mat = zeros(1, ma

(3) Max determinant problem, Appendix

This is just a side talk and you can skip this. It is a detail about relationship between Fredholm equation of the second kind and the max determinant problem. The basic idea is as following. The discrete form of Fredholm equation of the second kind is a matrix form (a linear system). To get the limit of the discrete form, the dimension of matrix n goes to infinity. The solution of linear system is obtained by a variant of Cramer's rule. This needs the determinant. The absolute value of the determinant relates with the system's convergence. Therefore, the max determinant problem was interesting. Fredholm equation of the second kind is as following. Assume this equation as a discrete problem, the range a,b is n-subdivided, then Set λ (b-a)/n = h, the coefficient of this equation becomes following. When we let the subdivision number n to infinity, the dimension of matrix becomes infinite. When we solve this linear system by Cramer's rule, we need determinant. Please

(2) Max determinant problem

I would like to talk about why mathematicians are interested in max determinant problem. This is just my personal theory and I could not find an article that say this directly. So, I warn you that I might be completely wrong. The max determinant problem is mentioned in a context of partial differential equation.  Is a partial differential equation interesting? I safely say, yes. This includes heat and wave problem. We can design buildings, computers, cars, ships, airplanes, ... and so on. There are so many applications of this in our world. Hadamard is one of the mathematicians who contributed the max determinant problem. His one of the interests was partial differential equation. A basic partial differential equation, for instance, a wave equation is like this. This can be re-written as (By the way, if we wrote it as above, an operator d^2/d x^2 looks like to have an eigenvalue λ. Like Mu = -λu. This is a clue of relationship between integral equation and linear algebra.) Fred