2011-12-15

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 found these poems in

  • Akihiro Nozaki, A story of π, Iwanamishoten (1974) pp.77-78.

But this book also refers the followings:

  • Shin Hitotumatu, Essay for numbers, Chuuoukouronsha, (1972) p.109
  • Shigeo Nakano, the road to the modern mathematics, Shinyousya, (1973) p.19
  • Shuuichirou Yoshioka, The thousand and one nights of mathematics, Seinenshobou (1941) p.147, Gakuseisha(1959) p.107


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 independent eigenvectors
  • Algebratic multiplicity (AM): the number of multiplicity of eigenvalues

There is no rigid relationship between them. There is only an inequality relationship GM <= AM.

For example, a 4x4 matrix's AM = 3 (The number of different λs  is 2.), GM is not necessary to be 2.


By the way, this S is a special matrix and called Hadamard matrix. I wrote a blog entry how to compute this matrix.  This matrix is so special, it is symmetric, orthogonal, and only contains 1 and -1.

The identity matrix is also an example of such matrix. The eigenvalues of 4x4 identity matrix is λ = 1,1,1,1 and eigenvectors are
.



I took a day to realize this. But Marc immediately pointed this out.

Though, I still think one λ value corresponds to one eigenvector in general. The number of independent eigenvector is the dimension of null space of A - λ I. The eigenvalue multiplicity is based on this as the form of characteristic function. But, I feel I need to study more to find the deep understanding of this relationship.


Anyway, an interesting thing to me is one eigenvalue can have multiple corresponding eigenvectors.


References:
Gilbert Strang, Introduction to Linear Algebra, 4th Ed.



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. Ax = λ 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 diagonalization using eigenvector. My intuition was wrong.

For one eigenvalue, that has multiplicity, there can be multiple eigenvectors.

I will show the example of this one eigenvalue and multiple eigenventors in next article.

2011-11-03

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 was moved by the speaker's talk as he heard it first time. The speaker said, ``Everyone somehow knows what truly wants to do.''

Billy thought if he tried to find the meaning by this method, this must be almost real for him. This should not be just a concept to him. Billy decided the deadline, the last day of his life.  If he could not find the meaning until the deadline, that day shall be his last day. Billy might be able to find the meaning of his life with this method. But if it took too long for him, it would be no worth for him. Because everyday became a pain for him.

For a first few weeks, this idea didn't give him the meaning. But he can see the world more clear. At least he understand what he don't want to do today. His interest to his life started to regain the meaning a bit. He still could not feel real that today was the last day of his life, but he could feel it will ends soon enough.

But, at the end, he could not find the meaning before his deadline day. Therefore, he has left this world. Although, his last days were a bit better than the days even he could not find the meaning. I suppose that is still a good thing. So it goes.

2011-10-09

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 rational Se-Clugers were agreed to continue to live is no sense, and suicided themselves.

The zoo in Tralfamadore also keeps this species, but when they knew their species were gone, they also suicided as a logical conclusion. Tralfamadore people of couse knew this future, but as usual, they did nothing. But they can travel the time, they just back to the past when they want to meet Se-Clugers.

Who cares intelligent and rational?

2011-09-27

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 definition is kind of difficult for me. The definition said if the and-probability is equal to the multiplication of each probability, they are independent. However, how do you know the probability in general? I think it is hard to know exact probability from an observation. Maybe it's just definition, but, independent events are not so clear for me by this definition.

References

[1] Hisao Tamaki, Introduction to statistics for information science, for application of simulation algorithms. ISBN-13: 978-4781910123 (Japanese)

[2] Malvin H. Kalos and Paula A. Whitlock, Monte Carlo Methods, Volume I: Basics, ISBN-13: 978-0471898399

2011-09-22

Sample variance and Bessel's correction


The blog is about sample variance and Bessel's correction.

Introduction to Sample variance and Bessel's correction
and




2011-08-01

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.

2011-07-15

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.

2011-06-20

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 froh, dass wir die gleichen Geschichten mit Ihnen teilen können.
Es ist eine der Aufgaben eines Schriftstellers zu träumen.
Die wichtigere Aufgabe eines Schriftstellers ist es aber, diese Träume mit anderen Menschen zu teilen.
Man kann ohne den Drang zum Teilen kein Schriftsteller sein.

Ich weiß, dass die Katalonier viel Mühsal in ihrer langen Geschichte erlebt haben.
Es gab raue Zeiten, aber Sie waren stark und haben überlebt, haben Ihre eigene Sprache und Kultur beschützt.
Wir hätten viel zu teilen.

Wenn wir "unrealistische Träumer" werden, sowohl in Japan als auch hier in Katalonien, wenn wir eine gemeinsame Vorstellung unserer Werte etablieren, wäre das nicht großartig?
Es wäre unser Ausgangspunkt für die Wiedergeburt der Menschheit, ein Ausgangspunkt nach den Erlebnissen vieler Naturkatastrophen und nach furchtbarem Terrorismus.
Wir sollten uns nicht fürchten zu träumen.
Wir sollten uns nicht davor fürchten, eine Vision des Ideals zu haben.
Und wir sollten es nicht zulassen, dass uns die Hunde des Unheils namens "Effizienz" und "Bequemlichkeit" fangen.
Wir werden "unrealistische Träumer" sein, stark und zuversichtlich vorwärts strebend.

Dies ist das Ende meiner Rede, allerdings möchte ich sagen, dass ich das volle Preisgeld für die Opfer des Erdbebens und der Atomkatastrophe spenden werde.
Ich danke dem katalanischen Volk und der "Generalitat de Catalunya", die mir diese Gelegenheit gegeben haben.
Und ebenfalls spreche ich als Japaner den kürzlichen Opfern des Bebens von Lorca mein tiefes Beileid aus.




