(8) Max determinant problem: Algorithm 4, combination

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

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.