(4) Max determinant problem: Algorithm 1, Permutation method

Now, I introduce the problem and explain how I have developed my last answer. My first solution is correct, but, it is practically useless.  In chapter five of Introduction to Linear Algebra, Strang asked us a question, what is max determinant value of 6x6 {-1, 1} matrix? (Problem 33) This is a matlab question, so we can use matlab/octave. My first answer is generate all the combination of {-1,1}. This is Algorithm 1: permutation method.

Algorithm 1: permutation method

Since the component of matrix is limited to -1 or 1, we can generate all the permutation of 6x6 matrix and compute their determinant, then find the max determinant value. Program 1 shows the implementation.

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

I just ran this program on Intel Core2 2.26GHz machine's octave. But it doesn't stop after an hour. I switched to 5x5 matrix, it took two hours and j10 minutes. I should have first thought how large is the combination. In 5x5 matrix case, it is 2^{25}, which means, 33554432, 3.3 * 10^{7}.  In 6x6 case, it is $2^\{36\}$, which means 68719476736, 6.8 * 10^{10}. If I run this program on my machine, it took more than 2200 hours, i.e., 92 days, almost three months. This is too much time for just a practice problem. I suspect there is a better way.