では問題を示し，どうやって解いたかについて具体的に順を追って説明していく．まずは正しいが，実用的でない方法から説明していく．
Introduction to Linear Algebra の第5章の問題33で，Gilbert strang は{-1,1}のみを使った 6x6 の matrix の deterinant の最大値を matlab を使って計算してみることを求めている．私が最初に考えたのは単純に全ての組合せを使うものであった．それが Algorithm 1: permutation 法である．
Algorithm 1: permutation method
Matrix の要素は -1 と 1 に限られているのであるから，全ての順列を生成してその determinant を計算し，最大値を求めることができる．それが Program 1である．
ところで Amoeba ではプログラムを整形する方法がわからないので，
http://shitohichiumaya.blogspot.com/2011/04/4-max-determinant-problem-algorithm-1.html
を参照して欲しい．
Program 1
function algo_01(mat_rank)
% Introduction to linear algebra Chapter 5. problem 33
% Algorithm 1: generate all the combination and test method.
% @author Hitoshi
if nargin ~= 1;
error('Usage: algo_01(mat_rank)')
end
% possible element set A_i = {-1, 1}
SetA = [-1 1];
cand_mat = zeros(1, mat_rank * mat_rank);
global MAXDET
global MAXDET_MAT
% We know det I = 1, therefore, it is a good initial value.
MAXDET = 1;
MAXDET_MAT = zeros(1, mat_rank * mat_rank);
gen_comb_set(SetA, cand_mat, mat_rank, 1);
MAXDET_MAT
fprintf(1, 'max detderminant = %d.\n', MAXDET);
end
%%----------------------------------------------------------------------
% Execute depth num_set loop by recursion to generate matrix candidates.
%
% \param SetA element candidate set
% \param cand_mat current candidates
% \param mat_rank rank of matrix (not exactly the rank, size of n)
% \param loopdepth parameter to simulate for-loop depth by recursion.
function gen_comb_set(SetA, cand_mat, mat_rank, loopdepth)
global MAXDET;
global MAXDET_MAT;
num_set = mat_rank * mat_rank;
num_cand = size(SetA);
szSetA = size(SetA);
% This should be assert(sum(szSetA == [1 2]) == 2)
if sum(szSetA == [1 2]) ~= 2
error('Not assumed set candidate matrix (should be 1x2)')
end
if loopdepth > num_set
MA = reshape(cand_mat, mat_rank, mat_rank);
det_a = det(MA);
if det_a > MAXDET
MAXDET = det_a;
MAXDET_MAT = MA;
end
else
for j = 1:szSetA(2)
cand_mat(loopdepth) = SetA(j);
gen_comb_set(SetA, cand_mat, mat_rank, loopdepth + 1);
end
end
end
このプログラムを Intel Core2 2.26 GHz, octave で走らせてみたら1時間たっても終わらない．そこで 5x5 の場合を計算してみたら，2時間10分ほどかかった．まず最初に考えるべきだったが，いくつの場合を試すのか考えてみると，5x5のmatrix では 2^{25} 通りあるので， 33554432, 3.3 * 10^{7} である．6x6の場合は 2^{36} 通りあるので， 68719476736, 6.8 * 10^{10} である．順当に行けば 2200 時間ほどあれば解ける，つまり 92 日，3ヶ月あればよいのだが，それが練習問題になっているというのはどうもおかしい．もっと賢い方法があるようである．