Acknowledgments


Thanks to Daniel S. and Andy K. for working with me on this translation.

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 darauf, dass Atomkraftwerke effiziente Stromerzeuger sind.
Das bedeutet, dass sie profitabel sind.
Zudem bezweifelt die japanische Regierung, besonders nach dem Ölschock, die Stabilität der Ölversorgung.
Die Regierung hat den Bau von Atomkraftwerken zum Regierungsprogramm erhoben.
Die Energieversorger haben Unmengen Geld in Werbung gesteckt, die Medien genötigt und die Illusion atomarer Sicherheit verbreitet.

Eines Tages haben wir die Wahrheit erkannt: 30% der Elektrizität wird in Japan aus Atomkraft gewonnen.
Obwohl das japanische Volk sich dessen nicht bewusst ist, hat die kleine Insel Japan, ein Land mit häufigen Erdbeben, die weltweit drittgrößte Ansammlung von Atomkraftwerken errichtet.

Jetzt ist es einfach eine Tatsache, dass wir Atomkraft nutzen.
Leute, die Angst vor Atomkraft haben, werden mit Drohungen kritisiert wie "Dann haben Sie kein Problem damit, dass wir nicht genug Strom haben?"
"Ist es in Ordnung für Sie, wenn wir im Sommer keine Klimaanlagen benutzen können?"
Menschen, die Atomkraft in Frage stellen, werden als "unrealistische Träumer" abgestempelt.

Das ist die Situation, in der wir uns nun wiedergefunden haben.
Die Atomkraftwerke, die hätten sicher und effizient sein sollen, zeigen uns nun Verwüstung, als ob sie das Tor zur Hölle aufgestoßen hätten.

Atomkraftwerksbefürworter haben immer darauf bestanden, man "solle sich der Realität stellen".
Diese Realität war nicht die Realität, es war nur eine oberflächliche Bequemlichkeit.
Sie haben die Realität durch ihre "Realität" und fehlerhafte Logik ersetzt.

Dies ist eine Verfälschung des Technologiemythos, auf den Japan lange stolz war.
Gleichzeitig ist es die Niederlage der Ethik und Werte der Japaner, die so eine wankelmütige Logik zugelassen haben.

"Bitte ruhet in Frieden, wir werden den Fehler nie wiederholen."

Wir müssen diese Worte wieder in unsere Herzen meißeln.

Dr. Robert Oppenheimer war der Chefentwickler der Atombombe im Zweiten Weltkrieg.
Er war erschüttert, als er von den katastrophalen Szenen erfahren hat, die von den Atombomben verursacht wurden.
Er sagte zu Präsident Truman,

"Herr Präsident, an meinen Händen klebt Blut."

Präsident Truman bot Oppenheimer sein weißes, sauber gefaltetes Taschentuch an und sagte:
"Bitte. Möchten Sie es abwischen?"

Natürlich gibt es kein sauberes Taschentuch, mit dem man all das Blut dieser Welt aufwischen kann.

Wir Japaner sollten unaufhörlich "Nein!" zu Atomkraft rufen.
Das ist meine persönliche Meinung.

Wir hätten all die Technologie, die wir hatten, zusammennehmen sollen, wir hätten die Weisheit, die wir hatten, vereinigen müssen, wir hätten viel Kapital aufwenden müssen, um eine neue Energiequelle als nationale Alternative zu Atomkraft zu entwickeln.
Das hätte unsere Möglichkeit sein können, unserer gemeinsamen Verantwortung für die Opfer von Hiroshima und Nagasaki gerecht zu werden.
Das wäre unsere große Gelegenheit gewesen, die Gelegenheit des japanischen Volkes, wirklich etwas zur Welt beizutragen.
Auf dem Weg zu rasantem Wirtschaftswachstum wurden wir allerdings von einem einfachen Argument, der sogenannten "Effizienz", mitgerissen und sind vom wichtigen Pfad abgekommen.

Der Wiederaufbau zerstörter Häuser und Straßen ist die Aufgabe fachkundiger Menschen.
Aber unsere ruinierte Ethik und Werte wieder herzustellen, das ist die Aufgabe jedes einzelnen von uns.
Es wird eine schlichte, rustikale und geduldige Arbeit sein.
Wie, wenn an einem Frühjahrsmorgen alle Bewohner eines Dorfes auf die Felder gehen, die Erde pflügen und besäen, müssen wir uns zusammenschließen und diese Arbeit gemeinsam tun.

Es sollte einen Teil geben, den wir, die Spezialisten der Worte, die Autoren, zu dieser riesigen kollektiven Aufgabe beitragen können.
Wir müssen die Saat neuer Geschichten ausbringen und ihnen zur Blüte verhelfen.
Es sollten Geschichten sein, an denen wir alle einen Anteil haben können.
Sie sind wie Lieder beim Säen auf dem Feld -- sie werden die Menschen mit ihren Rhythmen bestärken.



Acknowledgments

Thanks to Daniel S. and Andy K. for working with me on this translation.

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 erschüttert.
Obwohl wir Erdbeben kennen, erschreckt uns das Ausmaß der jetzigen Zerstörung.
Wir fühlen uns hilflos.
Wir sorgen uns sogar um die Zukunft unseres Landes.

Aber letztendlich werden wir wieder Mut fassen.
Wir werden uns wieder aufrappeln, da mache ich mir keine großen Sorgen.
Wer können nicht für immer im Schock erstarren.
Wir können die kaputten Häuser wieder aufbauen, wir können die zerstörten Straßen instand setzen.

