## 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. 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

Translated by Lx=d HY

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

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

Translated by Lx=d HY

1.1 光輸送問題

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

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

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