2010-05-30

2.5 Problem 7(C) Introduction to Linear Algebra by Gilbert Strang

Linear Algebra, 2.5, Problem 7 (c)

In Gilbert Strang's Introduction to Linear Algebra 4th ed., chapter 2, section 5, Problem 7 (c) is as following.

If A has row 1 + row 2 = row 3, show that A is not invertible: (c) What happens to row 3 in elimination?

The question is ''what happens in elimination?'' Therefore, first I tried the elimination. It turned out it is complicated. I was in Saarbruecken last week. I have no one to meet one afternoon there, so, I compute this on a piece of paper with a pen. I sat in a cafe in Sankt Johanner Markt for two hours for this, but, I had no luck at that day.

Now I had the answer, but, this is a bad answer. This is not a wrong answer, but I would say this is not a good answer.




Row 3 is always (0 0 0).

Actually I used a computational software. Unfortunately, this result doesn't give me a feeling ``I understand something.'' I didn't understand, Why the row 3 becomes all zero, in this way. I could not answer a related question: Is this happens 4 by 4 matrix or n by n matrix? Therefore, I would say ``this answer is not wrong, but not a good one.''

A better answer gives me more insight of this problem. I have one in a cafe in Saarbruecken. This is based on the idea, linearity.

The elimination method eliminates row 3 by the vector that is a linear combination of row 1 and row 2. For a 3 by 3 matrix,

When row 1 and row 2 are independent, they forms a plane. This plane passes through the origin. It is not possible, when two component are 0s and third is only non-zero. For example, imagine any plane go through the origin. If a point on a plane, x = 0, y = 0, z = k, but this plane goes through the origin, then it is only k = 0.

If row 1 and row 2 are not independent, they form a line goes through the origin, or origin itself. The same reason above, it doesn't exist that two components are both 0 and third one is not zero. When row 1 and row 2 are only origin, the linear combination of row 1 and row 2 is still only (0 0 0).

Therefore, row 3 is (0 0 0).

This linear combination understanding is simpler and more powerful. It is not limited to 3 by 3. Also this condition holds row 3 can be any linear combination of row 1 and row 2. If row 3 is any linear combination of of row 1 and row 2, A doesn't have its inverse.  n by n matrix is also the same. This answer is better since we can understand more general cases.

2010-05-29

Skewed Commutative (?) Matrix (6)

A by-talk

I was in Saarbrueecken to perticipate my friend's Polterabend. When I took my breakfast on Satutday, I met an old friend, Tom, totally unexpected. Since he now lives in US. He just visited a week here. I just talked about an article I am going to write (this one), then it turns out that he is also reading Gilbert Strang's Introduction to Linear Algebra. What a coincidence. That reminds me that the end of last year. I was in Yokohama and met an old friend from Germany. The meeting is not so coincident since there was a big event related with my job and he also worked in the area. But again, he was also reading the same book.  Murakami wrote some about Jazz's coincidence in his 'Tokyo Kitansyu (Strange stories in Tokyo)'. It is really such things happens sometimes.


Appendix 1

Pairs of AB=-BA matrix.

Skewed Commutative (?) Matrix (5)

Visualizing AB=-BA
I looked into the results and found out there are many dense matrices. These are not so easy to comprehend for me. For example, I have no intuitive understanding on

Dense matrix example

with a glance.

I am a lazy Sunday researcher, so let's use matlab again. matlab has a eigshow, a great example code for matrix visualization. You can find the source code of that in the matlab installed directory. I read the eigshow code, then wrote a AB=-BA visualizer.

The following Figures are the snapshots of the program. You will find the source code in the Appendix of this follow up blog, so you could try it if you are interested in.

2010-05-28

Skewed Commutative (?) Matrix (4)

Marco's Question
In the conference, I met my old friend, Marco. This conference is the state of the art computer graphics conference, so, the story of 2 by 2 matrix is totally not be interedted in. However, he asked me what I am on, then I answer the matrix story. Then he asked me a question, ``Can we visualize such matrices?'' It is a brilliant question. What is the common property of these matrix? Is that any common geometrical property, for instance?

The geometric property of my first answer, Equation(1) of Skewed Commutative (?) Matrix (1), is 90 degree rotation (A) and flip y direction (B). In Figure AB_BA, these matrices applied to the vector (1,0) which is shown as the red arrow.


Figure AB_BA


As shown in Figure AB_BA, when AB is applied to the vector (1 0)^T, first B reflects Y axis direction, but the vector (1 0)^T has no change since Y component is 0. Then A rotates the vector by 90 degrees. The result is a Y axis + direction vector, (0 1)^T. Instead, BA first rotate the vector with 90 degrees by A, (1 0)^T becomes (0 1)^T, then Y axis reflection makes (0 -1)^T. In the end, these two operation, AB and BA are negation relationship, AB = -BA. This is also one of the good intuitive example of AB != BA (!= means not equal here).  This property of matrix operation is non-commutative. The multiplication of AB is







 Result AB and BA