Aber ich habe angefangen, über die Sache nachzudenken.
Wir haben einen Teil dieses Planeten, dieser Erde, nur geliehen ohne um Erlaubnis zu fragen.
Die Erde hat nie so etwas wie "Bitte wohnt hier" gesagt.
Wir können uns nicht beschweren, wenn die Erde ein bisschen bebt.

Hier und heute möchte ich über etwas reden, das schwer zu reparieren ist, nicht über Gebäude oder Straßen.
Wie sieht es zum Beispiel mit unserer Weltanschauung aus, mit unseren ethischen Grundsätzen und unserer Werter?
Sie sind keine greifbaren Dinge.
Sind sie einmal zerstört, so sind sie nur schwer wieder herzustellen.

Ich rede im Besonderen über die Atomkraftwerke in Fukushima.

Wie Sie sicher wissen, sind drei der sechs von Beben und Tsunami beschädigten Reaktoren nicht repariert worden und verteilen radioaktive Abfälle.
Es gab Kernschmelzen.
Das Erdreich in der Umgebung ist verseucht.
Wahrscheinlich ist stark radioaktiv belastetes Abwasser ins Meer entwichen.
Der Wind verteilt Radiaktivität auf ein noch größeres Gebiet.

Fast 100.000 Menschen müssen die Umgebung des Kraftwerks verlassen.
Felder, Viehzuchten, Fabriken, Einkaufszentren und Häfen sind verlassen.
Haus- und Nutztiere sind herrenlos geworden.
Leute, die früher dort gelebt haben, werden vielleicht nie mehr in ihre Häuser zurückkehren können.
Und der Schaden beschränkt sich nicht auf Japan.
Es tut mir wirklich leid, dass unsere Nachbarstaaten auch betroffen sein könnten.

Wie konnte es zu dieser tragischen Situation kommen?
Der Grund ist offensichtlich.
Die Konstrukteure der Reaktoren haben nicht mit einem so großen Tsunami gerechnet.
Diese Region war bereits von ähnlich großen Tsunamis betroffen, sodass es bereits die Anforderung gab, die Sicherheitskriterien der Reaktoren zu überarbeiten.
Der Energieversorger hat diese Anforderungen aber nie ernst genommen.
Weil die Firma profitorientiert ist, hat sie kein Interesse an riesigen Investitionen in Maßnahmen gegen einen großen Tsunami, der nur alle paar Hundert Jahre auftritt.

Die Regierung sollte die Sicherheit von Atomkraftwerken strikt überwachen, aber es scheint, als hätte sie die Sicherheitskriterien aufgeweicht, um ihre Atomenergiepolitik voranzutreiben.

Ich weiß nicht warum, aber die Japaner sind ein Volk von Menschen, die fast nie wütend werden.
Es ist ihre Stärke, geduldig zu sein, aber sie können kaum starke Emotionen ausdrücken.
Das scheint ein Unterschied zu den Leuten in Barcelona zu sein.
Aber ich glaube, dass diesmal selbst die Japaner ernsthaft wütend werden.

Trotzdem müssen wir uns selbst mit einschließen, weil wir ein so verzerrtes System zugelassen oder toleriert haben.
Die jetzige Situation ist eng mit unserer Moral und unseren Werten verbunden.

Wie Sie wissen, sind wir Japaner das einzige Volk das Atombomben erlebt hat.
Im August 1945 haben US-Bomber Atombomben über Hiroshima und Nagasaki abgeworfen.
Mehr als 200.000 waren sofort tot.
Die meisten Überlebenden starben langsam an den Krankheiten, die die Strahlung der Bomben auslöste.
Wir haben gelernt, wie vernichtend Atombomben sein können und wie Radiaktivität die Welt und ihre Völker zerstört.
Das haben wir aus diesen Opfern gelernt.

Auf dem Mahnmahl für die Atombombenopfer in Hiroshima steht:

"Bitte ruhet in Frieden, wir werden den Fehler nie wiederholen."

Das sind bedeutende Worte.
Sie bedeuten, dass wir gleichzeitig Opfer und Täter sind.

Acknowledgments

Thanks to Daniel S. and Andy K. for working with me on this translation.

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 etwas beschleunigt hat, sodass die Tage fast eine 1,8-millionenstel Sekunde kürzer geworden sind.

Die Zerstörung durch das Erdbeben selbst war riesig, aber der Tsunami, der auf das Beben folgte, hat das Land verwüstet. Die Welle erreichte teilweise 39 Meter Höhe.  39 Meter Höhe bedeutet, dass, wenn es Menschen geschafft haben, sich auf den zehnten Stock eines normalen Hauses zu flüchten, sie trotzdem nicht überlebt haben. Die Menschen am Strand hatten keine Zeit zu fliehen.  Etwa 24.000 Menschen fielen dem Tsunami zum Opfer; 9.000 von ihnen werden noch vermisst. Die meisten von ihnen liegen vielleicht noch im kalten Meer. Wenn ich darüber nachdenke, wenn ich mir vorstelle, ich hätte einer von ihnen sein können, bin ich tief erschüttert. Viele Überlebende haben Familienangehörige und Freunde verloren, ihr Hab und Gut, ihr soziales Umfeld, ihre Lebensgrundlage verloren. Einige Städte und Dörfer wurden komplett weggeschwemmt. Viele Menschen haben einfach alle Hoffnung verloren.

