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万倍速い計算機を作るのはとても難しい．数学や計算機の世界では根性という言葉は意味を持たない．賢さのみが意味を持つ．

(9) 最大 determinant 問題: Joachim's improvement