Therefore, AB = -BA. My question is what the other pairs of matrix means, and, Marco's question is can we visualize them? There are 56 pairs of matrix that satisfy the condition. You can find all the matrix pairs in the Appendix.

2010-05-27

Skewed Commutative (?) Matrix (3)

Norrkoeping

This early of May, I visited to Norrkoeping in Sweden to perticipate a conference. This city is fantastic. Although it is neither a big city nor having a famous sight seeing point, the people living there are just nice.

I arrived at there very late, around 1 am, yet it is planned, so I took a taxi to go to my hostel. The taxi driver found the address, but we could only see a train station, not see the hostel. Then the driver stopped the meter and looked for the hostel. In this case, the driver usually doesn't stop the meter, I was already impressed. Later we know the hostel was there, the 1st floor of the train station was actually the hostel.

We found a small sign, that tells hostel, so I thanked him and he left. But, now the door of the hostel is closed and I found out there is no door opened. I found a sign that it seems the opening time, but it is in Swedish except numbers. If it is the opening time, I need to wait until 5 o'clock in the morning. I've got totally lost.Unfortunately, my handy phone didn't find the network, so didn't work.

Then, one guy was just passing and told me, ``Would you like to get in there?'' I was a bit cautious, but I found no other help. He asked me, ``Do you have a number?'' I first didn't get, but, he meant the number of hostel. I showed the number, then he took his handy phone and call somewhere.

I paid this conference by my own, so I tried to find something reasonable. Most of the hotels that has English web pages were kind of expensive. Fortunately, I have a Swedish friend and he helped me out to find some cheaper place, but these have Swedish web pages only. Later I found out that I should call the hostel when the door is closed. At the end, the kind guy gave me two numbers, one is to open the front door, the other is the number of safe that has my room key.

Everything goes like that in this city. When I bought a hotdoc, I did not have enough coins, one Krone is missing. I gave a note, but the shop keeper just took the coins still one Krone less. In the other shop when I bought two bottles of water, then they recommended a special cheaper combination is now under offer. When I paid the hostel fee, I unconsciously put my credit card into my pocket, but I usually kept it my wallet, so I thought I lost the credit card. The woman in the hostel helped me to search the card. It turned out it is my mistake, she  was glad together. It is really nice people there in Noorkoepping.

2010-05-25

Let's enhance reflection, eigenvalue is off

I worked on image processing a bit, but is this the usual people expecting?

Let's enhance
Reflection...

2010-05-24

Skewed Commutative (?) Matrix (1)

Introduction to Linear Algebra by Gilbert Strang
Chapter 2, Section 4, Problem 22


Abstract

``By trial and error find real nonzero 2 by 2 matrices such that DE = -ED (not allowing DE = 0)'' is a problem 22, Chapter 2, Section 4 in Introduction to Linear Algebra 4th ed. by Gilbert Strang. When I worked on this problem, I got another question. ``How many such matrix pairs are there?'' I computed it and got an answer 56. Then I talk about this with my friend Marco, he asked me another question, ``Can we visualize them?'' Here is my answer of his question.


Linear Algebra, 2.4, Problem 22
There are many interesting questions in the book, Introduction to Linear Algebra 4th ed. by Gilbert Strang. For example, in Chapter 2, Section 4, Problem 22 is

 By trial and error find real nonzero 2 by 2 matrices such that
 A^2 = -I, BC = 0, DE = -ED (not allowing DE = 0).
By trial and error, I found the following answer.

Equation(1)

The book's solution page has a different answer with a comment, ``You can find more examples (p.521).''

Then I thought that How many such matrix pairs were there.

To to continued....

Skewed Commutative (?) Matrix (2)

How many such matrices are there?
I first calculated the constraint and tried to find the matrix pairs that satisfy the constraint. I.e., I compute AB and -BA,


Equation first try

then four equations I got. However, there were so many cases and I had no confidence I did this correct.

My next idea is using matlab/octave. To make the problem simple, I added the following condition, I think it is still enough interesting with this condition.

  The elements of the matrix are {-1,0,1} only.

My choise of algorithm is a simple standard 'generate and test' method, I generate 6561 (= 3^4 x 3^4) pairs of matrix, then test each matrix pair satisfying the condision AB=-BA (not allowing AB=0) or not. In this method, I generate the permulation and not the combination, therefore I counted the same pair twice. (For example, If we do D = B, E = A in Equation(1) from the last blog, AB and DE are different solutions.)

The result is 112, therefore, I found 56 pairs of matrix.

A personal annotations of Veach's thesis (7)

Here is my Japanese translation, part 3/3.

Robust Monte Carlo Methods for Light Transport Simulation
光輸送シミュレーションのためのロバストなモンテカルロ法

著者(Author): Eric Veach
Translated by Lx=d HY

1.1.2 輸送モデルに関する仮定