Es scheint mir, dass Japaner zu sein das Zusammenleben mit vielen Naturkatastrophen bedeutet.
Der größte Teil von Japan liegt von Sommer bis Herbst auf dem Weg der Taifune.
Jedes Jahr haben wir gewaltige Schäden und viele Menschen verlieren ihr Leben.
Es gibt viele aktive Vulkane in Japan.
Heute sind 108 Vulkane in Japan aktiv.
Und dann sind da natürlich die Erdbeben.
Der japanische Archipel balanciert unsicher auf den vier tektonischen Platten am Rande des Ostasiatischen Kontinents.
Wir leben sozusagen auf einem Erdbebennest.

Wir können den Weg und die Ankunftszeit eines Taifuns einigermaßen abschätzen, aber Erdbeben können wir nicht vorhersagen.
In einer Sache sind wir uns jedoch sicher: es ist nicht vorbei.
Es wird in der nahen Zukunft ein weiteres schweres Beben geben.
Viele Seismologen erwarten ein Erdbeben der Stärke 8 nahe Tokio innerhalb der nächsten 20 bis 30 Jahre.
Es könnte nächstes Jahr passieren oder morgen Nachmittag.

Dennoch führen allein in Tokio 13 Millionen Menschen wieder ein normales Leben.
Leute fahren immer noch in überfüllten Zügen.
Leute arbeiten immer noch in Hochhäusern.
Ich habe nichts davon gehört, dass die Bevölkerungszahlen von Tokio nach dem Erdbeben zurückgegangen wären.

"Warum?" könnten Sie fragen.
"Warum wohnen so viele Menschen an einem so schrecklichen Ort?
Wie können dort jetzt so viele Menschen normal leben?"

Die japanische Sprache kennt den Begriff des "Mujo".
Alles auf dieser Welt wird früher oder später verschwinden, nichts bleibt wie es ist und alles ändert ständig seine Form.
Es gibt weder ewige Stabilität noch unveränderliche Unsterblichkeit.
Diese Weltanschauung des "Mujo" kommt zwar aus dem Buddhismus, wir erben sie aber aus einem anderen Zusammenhang als der Religion.
Die Idee des "Mujo" ist in die japanische Seele eingebrannt und hat sich von Urzeiten bis heute kaum verändert.

"Alles zerfließt" ist eine Art Weltanschauung der Resignation.
Daraus kann die Idee erwachsen, dass der Mensch der Natur machtlos gegenüber steht.
Aber die Japaner haben Schönheit in dieser wie Resignation wirkenden Anschauung gefunden.

Wenn wir zum Beispiel über Natur reden, genießen wir die Kirschblüte im Frühling, wir genießen die Glühwürmchen im Sommer und das bunte Laub im Herbst.
Wir genießen gemeinsam und ständig.
Wir schätzen es als eine Selbstverständlichkeit.
Die berühmten Sehenswürdigkeiten der Kirschblüte, der Glühwürmchen und des Herbstlaubs sind zu ihrer Saison immer überfüllt.
Es ist schwer, zu diesen Zeiten ein Hotel zu bekommen.

Woran liegt das?





Acknowledgments
Thanks to Daniel S. and Andy K. for working with me on this translation.

2011-06-14

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 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 am deeply proud that the Catalunyan people appreciate my work and have honored me with this prize. We live far away from each other and we speak different languages. Even our cultural foundations are different. But we still have similar problems and we have similar reasons for happiness and sadness -- we are both citizens of the world. That's why many of the stories of Japanese writers are translated into Catalan and people can read them. I am so happy that we can share the same stories with you. Dreaming is one of the jobs of a writer. But the more important job of a writer is to share these dream with other people. One cannot be a writer without feeling the need to share.

I know that the Catalunyan people have had a lot of hardship in their long history. There have been some harsh times, but you were strong and survived, protecting your own language and culture. We should have a lot of things to share.

If we become ``unrealistic dreamers,'' both in Japan and here in Catalunya, and if we establish a common idea of our values, how great it would be. This would be our starting point for the rebirth of humanity, a starting point after experiencing many natural disasters and passing through times of horrible terrorism. We should not fear having a dream.  We should not fear having a vision of the ideal. And we should not allow ourselves to be caught by the dogs of disaster named ``Efficiency'' and ``Convenience''. We will be ``unrealistic dreamers,'' striding forward, strong and confident.

This is the end of my speech, though I would also like to say that I will donate the full prize amount to the victims of the earthquake and of the accidents of the atomic reactors. I thank the people of Catalunya and the Generalitat de Catalunya who gave me these opportunities. And also, as a Japanese person, I express deep condolences to the recent earthquake victims of Lorca.





Supplement by the translator

