ビンゴ行列の行列式の最大値(理論編)
前回の記事では、遺伝的アルゴリズムによりビンゴ行列の行列式の最大値を求めようとしましたが、ここでは数学的な観点から最大値を探してみようと思います。
以下、「行列式が最大になるようなビンゴ行列」を「最大ビンゴ行列」と呼ぶことにし、最大便ご行列が具体的に何であるか求める問題を最大ビンゴ行列問題と呼ぶことにします。
定理1. 最大ビンゴ行列の第j列の要素は、0,15j,15j-1,...,15j-4のいずれかである。
証明.
行列式は行列の1つの成分に関して見ると1次式である。最大ビンゴ行列をAとし、その第(i,j)成分をa_ijと書くことにする。
このとき、a_ijが0,15j,15j-1,...,15j-4のどれでもない場合を考えると、
もしAの行列式のa_ijの係数が負であれば、a_ijの値を最小すなわち0にし、
もしAの行列式のa_ijの係数が正であれば、a_ijの値を最大すなわち15j,15j-1,...,15j-4のうち第i列に現れていないものにすることで、
Aの行列式の値を更に大きくできるので、値を変える前のAは最大ビンゴ行列ではなかったことになる。
したがって、最大ビンゴ行列の第i列の要素は、0,15j,15j-1,...,15j-4のいずれかである。
定理2. 最大ビンゴ行列の第1列の要素は、0を4個以上持たない。
第1列が0を5個持たないことは自明なので、0を4個持たないことを証明する。第1列の非零の値の位置で場合分けする。以下、Aを第1列に0を4個持つ正則ビンゴ行列とする。
(i) 第1列の非零の要素が第3行以外にある場合
第3行以外の行を偶数回入れ替えることで、非零の要素を第1行に置くことができ、かつAの行列式を正にできる。
また、\( A = \left( \begin{array}{cc} a_{11} & S \\ O & T \end{array} \right) \)とすると、
\( |A|=a_{11}|T| \)であり、|A|>0より|T|>0であるから、\( a_{11}\neq 15 \)であれば\(a_{11}\neq 15 \)とすることでAの行列式を大きくできる。
また、Tに対し定理1と同様の議論を行うことで、i列目の値が0,15i,15i-1,....,15i-3であることがわかる(2<=i<=5)。
このような条件のもとで行列を全探索すると、以下の行列が最大となる。
Matrix[[15, 0, 0, 0, 0], [0, 30, 0, 0, 73], [0, 0, 0, 60, 75], [0, 0, 45, 0, 74], [0, 29, 44, 59, 0]](行列式は263256750)
この行列式は前回の記事で求めた行列の行列式よりも小さいので、これは最大ビンゴ行列とならない。
(ii) 第1列の非零の要素が第3行にある場合
(i)と同様の方法で全探索すると、以下の行列が最大となる。なお、これは(i)で求めた行列と本質的に同じである。
Matrix[[0, 30, 0, 0, 73], [0, 29, 44, 59, 0], [15, 0, 0, 0, 0], [0, 0, 0, 60, 75], [0, 0, 45, 0, 74]](行列式は263256750)
この行列式は前回の記事で求めた行列の行列式よりも小さいので、これは最大ビンゴ行列とならない。
以上(i)(ii)より、最大ビンゴ行列の第1列の要素は、0を4個以上持たないことが示された。
定理3. 最大ビンゴ行列の各行と各列には、少なくとも1個の0が存在する。
背理法で証明するために、0が存在しないような行または列をもつ最大ビンゴ行列を考え、これをAとする。
Aが0が存在しないような列を持たない場合、Aの転置を改めてAと置き直すことで、Aは0が存在しないような列を持つと仮定できる。このとき、Aの第j列に0が存在しないとする。
Aの行列式はa_1j,a_2j,...,a_5jのそれぞれについての一次式で、かつそれぞれの係数は正であるから(∵定理1の証明の議論と∀i∈[1,5], a_ij>0より)、a_1j,a_2j,...,a_5jのどれをどれだけ増加させてもAの行列式は増加する。
(以下工事中)