Algorithm 3.5: permutation

私の会社では同僚と Lunch に行く．そこではこういう話をすることがある．Leoと Joachim がこの話に興味を持った．minimal dot product 法は私は良いアイデアだと思って得意になって同僚に話をし，同僚も悪いアイデアではないと思ったようだ．私はこれは高速だと思っておおはしゃぎしたが，結果は前回の通り，失敗だった．

Marc は geometry 的なアプローチを示唆した．これは Hadamard matrix を考える時には良い clue になる．Hadamard の上界は次式のようになっている．

これは geometry で考えると簡単である．まず，n 次元の原点から (1,1,1,..., 1) 座標までの距離は，n 次元のピタゴラスの定理から

である．これが全て直交した図形の体積は，そのn 乗であるから，上式が上界を示していることは簡単だ．問題は直交軸を形成できない次元の場合が問題である．例えば Strang の質問がそうである．Strang の本の問題は簡単そうに見えて，常にこういうことを考えて作った問題なのだ．

Joachim は matrix の構造をもっと考えれば組合せを絞れるという話をしていたのだが，minimal dot product 法はそういうことをあまりせずとも候補を絞れるので単純で賢いと思って考えなかったのだが，失敗したために考えることにした．

改良手法として，まったく同じ row を持つものは意味がない．その場合にはdeterminant は 0 になるからどんな determinant でも 0 以外ならば最大値になる候補になる．(0になる理由は，Geometry から考えると簡単である．ある体積を張るようなベクトルの二つが同一になる場合，体積は0である．たとえば，三角形の2つの辺が重なってしまう場合にはその三角形の面積は0になるのと同じ理由で
ある．) row 交換は determinant の符号を変化させることを考慮すると，負の determinant でも 0 でなければただちに正の determinant を求められる．これは最大 determinant が求まれば，2つの row を交換することで，直ちに最小も求まることを意味している．(また Geometry を考えると簡単である．ある2つの辺を入れ替えると，その体積は符号が変化するだけで体積の絶対値は変化しない．)

したがって，row の候補を組合せで生成し，その permutation を考えることにする．これは 2^{36} の候補ではなく，_{2^6}P_{6} を考える方法である．しかし，これはまだ，53981544960 通りある．確かに 2^{36} よりは小さいのだが，ほとんど同じ orderである．計算してみると 27% 程度の改善しかみこめない．

この方法は速度の改善をあまりしないので次の方法に行くことにしよう．

(7) 最大 determinant 問題: Algo 3.5. another perm.