Japanese transcripts of Murakami's speech can be found on the Web, mainly from the newspaper companies. However, there are some differences between Murakami's actual speech and these newspaper transcripts. (Perhaps the newspapers used an earlier manuscript of the speech.) This translation is based on the video of the speech on YouTube (http://www.youtube.com/watch?v=ZL-W7tX1Z-Y and related videos).


Acknowledgments


Thanks to Andy K. for working with me on this translation.

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



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 an atomic bomb. We Japanese arranged this accident by ourselves: we made a mistake, we ruined our land, and we destroyed our lives.

Why has this happened? Where did our aversion to nuclear power go? We had that feeling for a long time after the war. We consistently looked toward a wealthy and peaceful society. What ruined and destroyed such a goal?

The reason is simple. It is ``効率 (Kouritu).'' ``Efficiency.''

Power companies insist that atomic reactors are efficient systems for generating electricity. That means it's a profitable system. Moreover, the Japanese government doubts the stability of the oil supply, especially after the oil shock. The government promoted building atomic reactors as the national policy. The power companies spent a huge amount of money on advertising, coerced the media, and distributed the illusion of the safety of atomic reactors.

One day, we suddenly realized the true situation: 30 of Japanese electricity is supplied by atomic reactors. Even though the Japanese people were not aware of it, the small island of Japan, a country with frequent earthquakes, had been developing what is now the third-largest installation of atomic reactors in the world.

Now it is simply a fact that we have nuclear power. People who have a fear of atomic reactors are criticized with threats like ``Then, are you fine even we don't have enough electricity?'' ``Are you fine if you cannot use air-conditioning in the summer?'' A person who questions nuclear power plans is labeled as ``an unrealistic dreamer.''

This is now the situation we found ourselves in. The atomic reactors that should be safe and efficient are now showing us devastation as if they opened the lid of hell.

The promoters of atomic reactors always insisted ``look at the reality.'' That reality was not the reality, it was just a superficial convenience. They replaced reality with their ``reality'' and flawed logic.

This is a corruption of the technology myth that Japan has been proud of for a long time. And simultaneously, this is the defeat of the ethics and standard of the Japanese people who allowed such a ``changeling of logic.''

``Please rest in peace, since we will never repeat the mistake.''

We need to carve these words in our hearts again.

Dr. Robert Oppenheimer was the leader of the development of the atomic bomb during the World War II. He was shocked when he found out about the disastrous scenes that had been created by the atomic bombs. He said to President Truman,

``Mr. President, I have blood on my hands.''

President Truman offered his white, well-folded pocket handkerchief to Oppenheimer, saying, ``Here. Would you like to wipe them?''

Needless to say, there is no clean handkerchief that can wipe up such an amount of blood in this world.

We Japanese should continuously shout ``No!'' to nuclear. This is my personal opinion.

We should have gathered all the technology we had, we should have combined all the wisdom we had, we should have invested a large amount of social capital, all to develop a new energy source that can replace the atomic reactors at the national level. That could be our way to honor our collective responsibility to the victims who died at Hiroshima and Nagasaki. That would be the big opportunity for us, the Japanese people, to really contribute to the world. However, on the way to the rapid development of our economy, we were swept along by an easy criterion, so-called ``Efficiency,'' and we lost the important path.

To rebuild the destroyed buildings and roads is the work of specialized people. But to try to reconstruct our ruined ethics and standards, that is the work of all of us. It will be a simple, rustic, and patient work. Like a fine spring morning, when all the people from a village go to the fields, tilling the soil and seeding it, we must all join and cooperate in this work.

For such huge collective work, there should be a part of that we, the professionals of words, the writers, can positively contribute. We should combine new ethics and standards with new words. We need to plant the seeds of new stories and help them bloom. They should be the stories we all can share. They are like the songs in the field for sowing -- they will encourage the people with their rhythms.



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



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 the prime time of beauty passing and vanishing.

I don't know if natural disasters have affected that Japanese mentality. But we accepted the sequence of natural disasters with a feeling of ``so it goes.'' We survive by overcoming all this damage as a collective. But these kinds of experiences might affect our aesthetic sense.

Almost all Japanese are shocked by this huge earthquake. Even though we know about earthquakes, we recoil at the scale of the damage of this one. We feel helpless. We even fear for the future of the country.

But at the end, we will reconstruct our spirit. We will stand up again and recover. I am not so worried about this. We could not sink into the shock forever. We can rebuild the broken houses, we can repair the destroyed roads.

But I started to think about it. We just rent a part of this planet, Earth, without asking any permission. The Earth never said anything to us like, ``Please live here.'' We cannot complain to anyone when the Earth shake a bit.

Here today, I would like to talk about something that is difficult to repair, not about buildings or roads. For example, what about our view of the world? Our ethical standards and our morals? They are not tangible objects. Once they are broken, it is hard to reconstruct them.

I am talking about, more specifically, the atomic reactors in Fukushima.

As you all may know, three reactors out of six damaged by the earthquake and tsunami have not been fixed and are spreading radioactive waste.  There were meltdowns. The surrounding soil is polluted. Probably waste water with high radioactive density escaped into the sea. The wind also spread the radioactivity to a wider area.

Almost 100,000 people must leave the area around the atomic reactors.  Fields, stock farms, factories, shopping malls, and harbors are abandoned and nobody is there. Pets and domestic animals are also abandoned. The people who once lived there might not be able to come back to their homes again. However, the damage is not only limited to Japan. I am really sorry that it might affect our neighbor countries, too.

Why has this tragic situation happened? The reason is obvious. The designers of the reactors did not take into account this kind of large tsunami. Tsunamis of similar scale have struck this region before, so there already had been a request to revise the safety criterion of the reactors. But the power company never took the request seriously.  Because they are a commercial company, they do not welcome the idea of investing a huge amount of money for a large tsunami that may only come once in a several hundred years.

The government should strictly manage the safety criteria of atomic reactors, but it seems as if they relaxed these safety criteria to promote their atomic power policy.

I don't know why, but the Japanese are a people who hardly ever get angry. They are good at being patient, but they are not good at expressing strong emotions. This seems to be different than the people of Barcelona. But this time, I believe even the Japanese will become seriously angry.

However, we must at the same time implicate ourselves, since we allowed or conspired to produce such a distorted structure. This situation is deeply related to our morality and our standards.

As you know, we Japanese are the only people in history who have experienced atomic bombs. In August, 1945, U.S. bombers dropped atomic bombs on the cities Hiroshima and Nagasaki. More than 200,000 people were killed instantly. Most of the survivors had a slow death, suffering from illnesses caused by the atomic bomb's radiation. We learned how destructive atomic bombs can be and how radioactivity can damage the world and its people. We learned this based on these victims.

The memorial for the victims of the atomic bomb in Hiroshima has the following words on it:

``Please rest in peace, since we will never repeat the mistake.''

These are great words. They mean that we are simultaneously the victims as well as the assailant.




2011-06-13

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



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 know how great the city of Barcelona is. I am very happy that I can come back to this beautiful and culturally rich city that has such a long history.

Unfortunately, I cannot talk about the kissing story today. I should talk about a little more serious topic.

As you may know, on March 11th, at 14:46, there was a large earthquake in the Tohoku area of Japan. The earthquake was so powerful that the revolution speed of the earth became a bit faster, making the day almost 1.8-millionths of a second shorter.

The damage of the earthquake itself was huge, but the tsunami after the earthquake also devastated the land. The tsunami reached 39 meters in height at some places. Thirty-nine meters in height means that if someone could run up to the tenth floor of a normal build, they still could not survive. People near the shore had no time to run away. Around 24,000 people were  Around 24,000 people were victims and out of those 9,000 are still missing. Most of them might still be under the cold sea. When I think about it, when I imagine that I could have been one of them, I am deeply distressed. Even many survivors lost their family and friends, lost their home and property, lost their community, lost their basis of living. Some of the cities or villages were completely swept away. The hope in many people lives is simply gone.

It seems to me that being Japanese means living together with many natural disasters. Most parts of Japan are in the paths of typhoons from summer to autumn. Every year we have huge damages; we always lose many lives. There are many active volcanoes all over Japan. There are 108 active volcanoes in Japan today. And of course, earthquakes. The Japanese archipelago sits precariously on the four large plates at the edge of the east Asian continent. We are, so to speak, living in a nest of earthquakes.

We can estimate the path and arrival time of a typhoon to some extent, but we cannot predict when an earthquake will come. But we are sure of one thing: this is not the end. There will be another large earthquake in the near future. Many seismologists expect an earthquake of magnitude 8 near Tokyo in the next 20 to 30 years. It might be the next year, or tomorrow afternoon.

Nevertheless, all 13 million people just in the city of Tokyo, now have a normal life again. People still commute by crowded trains. People still work in skyscrapers. I never heard anyone say that the population of Tokyo decreased after the earthquake.

"Why?" you may ask us. "Why do so many people live in such a horrible place? How can so many people have a normal life there now?"

Japanese has a word: ``無常 (mujo)''. Everything born into this world will vanish sooner or later, never staying in one state, and is constantly changing its form. There is neither eternal stability nor unchanging immortality. Although this world view of ``mujo'' comes from Buddhism, we inherited it in a different context than from a religion. The idea of ``mujo'' is burned into the Japanese mind and has almost always been the same, from ancient times to today.

``Everything is just gone'' is the kind of world view in which you just give up. This can become the idea that ``a human being is powerless against nature.'' But the Japanese have found a positive way of seeing beauty in a view that seems like giving up.

When we talk about the nature, for instance, we enjoy cherry blossoms in the spring, we enjoy fireflies in the summer, and we enjoy colored leaves in the fall. We do it collectively and habitually. We appreciate it as a self-evident thing to do. The famous sights of the cherry blossoms, the fireflies, and the colored leaves are all crowded during their seasons. It is difficult to book hotels during those seasons.

Why is that?







2011-05-24

Poincare --- pi 1 but sphere

2011-05-03

(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 implementation with tic/toc command. $n<=5$ case, the elapsed time is too small and user time is 0. The ``()'' shows an estimated value.


This time, we implemented the same algorithm with octave, matlab, and C++. If we normalized the result with the number of the determinant computation, C++ implementation is 3.7 times faster than matlab implementation, 55 times faster then octave implementation. How you interpret this number is depends on your point of view. But I am impressed that the matlab implementation is only 3.7 times slower than C++.

Acknowledgements

Thanks to Leo, Joachim, and Marc for the discussion.

(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 in the first column. n is the size of the matrix. Therefore, we could know the nxn matrix's max determinant with computing (n-1)x(n-1) {0,1} matrix's max determinant.  You can find this rule in http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html, equation (3) α_{n} = 2^{n-1}β_{n-1}. But mathworld did not give us the proof of this equation. This Joachim's method is one of the proof. Since it is simple and comprehensive, I think this might be a standard proof of equation (3).

Again, this Joachim's method can decrease the matrix size by one, we can get enormous speed up. For instance, n = 7 case, we can get 128 times faster.

This is one example that research of mathematics and algorithm is important. It is quite difficult to build a 128 times faster computer. Compare to the first algorithm with the Joachim's improvement, the difference of elapsed time is 100,000. It is quite difficult to build a 100,000 times faster computer. In mathematics or computer science, the word ``guts'' has no meaning, only ``cleverness'' has meaning.

2011-05-02

(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
  while (1)
      mat = CombMat(curChoise,:);
      d = det(mat);
      if d > MaxDet
          MaxDet = d;
          MaxDetMat = mat;
      end

      find_idx = 0;
      for i = MatrixRank:-1:1
          if curChoise(i) < CombRowCount - (MatrixRank - i)
              find_idx = i;
              break
          end
      end

      if find_idx == 0
          break                         % done
      else
          start_val = curChoise(find_idx) + 1;
          curChoise(:,find_idx:MatrixRank) = start_val:(start_val + MatrixRank - find_idx);
      end
  end
  toc

  MaxDet
  MaxDeterminant = MaxDetMat;
end

I got the idea using combination immediately after the permutation idea, therefore, I wanted to skip the algorithm 3.5. However, I made a mistake and implemented permutation of rows. What a terrible mistake. The difference of permutation method and combination method is 6! cases. This is 720. I estimated 60 days for the computation time of permutation method. But, the combination method is 720 times faster, it took only two hours.

I got the correct result by this program. Actually, there is a nice side effect. I could not find any concrete matrix that has the max determinant from the Web. So, this is one of the 6x6 matrix that has the max determinant value.



The function gen_combinatorial_matrix() is generating permutation of row. I omit the implementation since it's not substance and very easy to implement anyway.

2011-04-28

(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 book are always like this. It seems simple problems, but, they are deep.

Joachim also suggested me that exploiting the matrix structure. But when he told me that, I thought minimal dot product is the answer. Therefore, I stupidly disregarded it. But my approach was completely failed, I needed to think about that.

First of all, if the matrix has the same row, the determinant is always zero. (Think about geometry, two axes are the same, then, no volume. Like two edges of a triangle are the same, the triangle is degenerated.) This we can omit it because any determinant value if exists, the max determinant is always more than zero. Even we have a minus value, just exchange two rows, then you got a plus determinant. (This means that if I have the max determinant, then I immediately have the min determinant by exchanging any two rows. Also think about geometry, flip two axes changes the direction of the volume, means the sign is changed.)

Based on this observation, we have the following algorithm: generate all the row candidate, then permute the rows. This narrows down 2^{36} candidates to _{2^6}P_{6} candidates in n = 6 case. But this is 53981544960 cases. This is less than 2^{36}, but the almost the same order.

This algorithm can only improve 27% of the time. It is not so much gain. Let's see the next idea.

2011-04-21

(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
%%----------------------------------------------------------------------
% get minimal dotproduct row
% \param[in] cand_mat    candidate matrix
% \param[in] cur_row_idx current last row index
function min_dp_row_idx = get_min_dotprod_row(cand_mat, cur_row_idx)
  global MatrixRank;
  global CombMat;
  global CombRowCount;
  % init dot prod with the large one
  min_dotprod = dot(cand_mat(1,:), cand_mat(1,:)) * MatrixRank;
  min_dotprod_rowidx = 1;

  for i = 2:CombRowCount                % 1 has been used
    check_row = CombMat(i,:);
    % skip the same row if exists
    if check_same_row(cand_mat, check_row, cur_row_idx) == 1
      continue;
    end
    % check min dot product row
    sum_dotprod = 0;
    for j = 1:cur_row_idx
      sum_dotprod = sum_dotprod + abs(dot(cand_mat(j,:), check_row));
    end
    if min_dotprod > sum_dotprod
      min_dotprod = sum_dotprod;
      min_dotprod_rowidx = i;
    end
  end
  min_dp_row_idx = min_dotprod_rowidx;
end
%%----------------------------------------------------------------------
% check the same row exists
% \param[in] cand_mat  candidate matrix
% \param[in] check_row checking row entry
% \param[in] cur_row_idx current row index
% \return 1 when found the row
function ret = check_same_row(cand_mat, check_row, cur_row_idx)
  is_found = 0;
  % check the same entry in the candidate?
  for j = 1:cur_row_idx
    if all(check_row == cand_mat(j,:)) == 1
      is_found = 1;
      break;                       % the same entry found
    end
  end
  ret = is_found;
end


Program 3 generates a matrix that has relative large determinant value. But, they are not always the largest. For example, this program generates 32 when n = 5. But, the correct answer is 48 when n = 5. I could not proof why this doesn't work, if anybody know it, please let me know.

I needed to continue to seek for a better idea.

2011-04-20

(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;
  loopdepth     = 1;
  gen_comb_set(SetA, cand_mat, cand_row, mat_rank, loopdepth, cur_row_index);

  MAXDET_MAT
  fprintf(1, 'max detderminant = %d.\n', MAXDET);
end

%%----------------------------------------------------------------------
% Looking for the orthogonal rows and compute the determinant.
% \param SetA      element candidate set
% \param cand_mat  current candidate matrix
% \param cand_row  current candidate row
% \param mat_rank  rank of matrix (not exactly the rank, size of n)
% \param loopdepth parameter to simulate for-loop depth by recursion.
% \param cur_row   current row index to look for
function gen_comb_set(SetA, cand_mat, cand_row, mat_rank, loopdepth, cur_row)

  global MAXDET;
  global MAXDET_MAT;

  num_set  = mat_rank;
  num_cand = size(SetA);
  szSetA   = size(SetA);

  % This should be assert(sum(szSetA == [1 2]) == 2)
  if sum(szSetA == [1 2]) ~= 2
    error('Not assumed set candidate matrix (should be 1x2)')
  end

  if cur_row > mat_rank;
    % cand_mat;
    det_a = det(cand_mat);
    if det_a > MAXDET
      MAXDET = det_a;
      MAXDET_MAT = cand_mat;
    end

  elseif loopdepth > num_set
    if check_orthogonal_row(cand_mat, cand_row, cur_row) == 1
      cand_mat(cur_row, :) = cand_row;
      cand_row = zeros(1, mat_rank);
      cur_row  = cur_row + 1;
      gen_comb_set(SetA, cand_mat, cand_row, mat_rank, 1, cur_row);
    end
  else
    % raw is not yet ready, generate it.
    for j = 1:szSetA(2)
      cand_row(loopdepth) = SetA(j);
      gen_comb_set(SetA, cand_mat, cand_row, mat_rank, loopdepth + ...
                   1, cur_row);
    end
  end
end


%%----------------------------------------------------------------------
% check the rows are orthogonal with rows < cur_row
% \param cand_mat  current candidate matrix
% \param cand_row  current candidate row
% \param cur_row   current row index to look for the orthogonal
function ret_is_all_orthogonal = check_orthogonal_row(cand_mat, cand_row, cur_row)

  is_all_orthogonal = 1;
  for i = 1:(cur_row - 1)
    if dot(cand_mat(i,:), cand_row) ~= 0
      is_all_orthogonal = 0;
      break
    end
  end

  ret_is_all_orthogonal = is_all_orthogonal;
end

But, this program gives me the max determinant value is zero when 3x3, 5x5, and 6x6 matrix. This is strange. For instance, I can easily find a non zero determinant matrix, for instance, [1 1 1; 1 -1 -1 ; 1 1 -1] for 3x3. The determinant is 4. Also I realized I can not make a orthogonal rows in 3x3 case as the following.

When I think about the geometry, it is also easy to see it is not possible. Figure 1 shows we can not generates orthogonal vectors in 3D case when the coordinates value are only allowed {-1, 1}.
Figure 1: 3D, can not make orthogonal vectors by using {-1,1} coordinates
Figure 2 shows that this method works in 2D case. There are cases that we could make orthogonal vectors even the coordinate values are limited. Figure 2 also shows that the volume (= area, in 2D) that represents the determinant. This is (√2)^2 = 2, and the max determinant of 2x2 matrix is also 2.
Figure 2: Orthogonal vectors by using {-1,1} coordinates in 2D case.
This method can be applied to only 1,2,4n (n >=1) cases. At this point, I found these kind of matrices are called Hadamard's matrix. This problem is called Hadamard's Maximum Determinant Problem. On the Web, there is even the number (max determinant value) for 6x6 case. I am surprised that a lot of cases are known. In the case of 1,2,4n, there is a construction method to generate a Hadamard matrix. The number 1,2,4n is called Hadamard number.

Moreover, matlab/octave has function hadamard(), this generates a Hadamard matrix.

But, I didn't know how to compute the max determinant value of non-Hadamard number matrix.  According to http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html, the max determinant value sequence of Hadamard matrix is known in 1962. There should be a clever method.

2011-04-19

(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, mat_rank * mat_rank);

global MAXDET
global MAXDET_MAT

% We know det I = 1, therefore, it is a good initial value.
MAXDET = 1;
MAXDET_MAT = zeros(1, mat_rank * mat_rank);

gen_comb_set(SetA, cand_mat, mat_rank, 1);

MAXDET_MAT
fprintf(1, 'max detderminant = %d.\n', MAXDET);
end

%%----------------------------------------------------------------------
% Execute depth num_set loop by recursion to generate matrix candidates.
%
% \param SetA      element candidate set
% \param cand_mat  current candidates
% \param mat_rank  rank of matrix (not exactly the rank, size of n)
% \param loopdepth parameter to simulate for-loop depth by recursion.
function gen_comb_set(SetA, cand_mat, mat_rank, loopdepth)

global MAXDET;
global MAXDET_MAT;

num_set  = mat_rank * mat_rank;
num_cand = size(SetA);
szSetA   = size(SetA);

% This should be assert(sum(szSetA == [1 2]) == 2)
if sum(szSetA == [1 2]) ~= 2
    error('Not assumed set candidate matrix (should be 1x2)')
end

if loopdepth > num_set
    MA = reshape(cand_mat, mat_rank, mat_rank);
    det_a = det(MA);
    if det_a > MAXDET
        MAXDET = det_a;
        MAXDET_MAT = MA;
    end
else
   for j = 1:szSetA(2)
       cand_mat(loopdepth) = SetA(j);
       gen_comb_set(SetA, cand_mat, mat_rank, loopdepth + 1);
   end
end
end

I just ran this program on Intel Core2 2.26GHz machine's octave. But it doesn't stop after an hour. I switched to 5x5 matrix, it took two hours and j10 minutes. I should have first thought how large is the combination. In 5x5 matrix case, it is 2^{25}, which means, 33554432, 3.3 * 10^{7}.  In 6x6 case, it is 2^{36}, which means 68719476736, 6.8 * 10^{10}. If I run this program on my machine, it took more than 2200 hours, i.e., 92 days, almost three months. This is too much time for just a practice problem. I suspect there is a better way.

2011-04-18

(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 note that Fredholm didn't use Cramer's rule directory. We need a bit more details (Fredholm minor, Fredholm determinant), however, I just want to know what was the motivation of the max determinant problem. (Also I don't understand whole the Fredholm equation discussion.)

(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.)

Fredholm wrote this kind of integral equation in a finite sum form. This is a matrix form. He had an idea to solve this equation by taking the limit of it, e.g., the dimension of matrix goes to infinite.

If we can write an integral equation in his form, each finite sum equation can be solved by solving linear equations. At that time, people solved the linear equations by Cramer's rule. Cramer's rule has 1/det(A) form. If a matrix A's size becomes larger, the solution can converge or not is depends on the (absolute) max determinant value, whether it is less than 1 or not. I imagine that this is the reason of mathematicians are interested in the max determinant problem. Though, I could not find a direct article about the motivation of why they are interested in the max determinant problem.

(Note: I explained only a little that how an integral equation has a matrix form. Because this is quite detail, I will add appendix in case one is interested in this.)

Although Fredholm didn't use Cramer's rule directly, the proof of convergence needs maximal value of determinant (see. 30 lectures of Eigenproblem, Shiga Kouji, p.121. (in Japanese)).

Hilbert removed the determinant from this problem and established eigenvalue based solution --- Hilbert space. He climbed up the view one level. I think determinant is still an important subject, though, eigenanalysis is much interesting. This is also just my impression, but, when Hilbert established the Hilbert space, people's interest moved to eigenvalues from the determinant. I just imagine this.