DMNA 因数分解(2) - タンタン的思考

因数

自動的に因数分解する方法がだいたい分かった．昨日までは乗数を冗長2進数で表現したときに有意ビットが2桁までの数を対象にして，演算が閉じる（環とか体みたいな）集合を考えていたのだがうまくいかなかった．その原因は写像する（整数化を行う）関数が1対多になってて逆関数が定義できなかった．

ふと，集合理論で真っ当に解けば良いことに気が付く．なんて書くと難しく聞こえるが，要は総当たり．純関数言語で記述すれば，記述自体は簡単なのであっけなく出来た．でも，未知数が増えると計算量，というか記憶領域が膨大になって，落ちる．結局手続き型で記述するしかないのかな．Mathematicaをそこまで使いこなせていないのが原因ではあるんだが．

というわけで，今のところ発見した性能の良さそうな因数分解としては，
$\left(\begin{array}{cc} 1 && \tan(\pi/16) \\ \tan(\pi/16) && 1 \\ \end{array}\right)\propto \left(\begin{array}{cc} 1 && 7 \\ 7 && 1 \\ \end{array}\right) \left(\begin{array}{cc} 15 && 260 \\ 260 && 15 \\ \end{array}\right)$
など．他に，
$\left(\begin{array}{cc} 1 && \tan(\pi/16) \\ \tan(\pi/16) && 1 \\ \end{array}\right)\propto \left(\begin{array}{cc} 1 && 9 \\ 9 && 1 \\ \end{array}\right) \left(\begin{array}{cc} 8 && 257 \\ 257 && 8 \\ \end{array}\right) \left(\begin{array}{cc} 17 && 1 \\ 1 && 17 \\ \end{array}\right)$
なんてのもある．

でも，これらの行列も結局は2^16などで正規化を入れないと計算が破綻してしまう．逆に2^16を上限にうまい分解をすれば確かに計算精度さえも向上させることが可能．そんなこんなで，理論的にこれ以上突き詰めることはなさそう．あとは，基本方針に従って分解していけば良いだけ．

行列を因数分解するいうときの因数とは，冗長2進数のことでした．これがコアのアイディアだな．

行列の性質

ところで1つ疑問が残った．
$\left(\begin{array}{cc} \alpha && \beta \\ \beta && \alpha \\ \end{array}\right) = \left(\begin{array}{cc} a_{11} && a_{12} \\ a_{21} && a_{22} \\ \end{array}\right) \left(\begin{array}{cc} b_{11} && b_{12} \\ b_{21} && b_{22} \\ \end{array}\right)\cdots$
と分解するとき，
$a_{11}=a_{22}, a_{12}=a_{21}, b_{11}=b_{22}, b_{12}=b_{21}, \cdots$
というのは証明できるのだろうか？私の数学力ではちょっと手におえなくて．情けないなぁ．これが証明できれば因数分解に必要な計算量を削減できるんだが．

直感的には正しそうなんだが厳密にそうかと問われると困る．ただ，反例が見つかったわけでもないので（そもそも探してない），とりあえず上記の仮定を置いている．