Algorithm 3.5: another permutation
I often go to lunch with my colleagues. At this point, I started to talk about this problem. It seems, Leo, Joachim, and Marc are interested in this story. I thought minimal dot product method is a good idea, so, I was kind of proud of that I found this simple method. My friends also agreed that this might work. But, the result is complete failure as shown in the last article.
Marc suggested me a geometrical approach. The max determinant of Hadamard matrix is
If you think about this is a geometrical problem, it is simple. The distance from origin to (1,1,1, ..., 1) coordinate in n-dimensional space is
(n-dimensional Pythagoras theorem). This is one of the longest distance edge. If these length edges are all perpendicular, then the volume of such object has \sqrt{n}^n. This is exactly the Hadamard's bound. The problem arises when these vectors can not be perpendicular. For example, this Strang's question. The problems in Strang's book are always like this. It seems simple problems, but, they are deep.
Joachim also suggested me that exploiting the matrix structure. But when he told me that, I thought minimal dot product is the answer. Therefore, I stupidly disregarded it. But my approach was completely failed, I needed to think about that.
First of all, if the matrix has the same row, the determinant is always zero. (Think about geometry, two axes are the same, then, no volume. Like two edges of a triangle are the same, the triangle is degenerated.) This we can omit it because any determinant value if exists, the max determinant is always more than zero. Even we have a minus value, just exchange two rows, then you got a plus determinant. (This means that if I have the max determinant, then I immediately have the min determinant by exchanging any two rows. Also think about geometry, flip two axes changes the direction of the volume, means the sign is changed.)
Based on this observation, we have the following algorithm: generate all the row candidate, then permute the rows. This narrows down 2^{36} candidates to _{2^6}P_{6} candidates in n = 6 case. But this is 53981544960 cases. This is less than 2^{36}, but the almost the same order.
I often go to lunch with my colleagues. At this point, I started to talk about this problem. It seems, Leo, Joachim, and Marc are interested in this story. I thought minimal dot product method is a good idea, so, I was kind of proud of that I found this simple method. My friends also agreed that this might work. But, the result is complete failure as shown in the last article.
Marc suggested me a geometrical approach. The max determinant of Hadamard matrix is
(n-dimensional Pythagoras theorem). This is one of the longest distance edge. If these length edges are all perpendicular, then the volume of such object has \sqrt{n}^n. This is exactly the Hadamard's bound. The problem arises when these vectors can not be perpendicular. For example, this Strang's question. The problems in Strang's book are always like this. It seems simple problems, but, they are deep.
Joachim also suggested me that exploiting the matrix structure. But when he told me that, I thought minimal dot product is the answer. Therefore, I stupidly disregarded it. But my approach was completely failed, I needed to think about that.
First of all, if the matrix has the same row, the determinant is always zero. (Think about geometry, two axes are the same, then, no volume. Like two edges of a triangle are the same, the triangle is degenerated.) This we can omit it because any determinant value if exists, the max determinant is always more than zero. Even we have a minus value, just exchange two rows, then you got a plus determinant. (This means that if I have the max determinant, then I immediately have the min determinant by exchanging any two rows. Also think about geometry, flip two axes changes the direction of the volume, means the sign is changed.)
Based on this observation, we have the following algorithm: generate all the row candidate, then permute the rows. This narrows down 2^{36} candidates to _{2^6}P_{6} candidates in n = 6 case. But this is 53981544960 cases. This is less than 2^{36}, but the almost the same order.
This algorithm can only improve 27% of the time. It is not so much gain. Let's see the next idea.
Comments