1. Re: Max determinant via Hadamard product of Toeplitz & Hankel (W. Edwin Clark)

...

OK, my searcher has now found matrices of the form Toeplitz*Hankel, where * denotes Hadamard elementwise matrix product (C=A*B means C_ij=A_ij B_ij) where both A and B are sign matrices, which achieve the maximum possible |determinant| among ALL matrices of size N with entries in [-1,1], for EVERY N=1,2,3,...,13 (and N=16). See http://oeis.org/A003433 .

It follows from your computation that some Hadamard matrices of order can be factored in this way. Question: Do all Hadamard matrices<http://en.wikipedia.org/wiki/Hadamard_matrix>have such a factorization? I would guess not.

--that is basically the $64000 question -- albeit with the slight alteration that we are not interested in the Hadamard matrix itself -- we merely want that one of its "equivalent" forms have a Hank*Toep expression -- and further, even then I merely ask that at least one Hadamard of each size have such an expression, not necessarily every one. Further, I am also interested in "maxdet" matrices of each size -- Hadamards are maxdet matrices only at multiples of 4 as the matrix size, but I am interested in all matrix sizes. =========REVIEW/RECAP ABOUT MAXDET PROBLEM======== It has been a problem open for over 150 years to find the largest determinant that an NxN matrix with |entries|<=1, can have. The current record upper & lower bounds are in this online "hall of fame": http://www.indiana.edu/~maxdet/ the exact answers are known for 1<=N<=21. Many contributions to the current hall of fame were made by Tomas Rokicki. (I played some role too, lesser and earlier.) Now, in all those years, there has never been a reasonably small+simple matrix subclass proposed, which contains the solutions to all maxdet problems for all N. Until now: the Toep*Hank form does the job for each size N=1,2,...,13. So maybe it keeps working forever! That would be spectacular if true. However, I have no great reason to believe it is true aside from fact it works for 1,2,...,13. I have no idea whether it works for N=14 and/or 15. Now if we restrict to N which happen to be 1,2, or divisible by 4, then it is famous open conjecture that a "Hadamard matrix" always exists of size N. That means a matrix with +1 and/or -1 entries, and determinant=N^(N/2) (which necessarily is maximum). Many great mathematicians have tried to investigate that question: J.J. Sylvester, J. Hadamard, R.E.A.C.Paley, John Williamson, and Jennifer Seberry being probably the greatest contributors. Williamson came up with a simple form which for over 50 years everybody conjectured sufficed to yield a Hadamard matrix of every size N=4*n>=4. It is: A B C D -B A -D C -C D A -B -D -C B A where A,B,C,D each are symmetric nXn circulant matrices chosen so it works. But eventually computer hardware & software got good enough to do an exhaustive search for all Williamson-form Hadamards with n<=59. The result of this search was one exists for each n=1,3,5,7,9,...,33 (only odd n need be considered)... plus it works for certain infinite sets of n... therefore "clearly" it keeps going forever... BUT none exist when n=35, 47, 53, and 59. So there is no Williamson-form Hadamard with size N=4*35=140. Oops!! The current guess is that the initial 50 years of thinking were exactly wrong and Williamson form almost never works!! Then Fletcher, Gisin & Seberry in 2001 came up with a new matrix form: -1 -1 j j -1 +1 j -j j' j' A B j' -j' B' -A' where j is an n-vector with all entries +1, the prime' denotes matrix transpose, and A and B are nXn circulant matrices. This if you pick A,B right hopefully yields an NxN Hadamard matrix where N=2n+2. Computers and humans have shown that suitable A,B exist showing this works for: n=prime, 2n+1=prime power, n+1=power of 2, n=(P+2)*P=product of twin primes, n=3,5,7,9,...,55,57,59,61. (Only odd n need be considered.) Therefore, it "clearly" keeps working forever. Well, maybe. Given the fate of the Williamson construction, I'm sure not willing to bet the house on this. You can also use this same form (perhaps lopping off the first one or two rows & columns and now allowing even n) to seek maxdet matrices of any size (not necessarily multiple of 4), something Rokicki has done a lot, and it often works pretty well. However, this then definitely fails to reach the max determinant, no matter what A, B you try, for numerous specific sizes N. So it seems every matrix form that has ever been tried, fails to yield maxdet matrices at at least some sizes. Hence my excitement over the Hank*Toep form, which has successfully yielded a maxdet matrix at every size 1,2,...,13 for which I have been able to complete an exhaustive search over all the Hank*Toeps. So far. Maybe the dream will die at size N=14. If it can be shown to survive up to N=20 then I will start to believe it keeps going forever. But showing it survives up to N=20 (or not) is probably beyond what my current computer can do... the entire internet could probably do it (if harnessed...) so I need to write better code.