Algorithm 4: combination

Determinant は row の入れかえでは符号しか変化しない．したがって，順列は必要ではなく，組合せのみが必要である．nxn の matrix の場合，row は n の要素を持つ．これの {-1,1}の順列は 2^6 = 64 である．したがって，この組合せの数は，_{2^6}C_{6} = 74974368 である．これは 2^{25} の倍程度であるから，全ての場合を計算しても5時間程度で済むのではないかと考えた．その実装がprogram 4 である．

Program 4
function MaxDeterminant = algo_04(matrix_rank)
% Introduction to linear algebra Chapter 5. problem 33
% Algorithm 4: combination method
% @author Hitoshi
if nargin ~= 1;
error('Usage: la_chapt5_33_comb_row(matrix_rank).')
end

MatrixRank = matrix_rank;
% generate all the row combination (simple permutation)
CombMat = gen_combinatorial_matrix(matrix_rank);
comb_mat_size = size(CombMat);
CombRowCount = comb_mat_size(1);
curChoise = 1:MatrixRank;

global MaxDet MaxDetMat
MaxDet = 0;
MaxDetMat = [];

tic
while (1)
mat = CombMat(curChoise,:);
d = det(mat);
if d > MaxDet
MaxDet = d;
MaxDetMat = mat;
end

find_idx = 0;
for i = MatrixRank:-1:1
if curChoise(i) < CombRowCount - (MatrixRank - i)
find_idx = i;
break
end
end

if find_idx == 0
break % done
else
start_val = curChoise(find_idx) + 1;
curChoise(:,find_idx:MatrixRank) = start_val:(start_val + MatrixRank - find_idx);
end
end
toc

MaxDet
MaxDeterminant = MaxDetMat;
end

実は combination を使うアイデアは既にあったので，algorithmn 3.5 のpermutation の手法を実装するつもりはなかったのだが，combination のつもりで実装したものが，実は permultation であった．とんでもない間違いをしてしまった．permutation と combination の違いはここでは 6! 通り，つまり，720倍違う．計算すると permutation 法では 60 日ほどかかることがわかったが，720倍高速な方法というのは 2 時間しかかからない．

答えはあっている．実は web では得らなかった副作用として，matrix も得られた．以下が 6x6 の {-1,1} matrixの最大の determinant を持つ matrix の一つである．

gen_combinatorial_matrix()は row の permutation を作るものだが，これは本質ではないし，実装も簡単なので省略する．

(8) 最大 determinant 問題: Algo 4. combination