L2^k直交表からL2^(k+1)直交表が作られる証明

閉店間際に丸善で購入。

けっこうライトな数学本で面白そう。

==

ソフトウェアテストPRESS#2にある「直交表の拡張（100ページ目）」の手順で表を拡張すると、それもまた直交表となる。


こちらのPDF資料を引用させてもらいました。

それを証明してみようかと。（ソフトウェアテストではなく、すでに趣味ですが）ただし、証明とはいってもブログで証明を書くのはしんどいのでポイントだけ。やり方は帰納法で。

• サイズが8（=2^3）へ拡張すると直交表となる
　これは自明。
• 直交表サイズが2^kへの拡張が正しいと仮定

　つまりはL2^k直交表については直交性が成立していると仮定しておく。
• 上記方法で表を拡張し、サイズが2^(k+1)の表を作成する
• この表が任意の2列に対して直交性をもつことを示す

　任意の2列を選び、左側にある列を列x、右側にある列を列yとする。



1. 列xおよび列yがともにk次因子以下


　k時点での仮定により自明。
2. 列xがk次因子以下、列yが(k+1)次因子


　列yはもともと、k次因子以下の列と左から2^k番目（0と1が交互に現れる列）の列との成分和で表現される。k次因子以下の列は行が2倍に拡張されていて、2^k番目の列は0と1が交互にあわられる性質を持っているため、直交の性質は保存される。（ちょっと端折った）
3. 列xおよび列yがともに(k+1)次因子


　列x、列yともにk次因子以下の列と左から2^k番目（0と1が交互に現れる列）の列との成分和で表現されるので、相殺されて結局はk時点での仮定により成立する。
• したがって、任意のk（k≧3）について成立する

証明中に少し出てくる、「高次因子群同士の交互作用が必ず低次因子群に表れる」という性質は、ソフトウェアテストへの応用という観点でいえば重要かも。