Algorithm 4: combination
Row exchange only changes the sign of determinant. Therefore, we don't need permutation, but only combination is necessary. The row of n by n matrix has n elements. The permutation of {-1,1} is 2^6 = 64. The number of combination of these is _{2^6}C_{6} = 74974368. Because this is just around double of 2^{25}, I expected that this will take only five hours. The implementation of this idea is Program 4.
Program 4
I got the idea using combination immediately after the permutation idea, therefore, I wanted to skip the algorithm 3.5. However, I made a mistake and implemented permutation of rows. What a terrible mistake. The difference of permutation method and combination method is 6! cases. This is 720. I estimated 60 days for the computation time of permutation method. But, the combination method is 720 times faster, it took only two hours.
I got the correct result by this program. Actually, there is a nice side effect. I could not find any concrete matrix that has the max determinant from the Web. So, this is one of the 6x6 matrix that has the max determinant value.
The function gen_combinatorial_matrix() is generating permutation of row. I omit the implementation since it's not substance and very easy to implement anyway.
Row exchange only changes the sign of determinant. Therefore, we don't need permutation, but only combination is necessary. The row of n by n matrix has n elements. The permutation of {-1,1} is 2^6 = 64. The number of combination of these is _{2^6}C_{6} = 74974368. Because this is just around double of 2^{25}, I expected that this will take only five hours. The implementation of this idea is 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
I got the idea using combination immediately after the permutation idea, therefore, I wanted to skip the algorithm 3.5. However, I made a mistake and implemented permutation of rows. What a terrible mistake. The difference of permutation method and combination method is 6! cases. This is 720. I estimated 60 days for the computation time of permutation method. But, the combination method is 720 times faster, it took only two hours.
I got the correct result by this program. Actually, there is a nice side effect. I could not find any concrete matrix that has the max determinant from the Web. So, this is one of the 6x6 matrix that has the max determinant value.
The function gen_combinatorial_matrix() is generating permutation of row. I omit the implementation since it's not substance and very easy to implement anyway.
Comments