行列の次元とランクとカーネルの関係

　前回作った線形写像の可視化ツールのおかげでイメージ力が高まった気がする。歩きながらいろいろな線形写像のイメージを膨らませていたら、ふと昔よく分かっていなかった式が「ああ、そういうことか。」と分かった。

式で書くとこういうやつ。

rank A + nullity A = n.

とか

dim (im T) + dim (ker T) = dim V.

とか。

（以下間違いなどあればご指摘ください。）

まずrank Aが写像先の空間の次元と同じになるということが分かった。

Aの中に線形独立じゃない列ベクトルがあると、写像先のある軸に関する値が別の軸たちの値によって決まってしまう（自由に動けない）ということになる。つまりAのrankが1つ減ると写像先の空間の次元が1つ減るんだなと気づいた。

次はカーネル。行列だとnullityと言うらしい。線形写像において写像先の空間が一個減るということは、先の空間の点に写像される元の点が1個じゃなくなるということを意味している（injectiveじゃなくなる）。

三次元空間で考えると、写像先空間の次元が1つ減る = 写像元の軸（軸って言ってるのは固有ベクトル）2つで写像先が決まるので、ある点に写像される写像元の点の自由度が増える。この例の場合は、直線上の任意の点が同じ1点に写像される。これをイメージすると、nullityの次元は写像でつぶれた次元と同じだなというのがイメージできた。

で結局上の式が確かにそうだなというのが納得できた。

ちょっと話はずれるけど、「rank(A) < nのときは写像がinjectiveじゃなくなる = 逆行列が存在しない = 行列式が0 = 固有値が0になるものがある。」もイメージで掴めた気がする。

injective(※1)じゃないから写像元が特定できない = 逆行列がない。これは当然。

さらにrank(A) < 0のときは、空間がつぶれている = 固有値が0になるような固有ベクトルがあるというのが固有空間をイメージすると分かる。

行列式は写像による体積の膨張率みたいなものなので、固有値が一つでも0なら0。

※1) 固有値0に対応する固有ベクトル成分は全部0につぶれるので、rank(A)のときはinjectiveじゃないし、surjectiveでもない。

線形代数の文章問題を作ってみた

　固有値、固有ベクトルが便利だと実感できるような簡単な文章問題を作ってみた。

個人的なイメージだけど、線形代数のテスト問題って、

• 行列Aの固有値、固有ベクトルを求めよ。
• 行列Aを対角化せよ。
• 行列Aの逆行列を求めよ。

みたいな感じで、「これ計算して何の意味があるの？」「で、それって何が嬉しいわけ？」となるようなものが多い気がするけど、文章問題にすることで日々の生活（？）に応用できるというのが分かっていいんじゃないかなと思う。

1. 天才科学者ガリレオはある微生物について研究していた。微生物は二次元平面上に生息していることが知られており、点(x, y)に存在する微生物は1秒経つと点(8x+y, 4x+5y)に移動することが分かった。
今一匹の微生物が点(1, -2)上にいることが分かった。2秒後にこの微生物はどの点にいるか？

2. ガリレオは点(7, -13)に微生物がいるのを発見した。ふとガリレオは思った。「この微生物は1分前にはどこにいたのだろう？」
1分前にこの微生物がいた点を求めよ。

3. ガリレオはこの微生物が大変危険であることを突き止めた。さらに悪いことにこの微生物の寿命は大変長いことがわかった。彼は微生物を駆除するためのレーザービーム装置を開発した。この装置はレーザーを放射した方向の直線付近にいる微生物をすべて殺すことができる（他の生物には害はない）。
レーザーを放射するためには莫大な資金が必要なため、レーザは一発しか打つことができない。どの方向にレーザーを打つのが効果的か？また、それは何故か？

行列式、トレースと固有値の関係

　行列式(determinant)、行列のトレース(trace)、固有値(eigenvalue)の関係について証明を読んだ。

determinant(A) = Πλ

行列Aの固有値をλ₁, λ₂, .. , λ_nとする。
これらは特性方程式det (A - λI) の根である。
つまり、
det (A - λI) = (λ₁ - λ) (λ₂ - λ) ... (λ_n - λ) である。
上式にλ = 0を代入すると、
det (A) = λ₁ λ_{2 ...} λ_{n =} Πλ   □

tr(A) = Σλ

まず tr(AB) = tr(BA)が成り立つことを示す。
tr (AB) = Σ_iΣ_j Aij Bjiである。
一方、
tr (BA)
= Σ_iΣ_j Bij Aji
= Σ_iΣ_j Aji Bij  (∵スカラー量の積はcommutative)
= ΣjΣi Aji Bij
= Σ_iΣ_j Aij Bji
となるので、tr(AB) = tr(BA).