光輸送アルゴリズムは全ての光の振舞いをシミュレートするのではない.なぜなら,ほとんどの応用でそれは必要でないからである.(脚注: 厳密に言えばそれは可能ですらない.なぜなら全ての物理学が知られているわけではないからである.しかし,光と物体の相互作用は物理学の中でも最もよく研究され,発展しているものの一つである.そして実質的に全ての観測される現象は,かなり高い精度で計算,予測できる.[Feynman 1985] したがって,コンピュータグラフィックスの目的としては我々はこれらの物理法則は,ほぼ完全に理解されていると仮定してよい.) グラフィックスの立場に立つと,物理学における光学の知識を使うことは,写実的な画像を生成する手法として,最も適していると考えられる.どのようなシーンを生成するかに対して,我々はどの光学的効果が重要なのかを判断し,そしてそれをシミュレートできるアルゴリズムを選ぶことになる.

我々の論文においては幾何光学モデルを基礎とする.このモデルでは,光は物体の表面からのみ放射,拡散,吸収される.そして,これらの面間では光は直進すると仮定する.したがって,雲や煙のような participate 物体(吸収・拡散を行う物体)や,あるいは屈折率が連続的に変化する物体(たとえば,熱せられた気体)は考慮しない.我々はまた,波長や量子力学的効果に依存する(たとえば回折や蛍光)光学効果のほとんどを無視する.特に,我々は光線間の相互作用の可能性を排除する.すなわち,光は完全に非干渉であることを仮定する.

通常のレンダリングでは,ここで我々が無視した効果はそれほど重要ではない.幾何光学は我々が日常で目にするものをほとんど全て,適切に高い精度でモデル化する.このため,実質的には,ほとんどのグラフィックスでの光輸送アルゴリズムはここで行なった仮定と同様の仮定を行っている.この章の後ほどで,他の選択肢となる物理モデルの可能性に関して調査することにする(1.5 と 1.6 節参照).

2010-05-10

Solving a maze by image processing (morphological operation).

I found a cool maze solver.

  http://www.mathworks.com/matlabcentral/fileexchange/27175-mazesolution

Usual solver is touch-always-the-right-hand-on-the-wall method, but this uses morphological operators.

I am not so sure, but the solution seems the following.

Assumption: Maze has only one solution path. It is topologically two components (two connected walls).

  1. Detect two wall components by a morphological operation.
  2. Expand two components by a morphological operation.
  3. 'AND' region of these two is the solution way.

It's cool.

2010-05-01

A personal annotations of Veach's thesis (6)

Here is my Japanese translation, part 2/3.

Robust Monte Carlo Methods for Light Transport Simulation
光輸送シミュレーションのためのロバストなモンテカルロ法

著者(Author): Eric Veach
Translated by Lx=d HY

1.1 光輸送問題

コンピュータグラフィクスの分野で光輸送シミュレーションは,現実のシーンと見紛うほどリアルな人工的な世界を作成する人々を助ける道具として利用されている.そのような道具には,物体の形状や表面の散乱属性などの仮想世界の環境の記述が入力されている.さらに,光源についての情報や,視点の情報も与えられている.これらの情報をもとに,光輸送アルゴリズムは現実の物理学に基いて光の振舞いをシミュレーションし,写実的で正確な画像を生成することを試みる.

1.1.1 なぜ光輸送は重要なのか

光輸送アルゴリズムの大きな目標の一つは,写実的な仮想環境モデルを人が効率的に生成することを助けることである.たとえば,現時点で,コンピュータアニメーションではよりリアルな光源をデザインすることに多大な努力が払われている.主な問題は,プロダクションで利用されている(スキャンラインやレイトレーシングなど)のアルゴリズムは通常間接光をシミュレートする能力がないか,限られた能力しかないことである.つまりライトが置かれた時点で通常は間接光が自動的に計算されることはほとんどない.そのかわり,それらの効果は人によって注意深く置かれた見えない光源によって模造されることがしばしばである.もし,我々がロバストな光輸送アルゴリズムによってこれらの間接光を自動で計算することができるなら,シーンのライティングを行う人の仕事はより簡単になる.

光輸送シミュレーションのその他の応用は予測可能なモデリングである.つまり実際に製作する前にこれから作成するものの外見を予測したいという欲求があり,これに応えようというものである.建築や製品デザインの分野ではこのような要求は明らかに必要とされている.これらの応用ではレンダリングの結果は客観的に正確であり,かつ,見た目も良いものであることが重要である.

最後にグラフィックスの分野での光輸送の技術を発展させることは,結局物理学や工学にの発展にも寄与する可能性が高い.1.6節ではこれらの可能性について詳しく議論する.

もしロバストな光輸送アルゴリズムが開発されれば,我々はこれが広く利用されると信じている.より簡単でより強力なアルゴリズムは,最終的にはいくつかの状況で複雑だが,現時点で性能の高いアルゴリズムよりも好まれる.これは一般的なコンピュータソフトウェアの傾向である.つまり,人が状況に応じてパラメータのチューニングを行なってそれによって高速に結果を得るようなアルゴリズムよりも,計算時間は多少かかっても,パラメータのチューニング,つまり人間が複雑な役割を果たさないような単純で強力なアルゴリズムが最終的には好まれるという傾向である.我々は簡単で,正確な光輸送のシュミレーションのもたらす利益は,多少計算コストが高いことは,人間のコストに比較してあまり影響がないと感じている.