Skip to main content

Posts

Showing posts from April, 2011

(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 boo

(6) Max determinant problem: Algorithm 3, min dot product

Algorithm 3: minimal dot product I extended the geometry idea: if a pair of axes has minimal dot product, it could be a max determinant matrix. Minimal dot product means as perpendicular as possible. I implemented this idea in Program 3. Program 3 function algo_03(matrix_rank) % Introduction to linear algebra Chapter 5. problem 33 % Algorithm 3: find minimal dot product vector % @author Hitoshi   if nargin ~= 1;     error('Usage: algor_03(matrix_rank).')   end   global MatrixRank;   MatrixRank = matrix_rank;   global CombMat;   CombMat = gen_combinatorial_matrix(matrix_rank);   % initialize candidate matrix   cand_mat = zeros(matrix_rank, matrix_rank);   cand_mat(1,:) = CombMat(1,:);   comb_mat_size = size(CombMat);   global CombRowCount;   CombRowCount  = comb_mat_size(1);   for i = 2:matrix_rank     min_dotprod_row_idx = get_min_dotprod_row(cand_mat, i);     cand_mat(i,:) = CombMat(min_dotprod_row_idx, :);   end   cand_mat   det(cand_mat) end %%------------------------

(5) Max determinant problem: Algorithm 2, Orthogonality

Algorithm 2: using orthogonality First I looked into the matrix pattern in 2x2 and 4x4. I saw the rows are orthogonal. I thought, ``Aha, because the determinant is volume and when a simplex has the maximal volume when the edge vector length is fixed? Orthogonal vectors!'' This is quite intuitive for me. Therefore, I implemented a method that looked up the orthogonal vectors. This is program 2. Program 2 function algo_02(mat_rank) % Introduction to linear algebra Chapter 5. problem 33 % Algorithm 2: generate Hadamard matrix (each row is orthogonal), but % this only can gives me 1,2,4k matrices % @author Hitoshi   if nargin ~= 1;     error('Usage: algo_02(mat_rank).')   end   % possible element set A_i = {-1, 1}   SetA = [-1 1];   cand_mat = zeros(mat_rank, mat_rank);   cand_mat(1,:) = ones(1, mat_rank);   cand_row = zeros(1, mat_rank);   global MAXDET   global MAXDET_MAT   MAXDET = 0;   MAXDET_MAT = zeros(1, mat_rank * mat_rank);   cur_row_index = 2;   loopdep

(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, ma

(3) Max determinant problem, Appendix

This is just a side talk and you can skip this. It is a detail about relationship between Fredholm equation of the second kind and the max determinant problem. The basic idea is as following. The discrete form of Fredholm equation of the second kind is a matrix form (a linear system). To get the limit of the discrete form, the dimension of matrix n goes to infinity. The solution of linear system is obtained by a variant of Cramer's rule. This needs the determinant. The absolute value of the determinant relates with the system's convergence. Therefore, the max determinant problem was interesting. Fredholm equation of the second kind is as following. Assume this equation as a discrete problem, the range a,b is n-subdivided, then Set λ (b-a)/n = h, the coefficient of this equation becomes following. When we let the subdivision number n to infinity, the dimension of matrix becomes infinite. When we solve this linear system by Cramer's rule, we need determinant. Please

(2) Max determinant problem

I would like to talk about why mathematicians are interested in max determinant problem. This is just my personal theory and I could not find an article that say this directly. So, I warn you that I might be completely wrong. The max determinant problem is mentioned in a context of partial differential equation.  Is a partial differential equation interesting? I safely say, yes. This includes heat and wave problem. We can design buildings, computers, cars, ships, airplanes, ... and so on. There are so many applications of this in our world. Hadamard is one of the mathematicians who contributed the max determinant problem. His one of the interests was partial differential equation. A basic partial differential equation, for instance, a wave equation is like this. This can be re-written as (By the way, if we wrote it as above, an operator d^2/d x^2 looks like to have an eigenvalue λ. Like Mu = -λu. This is a clue of relationship between integral equation and linear algebra.) Fred

(1) Max determinant problem

Abstract Gilbert Strang asked us what is the maximal determinant if the matrix has only specific numbers in his book, Introduction to Linear algebra. I enjoyed this problem for almost three weeks also as a programming problem. So I would like to introduce this problem in this article. Introduction My primary school has words, ``Be one day as one step of your life (一日生きることが一歩生きることであれ.)'' by Yukawa Hideki. These days I finally start to understand these words. I can only do something if I could do every day. Even for five minutes, if I do something every day, I found quite difference. Recently, I joined an activity. It took some significant time from my Sunday research time, though I would like to continue both my activity and my Sunday research. At the end of March, I learn max determinant problem that exists. I didn't have any dedicated time for this problem. But, I use my commune time and elevator waiting time, I solved this problem. (Our company's elevator giv