## 2011-04-21

### (6) Max determinant problem: Algorithm 3, min dot product

Algorithm 3: minimal dot product

I extended the geometry idea: if a pair of axes has minimal dot product, it could be a max determinant matrix. Minimal dot product means as perpendicular as possible. I implemented this idea in 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 generates a matrix that has relative large determinant value. But, they are not always the largest. For example, this program generates 32 when n = 5. But, the correct answer is 48 when n = 5. I could not proof why this doesn't work, if anybody know it, please let me know.

I needed to continue to seek for a better idea.