Lx=d: SundayResearch

Conclusion I and some of my colleagues think about max determinant problem in this article. I don't know there is a better method than combination method. But this algorithm is sufficient to answer the Strang's question, case n=6. In the deep mathematics, people know the max determinant up to 100, at least. The method I show here has nothing compare to them, my method is so primitive. These mathematicians researched on this problem around 1960. I assume they even don't use a computer. I use today's computer, but, I can not have n = 10 case. How they know n = 100? I do like, ``I see the answer is in the one of 10 million, then, I can just write a program to find it.'' I feel having a computer makes me dull. The following is the timing result on my computer (Core2 Duo P8400@2.26GHz, Linux 2.6.35, Windows Vista). Please note, Joachim's algorithm can reduce the n by 1. I measured Joachim's implementation with the time command on Linux, octave/matlab impl...

Joachim's improvement Recently, I have an activity to support for recent Japanese disaster. I would like to continue this activity. On the other hand, I have not so much time for my Sunday research. Meantime, my colleague Joachim R. found a improved method of the combination solution. It's a nice method and I would like to introduce it here. The basic idea is the following. Determinant doesn't change by elimination, therefore, we can eliminate the first column of {1,-1} matrix. Without loss of generality, we can say a_{1,1} is 1. (Because if it is -1, we can multiply -1 to the first row and switch the sign. In this case, the determinant also altered the sign, but we could always exchange the row to switch back the sign.)  Also, from det(A) = det(A^{T}), we can apply the same operation to the first column. At the end, we could have all 1 row at the first row. Let's write down this procedure. Where, k is the number of -1 in the first row, j is the number of -1 i...

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 Ma...