(あるいは，いかにしたら10,000次元の世界を見ることができるか.)
通常，数学では分野毎に最も重要な Fundamental theorem というものがある．Linear algebra では Fundamental theorem of Linear Algebra である．これは 4 つの sub space: Column space, row space, null space, leftnull space, 間の関係を言うものである．しかし，私は大学の授業でこれを習った覚えがない．聞き逃してしまったのだろうか．もし聞き逃したとしたらこれは非常に痛い失敗であった．column space の視点を持たないと高次元のlinear space がとても見えにくい．つまり row space しか知らないと，高次元の解はとてもみつけにくい．私の場合，4次元がもう見えない．しかし，column space の考えを知れば，何万次元だろうが，高次元など平気になる．もしよろしかったら御覧下さい．あるいはもっとお時間のある方はGilbert Strang の Introduction to Linear Algebra を読まれると良いでしょう．
Column space と row space Slides
Conclusion
最大 determinant 問題についてしばらく考えた．combination を用いる方法以上のものはわからないが，n=6 の場合を計算せよという問題には十分答えることができる．ただし，最大 determinant は理論的に研究されており，100程度までの数表ができている．これはここで示した方法ではとうてい太刀打ちできないような，賢い方法である．なまじ計算機があるとそれに頼って頭脳が劣化してしまうのかもしれない．
以下は速度を手元の計算機(Core2 Duo P8400@2.26GHz, Linux 2.6.35)で計測した結果である．Joachim の C++ 実装のものは組合せの計算は n が一つ小さいことを考慮して欲しい．また，Joachimのプログラムは time command,octave/matlab は tic/toc コマンドで計測した．ただし，time command の場合，n<=5 までは user time が 0 なので，あまり意味はない．また，() 内部は推定である．
今回同一のアルゴリズムを octave/matlab と C++ で実装した．Determinant を計算する回数を統一して比較すると，C++ の実装は matlab に比較して 3.7倍，octave に対して 55 倍高速である．この数字をどうみるかは意見が別れると思うが，私は matlab の実装が C++ に比較して 3.7 倍しか時間がかからないというのは結構高速であるという印象を受けた．
Acknowledgements
Thanks to Leo, Joachim, and Marc for the discussion.
最大 determinant 問題についてしばらく考えた．combination を用いる方法以上のものはわからないが，n=6 の場合を計算せよという問題には十分答えることができる．ただし，最大 determinant は理論的に研究されており，100程度までの数表ができている．これはここで示した方法ではとうてい太刀打ちできないような，賢い方法である．なまじ計算機があるとそれに頼って頭脳が劣化してしまうのかもしれない．
以下は速度を手元の計算機(Core2 Duo P8400@2.26GHz, Linux 2.6.35)で計測した結果である．Joachim の C++ 実装のものは組合せの計算は n が一つ小さいことを考慮して欲しい．また，Joachimのプログラムは time command,octave/matlab は tic/toc コマンドで計測した．ただし，time command の場合，n<=5 までは user time が 0 なので，あまり意味はない．また，() 内部は推定である．
今回同一のアルゴリズムを octave/matlab と C++ で実装した．Determinant を計算する回数を統一して比較すると，C++ の実装は matlab に比較して 3.7倍，octave に対して 55 倍高速である．この数字をどうみるかは意見が別れると思うが，私は matlab の実装が C++ に比較して 3.7 倍しか時間がかからないというのは結構高速であるという印象を受けた．
Acknowledgements
Thanks to Leo, Joachim, and Marc for the discussion.
Joachim's improvement
ここのところ，週末には私は日本の最近の災害に関する活動をしている．この活動は，個人的には多少の意味を見いだせるため，できる範囲で続けたいと思っている．ただ，時間がかかるため週末に日曜研究する時間がとれないのが難点である．
そうしている間に同僚の Joachim R. がこの手法を改良する方法をみつけたのでここに紹介しよう．
基本的なアイデアは以下の通りである．Determinant は elimination では変化しないので，{1,-1} matrix の最初のcolumn をelimination してもかまわない．一般性を失なわずに，a_{1,1}は 1であると言える．(なぜなら -1 の場合にはrow に -1 をかけ，符号を反転させることができる．この場合，determinant も(-1) がかかるが，後に row exchange すれば良い．) また，det(A) =det(A^{T}) より，この操作はcolumn にも可能であるから，最初の row を総て1 にすることが可能である．
これを順を追って書いてみよう．
ここで k は最初の row にあった -1 の数であり，j は最初の column にあった-1の数である．n は行列の大きさである．したがって，nxn の行列の場合には，(n-1)x(n-1) の {0,1}行列の最大値を知れば(n)x(n) の {-1,1}行列の最大値がわかる．これは http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html の式(3) α_{n} = 2^{n-1}β_{n-1} の証明である．mathworld はこの証明をしていないのと参考文献が古くて Web でみつからない．この Joachim の方法は簡潔でわかりやすい証明を与えている．
この Joachim の手法を使うと n を1つ減らせるので，劇的な速度向上が得られる．たとえば，n = 7 の場合，128 倍の速度向上が得られる．
これは数学やアルゴリズムがいかに重要かの好例である．128 倍高速な計算機を作るのは簡単ではない．combination の手法と組合せると，最初の方法に比較して10万倍高速になっている．10万倍速い計算機を作るのはとても難しい．数学や計算機の世界では根性という言葉は意味を持たない．賢さのみが意味を持つ．
ここのところ，週末には私は日本の最近の災害に関する活動をしている．この活動は，個人的には多少の意味を見いだせるため，できる範囲で続けたいと思っている．ただ，時間がかかるため週末に日曜研究する時間がとれないのが難点である．
そうしている間に同僚の Joachim R. がこの手法を改良する方法をみつけたのでここに紹介しよう．
基本的なアイデアは以下の通りである．Determinant は elimination では変化しないので，{1,-1} matrix の最初のcolumn をelimination してもかまわない．一般性を失なわずに，a_{1,1}は 1であると言える．(なぜなら -1 の場合にはrow に -1 をかけ，符号を反転させることができる．この場合，determinant も(-1) がかかるが，後に row exchange すれば良い．) また，det(A) =det(A^{T}) より，この操作はcolumn にも可能であるから，最初の row を総て1 にすることが可能である．
これを順を追って書いてみよう．
ここで k は最初の row にあった -1 の数であり，j は最初の column にあった-1の数である．n は行列の大きさである．したがって，nxn の行列の場合には，(n-1)x(n-1) の {0,1}行列の最大値を知れば(n)x(n) の {-1,1}行列の最大値がわかる．これは http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html の式(3) α_{n} = 2^{n-1}β_{n-1} の証明である．mathworld はこの証明をしていないのと参考文献が古くて Web でみつからない．この Joachim の方法は簡潔でわかりやすい証明を与えている．
この Joachim の手法を使うと n を1つ減らせるので，劇的な速度向上が得られる．たとえば，n = 7 の場合，128 倍の速度向上が得られる．
これは数学やアルゴリズムがいかに重要かの好例である．128 倍高速な計算機を作るのは簡単ではない．combination の手法と組合せると，最初の方法に比較して10万倍高速になっている．10万倍速い計算機を作るのはとても難しい．数学や計算機の世界では根性という言葉は意味を持たない．賢さのみが意味を持つ．