ここで行列Aのジョルダン標準形をJとすると、
tr(J)
= tr(V^-1AV)
= tr(V^-1VA)  (∵ tr(AV) = tr(VA))
= tr(A)
である。

ジョルダン標準形の主対角要素にはAの固有値が並んでいるため、
tr(A) = Σλ  □

References

[1] Math 215 HW #9 Solutions (University Of Georgia)
[2] The Theorem that the Sum of the Eigenvalues of a Matrix is Equal to its Trace

線形写像を見える化してみた

　一次元につぶれるような写像の固有ベクトルと固有値は幾何学的に求められそうだなと歩きながら頭の中で考えていたら、粒子が平面上をもさもさと移動するイメージが沸いてきて、もしかしたらこれをコンピュータで描画してみたら面白いのではないかと思って作ってみた。

http://kenjih.com/math_image/lineartransform.html

以下パラメータの設定例。

• 0次元につぶれる写像 A11 = 0, A12 = 0, A21 = 0, A22 = 0.
• 1次元につぶれる写像 A11 = 1, A12 = 1, A21 = 1, A22 = 1.
• つぶれない写像 A11 = 1, A12 = 2, A21 = 1, A22 = 3.
• 90度回転する写像 A11=0, A12=-1, A21=1, A22=0.
• 横0.3*縦0.5に縮小する写像 A11=0.3, A12=0, A21=0, A22=0.5.
• 横4*縦2に拡大する写像 A11=4, A12=0, A21=0, A22=2.

もっとわかりやすい表現方法はないだろうか。色をつけるとか？

二項係数の和

包除原理の問題を解いていたら、二項係数ついて面白い性質に出くわしました。

ずばり以下の式です。（有名な式かもしれないですが、習った記憶はありません。）

例として、n = 5のときを考えてみます。 1 - 5 + 10 - 10 + 5 - 1 = 0なので確かに上式が成り立ちます。ついでにn=4のときもやってみます。1 - 4 + 6 - 4 + 1 = 0でやはり成り立ちます。

パスカルの三角形を書くと、一般のnについて確かにそうなってるなというのが分かります。

まずnが奇数のときを考えてみます。nが奇数のときは左辺の項数がn+1で偶数個になります。+の項と-の項に分けて考えると、
+ - + - + - + -
のようになります。ここで、

 

を使うと、+と-の項がいいかんじに打ち消しあって和が0になるのが分かります。

次にnが偶数のときを考えます。このときは、パスカルの三角形において自分の値 = 上の２つの値の和

となっているのを利用します。これを利用すると隣合う項同士が消去しあって和が0になるのが分かります。

二項係数といえば以下の式が有名ですが、今回出会った式もなかなかの美式だなぁと思います。

Fake it 'til you become it

Found an interesting TED speech on Youtube:

http://www.youtube.com/watch?v=Ks-_Mh1QhMc

The video is about "how your body language affects you." It's known that your gestures have great impacts on what other people think about you. But they revealed that unverbal language also play a role in what you think of yourself -- or it shapes yourself --.

I like a couple of sentences that appear in the last part of the video.
1. Don't fake it 'til you make it. Fake it 'til you become it.
2. Tiny tweaks can lead to big changes.

Eleanor Rigby

 The BeatlesのEleanor Rigbyを訳してみました。

Eleanor Rigbyとは人の名前らしいです。意味が分かりにくいところは注釈（一部個人的な解釈が入っています）をつけました。

Ah, look at all the lonely people!

ああ、すべての孤独な人々を見よ！

Ah, look at all the lonely people!

ああ、すべての孤独な人々を見よ！

Eleanor Rigby picks up the rice in the church where a wedding has been

エレナ・リグビーは結婚式が行われた教会でお米を拾う（※1）

Lives in a dream

彼女は夢の中で生きている（※2）

Waits at the window wearing the face that she keeps in a jar by the door

ドアの近くに置いてある化粧品で化粧をして窓で待っている

Who is it for?

誰のために？

All the lonely people

すべての孤独な人々よ

Where do they all come from?

彼らはどこからやってきたのだろう？

All the lonely people

すべての孤独な人々よ

Where do they all belong?

彼らの居場所はどこだろう？

Father McKenzie

マッケンジー牧師は

Writing the words of a sermon that no one will hear

誰も聞きやしない説教の言葉を書いている

No one comes near

誰も近寄らない

Look at him working

彼が働いているのを見てごらん

Darning his socks in the night when there's nobody there

夜誰もいないところで自分の靴下を繕っている

What does he care?

彼には大切にするものがあるのだろうか？

Eleanor Rigby died in the church

エレナ・リグビーは教会で死んだ

And was buried along with her name

そして彼女の名前とともに墓に埋められた

Nobody came

誰もやって来なかった

