Skip to main content

(6) Max determinant problem: Algorithm 3.5, another permutation

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.

This algorithm can only improve 27% of the time. It is not so much gain. Let's see the next idea.

Comments

Popular posts from this blog

Why A^{T}A is invertible? (2) Linear Algebra

Why A^{T}A has the inverse Let me explain why A^{T}A has the inverse, if the columns of A are independent. First, if a matrix is n by n, and all the columns are independent, then this is a square full rank matrix. Therefore, there is the inverse. So, the problem is when A is a m by n, rectangle matrix.  Strang's explanation is based on null space. Null space and column space are the fundamental of the linear algebra. This explanation is simple and clear. However, when I was a University student, I did not recall the explanation of the null space in my linear algebra class. Maybe I was careless. I regret that... Explanation based on null space This explanation is based on Strang's book. Column space and null space are the main characters. Let's start with this explanation. Assume  x  where x is in the null space of A .  The matrices ( A^{T} A ) and A share the null space as the following: This means, if x is in the null space of A , x is also in the null spa

Gauss's quote for positive, negative, and imaginary number

Recently I watched the following great videos about imaginary numbers by Welch Labs. https://youtu.be/T647CGsuOVU?list=PLiaHhY2iBX9g6KIvZ_703G3KJXapKkNaF I like this article about naming of math by Kalid Azad. https://betterexplained.com/articles/learning-tip-idea-name/ Both articles mentioned about Gauss, who suggested to use other names of positive, negative, and imaginary numbers. Gauss wrote these names are wrong and that is one of the reason people didn't get why negative times negative is positive, or, pure positive imaginary times pure positive imaginary is negative real number. I made a few videos about explaining why -1 * -1 = +1, too. Explanation: why -1 * -1 = +1 by pattern https://youtu.be/uD7JRdAzKP8 Explanation: why -1 * -1 = +1 by climbing a mountain https://youtu.be/uD7JRdAzKP8 But actually Gauss's insight is much powerful. The original is in the Gauß, Werke, Bd. 2, S. 178 . Hätte man +1, -1, √-1) nicht positiv, negative, imaginäre (oder gar um

Why parallelogram area is |ad-bc|?

Here is my question. The area of parallelogram is the difference of these two rectangles (red rectangle - blue rectangle). This is not intuitive for me. If you also think it is not so intuitive, you might interested in my slides. I try to explain this for hight school students. Slides:  A bit intuitive (for me) explanation of area of parallelogram  (to my site, external link) .