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 in the first column. n is the size of the matrix. Therefore, we could know the nxn matrix's max determinant with computing (n-1)x(n-1) {0,1} matrix's max determinant. You can find this rule in http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html, equation (3) α_{n} = 2^{n-1}β_{n-1}. But mathworld did not give us the proof of this equation. This Joachim's method is one of the proof. Since it is simple and comprehensive, I think this might be a standard proof of equation (3).
Again, this Joachim's method can decrease the matrix size by one, we can get enormous speed up. For instance, n = 7 case, we can get 128 times faster.
This is one example that research of mathematics and algorithm is important. It is quite difficult to build a 128 times faster computer. Compare to the first algorithm with the Joachim's improvement, the difference of elapsed time is 100,000. It is quite difficult to build a 100,000 times faster computer. In mathematics or computer science, the word ``guts'' has no meaning, only ``cleverness'' has meaning.
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 in the first column. n is the size of the matrix. Therefore, we could know the nxn matrix's max determinant with computing (n-1)x(n-1) {0,1} matrix's max determinant. You can find this rule in http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html, equation (3) α_{n} = 2^{n-1}β_{n-1}. But mathworld did not give us the proof of this equation. This Joachim's method is one of the proof. Since it is simple and comprehensive, I think this might be a standard proof of equation (3).
Again, this Joachim's method can decrease the matrix size by one, we can get enormous speed up. For instance, n = 7 case, we can get 128 times faster.
This is one example that research of mathematics and algorithm is important. It is quite difficult to build a 128 times faster computer. Compare to the first algorithm with the Joachim's improvement, the difference of elapsed time is 100,000. It is quite difficult to build a 100,000 times faster computer. In mathematics or computer science, the word ``guts'' has no meaning, only ``cleverness'' has meaning.
Comments