Father McKenzie wiping the dirt from his hands as he walks from the grave

マッケンジー牧師は手から土を払って墓を後にする(※3)

No one was saved

誰も救われなかった

※1 イギリスでは結婚式でカップルに米を投げるという習慣がある。ここでは彼女が手にすることの出来ない幸せを表している。

※2 現実を受け止められず夢の中で生きている。自分も大切なパートナーを見つけて幸せになりたいと思っているが、実際は孤独な毎日を送っている。

※3 エレナ・リグビーはマッケンジー牧師が働く教会で死んだ。誰もやって来なかったので、マッケンジー牧師が彼女を埋葬した。

Taxman

歌詞が面白かったので訳してみた。The BeatlesのTaxman。



Taxmanっていうのは、イギリス労働党のHarold Wilsonをことを指しているらしいです。彼が整備した95 % supertax  policyに対する怒りを歌にしたようです[1]。

Let me tell you how it will be
このシステムがどうなってるか教えてやるよ

There's one for you, nineteen for me
お前の取り分は1、俺様の取り分は19

Because I'm the taxman, yeah, I'm the taxman
なぜなら、俺様はtaxmanだからさ。そう俺様はtaxmanなんだ。

Should five percent appear too small
5%って少ないって思うだろ？

Be thankful I don't take it all
でも全部取らないんだから感謝しろよ

Because I'm the taxman, yeah I'm the taxman
なぜなら、俺様はtaxmanだからさ。そう俺様はtaxmanなんだ。

If you drive a car, I'll tax the street
車を運転するなら、道路に税金をかけるぜ

If you try to sit, I'll tax your seat
席に座るなら、席に税金をかけるぜ

If you get too cold I'll tax the heat
寒くて暖房を使うときは、熱に税金をかけるぜ

If you take a walk, I'll tax your feet
徒歩で移動するなら、足に税金をかけるぜ

Taxman
taxman!

Yeah, I'm the taxman
そう、俺様はtaxman!

Don't ask me what I want it for
税金を何に使うかって？

If you don't want to pay some more
これ以上払いたくないなら、余計なことは聞くな

Because I'm the taxman, yeah, I'm the taxman
なぜなら俺様はtaxmanだから。そう、俺様はtaxman!

Now my advice for those who die
死んでいくやつらにアドバイスをくれてやるぜ

Declare the pennies on your eyes
目の上に乗せてる小銭もちゃんと申告しろよ

Because I'm the taxman, yeah, I'm the taxman
なぜなら俺様はtaxmanだから。そう、俺様はtaxman!

And you're working for no one but me
おまえらは、俺様のためだけに働いてるんだぜ

[1] http://rock.rapgenius.com/The-beatles-taxman-lyrics#note-798730

LIBSVMを使ってみた

 LIBSVM[1, 2]を使ってみた。

ダウンロード方法は以下参照。
http://www.csie.ntu.edu.tw/~cjlin/libsvm/#download

Javaで使用する方法を説明します。ここでは、データセットirisを使います。
まずirisのデータセット（iris.scale）を以下のサイトからダウンロードします。

http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html#iris

ちなみに上のページにはいろいろなデータセット（LIBSVM用にフォーマット済）が用意されています。

ダウンロードしたiris.scaleを開くと行数が150行あるのが分かります。1行=1データなので、これを適当にtrain dataとtest dataに分けます。今回は120データをtrain dataに、30データをtest dataにします。このとき、ラベルが均等になるように注意してください。ラベルは各行の１番左の値です。
train data用のファイルをiris.train、test data用のファイルをiris.testとします。

まず以下のコマンドで学習を行います。

java -classpath libsvm.jar  svm_train iris.train

学習が完了すると画面にモデル情報が表示されます。また、カレントディレクトリにiris.train.modelというファイルが生成されます。

次にテストデータの識別を行います。

java -classpath libsvm.jar  svm_predict iris.test iris.train.model iris.predict.out

コマンド引数は左から、テストデータファイル、識別に使用するモデル、識別結果出力ファイルです。識別が完了すると画面に識別率が表示されます。またirisi.predict.outに各データの識別結果（ラベル）出力されます。

ちなみに今回の識別率は、96.67%でした。

LIBSVMはソースコードも公開されているので読んでみようかなと思います。マルチクラス識別のところの手法が何を使っているか（One-Against-Oneとか、One-Against-Allとか）とか、二次計画問題をどのように解いてるかとか気になります。

ちなみにリファクタリングされたバージョンもあるようです[3]。ソース読むならこっちの方がいいかもしれません。

参考

[1] http://www.csie.ntu.edu.tw/~cjlin/libsvm/
[2] http://www.youtube.com/watch?v=gePWtNAQcK8
[3] http://dev.davidsoergel.com/trac/jlibsvm/