Algorithm 3: minimal dot product
私は geometry の手法を押しすすめて各軸が最小の dot product を持つものがいいのではと考えた．それが program 3 である．
Program 3
function algo_03(matrix_rank)
% Introduction to linear algebra Chapter 5. problem 33
% Algorithm 3: find minimal dot product vector
% @author Hitoshi
if nargin ~= 1;
error('Usage: algor_03(matrix_rank).')
end
global MatrixRank;
MatrixRank = matrix_rank;
global CombMat;
CombMat = gen_combinatorial_matrix(matrix_rank);
% initialize candidate matrix
cand_mat = zeros(matrix_rank, matrix_rank);
cand_mat(1,:) = CombMat(1,:);
comb_mat_size = size(CombMat);
global CombRowCount;
CombRowCount = comb_mat_size(1);
for i = 2:matrix_rank
min_dotprod_row_idx = get_min_dotprod_row(cand_mat, i);
cand_mat(i,:) = CombMat(min_dotprod_row_idx, :);
end
cand_mat
det(cand_mat)
end
%%----------------------------------------------------------------------
% get minimal dotproduct row
% \param[in] cand_mat candidate matrix
% \param[in] cur_row_idx current last row index
function min_dp_row_idx = get_min_dotprod_row(cand_mat, cur_row_idx)
global MatrixRank;
global CombMat;
global CombRowCount;
% init dot prod with the large one
min_dotprod = dot(cand_mat(1,:), cand_mat(1,:)) * MatrixRank;
min_dotprod_rowidx = 1;
for i = 2:CombRowCount % 1 has been used
check_row = CombMat(i,:);
% skip the same row if exists
if check_same_row(cand_mat, check_row, cur_row_idx) == 1
continue;
end
% check min dot product row
sum_dotprod = 0;
for j = 1:cur_row_idx
sum_dotprod = sum_dotprod + abs(dot(cand_mat(j,:), check_row));
end
if min_dotprod > sum_dotprod
min_dotprod = sum_dotprod;
min_dotprod_rowidx = i;
end
end
min_dp_row_idx = min_dotprod_rowidx;
end
%%----------------------------------------------------------------------
% check the same row exists
% \param[in] cand_mat candidate matrix
% \param[in] check_row checking row entry
% \param[in] cur_row_idx current row index
% \return 1 when found the row
function ret = check_same_row(cand_mat, check_row, cur_row_idx)
is_found = 0;
% check the same entry in the candidate?
for j = 1:cur_row_idx
if all(check_row == cand_mat(j,:)) == 1
is_found = 1;
break; % the same entry found
end
end
ret = is_found;
end
program 3 はある程度の大きさの determinant を持つ matrix を生成するが，知られている数列の答えと合わない．5 の場合には 32 を答えとして返すが，この場合は48が最大値であり，最小の dot product を選択するという方法では真の最大の determinant を求められない場合がある．(これが何故か証明できる方は御一報下さい．)
そこでもっと賢い方法はないか考えることにした．