[math-fun] max determinant circulant sign matrix of size 40, and summary
N=40 det=6.439842994660582748450 e31 circ=-+++---+-++---++-+-+---------++-++--+-++ think I'll quit finding them now. ---- In summary, all 2^N different NxN circulant sign matrices can have their determinants computed in O(N) arithmetic operations per matrix using the fourier trick combined with the gray code trick. If however we were to generate "binary necklaces" via a "3-gray code" for them, Mark Weston & Vincent Vajnovszki: Gray codes for necklaces and Lyndon words of arbitrary base, Pure Mathematics and Applications 17, 1-2 (2006) 175-182. http://homelinux.capitano.unisi.it/~puma/17_1_2/weston.pdf T.Ueda: Gray codes for necklaces, Discrete Maths. 219,1-3 (2000) 235-248. T.M.Y. Wang and C.D. Savage: A Gray code for necklaces of fixed density, SIAM J. Discrete Maths 9,4 (1996) 654-673. then we could effectively compute the determinants of all NxN circulant sign matrices in O(1) arithmetic operations per matrix, which would have enabled me to reach, not N=40, but in fact about N=44, with the same amount of computing. Perhaps somebody will program that refinement.
NxN circulant matrices with entries +-1 and maximum |determinant| (Matrices specified by stating top row.) N det example matrix 1 1 + 2 0 +- 3 4 -++ 4 -16 +--- 5 48 -++++ 6 -128 +----- 7 512 --+-+++ 8 2304 ++-+---- 9 6912 -+-++-+++ 10 22528 ++-+---+-- 11 273408 -+-+--+++++ 12 2097152 ++++--+-+++- 13 14929920 --+-+++++-+++ 14 -50331648 ++--+-+------- 15 390905856 +---++-+-+++++- 16 -1644167168 +---+-+++--+---- 17 12279939072 ++-+++--++-+---++ 18 69660573696 +++++-++--+-+-++-- 19 865782202368 +++--+++-+----++-++ 20 5566277615616 +-+--++-++++++--+++- 21 41248865910784 ---+-+++-++-++++-++++ 22 -215055782117376 +-+----+--+--++---+++- 23 2385859554836480 +-+---+-++-++++-+++--++ 24 25783171861708800 ++++-++-+-+---+--+++++-- 25 146322302697472000 +-+----++-++++--+++-++-++ 26 1107244165160239104 ++-++---+-++-+-+-----+---- 27 11063259546716733440 -+--+-+---+++++-++--+++-+++ 28 -76787161889935196160 +---+++---+--+++-+--+-+----- 29 6.68472148627227148e+20 -+-+-++-++-----+++----+---+-- 30 5.81509024420837982e+21 -+-+-+-+--+--+-------++++--++- 31 7.30634230169889910e+22 --+-+++-+++---++++++-+-++-+--+- 32 6.07251019096056018e+23 -+-+++-++--------++----+++--+--+ 33 6.83936575994044069e+24 -+---+++-++----+-++-++---+-+----- 34 4.49603940530125316e+25 ---++-------+-+--++++---+-+--++--+ 35 5.73365205894426472e+26 -+++-+-+--+--++-----++-+----+---+++ 36 6.80750852248195719e+27 -++-++++-+-+-+----++--+++++--+--++++ 37 5.41106751627075914e+28 --++-+---+---+-++---+++-++-+-++------ 38 4.39152787578415089e+29 -++-++---+---+-+--++----+-----++++-+-+ 39 6.32198265057225110e+30 --+-+++-+++--++++-+-++-+----+---+-+++++ 40 6.43984299466058275e+31 -+++---+-++---++-+-+---------++-++--+-++
Warren, how many of those terms can be relied on? On Fri, Aug 31, 2012 at 1:52 PM, Warren Smith <warren.wds@gmail.com> wrote:
NxN circulant matrices with entries +-1 and maximum |determinant| (Matrices specified by stating top row.) N det example matrix 1 1 + 2 0 +- 3 4 -++ 4 -16 +--- 5 48 -++++ 6 -128 +----- 7 512 --+-+++ 8 2304 ++-+---- 9 6912 -+-++-+++ 10 22528 ++-+---+-- 11 273408 -+-+--+++++ 12 2097152 ++++--+-+++- 13 14929920 --+-+++++-+++ 14 -50331648 ++--+-+------- 15 390905856 +---++-+-+++++- 16 -1644167168 +---+-+++--+---- 17 12279939072 ++-+++--++-+---++ 18 69660573696 +++++-++--+-+-++-- 19 865782202368 +++--+++-+----++-++ 20 5566277615616 +-+--++-++++++--+++- 21 41248865910784 ---+-+++-++-++++-++++ 22 -215055782117376 +-+----+--+--++---+++- 23 2385859554836480 +-+---+-++-++++-+++--++ 24 25783171861708800 ++++-++-+-+---+--+++++-- 25 146322302697472000 +-+----++-++++--+++-++-++ 26 1107244165160239104 ++-++---+-++-+-+-----+---- 27 11063259546716733440 -+--+-+---+++++-++--+++-+++ 28 -76787161889935196160 +---+++---+--+++-+--+-+-----
29 6.68472148627227148e+20 -+-+-++-++-----+++----+---+-- 30 5.81509024420837982e+21 -+-+-+-+--+--+-------++++--++- 31 7.30634230169889910e+22 --+-+++-+++---++++++-+-++-+--+- 32 6.07251019096056018e+23 -+-+++-++--------++----+++--+--+ 33 6.83936575994044069e+24 -+---+++-++----+-++-++---+-+----- 34 4.49603940530125316e+25 ---++-------+-+--++++---+-+--++--+ 35 5.73365205894426472e+26 -+++-+-+--+--++-----++-+----+---+++ 36 6.80750852248195719e+27 -++-++++-+-+-+----++--+++++--+--++++ 37 5.41106751627075914e+28 --++-+---+---+-++---+++-++-+-++------ 38 4.39152787578415089e+29 -++-++---+---+-+--++----+-----++++-+-+ 39 6.32198265057225110e+30 --+-+++-+++--++++-+-++-+----+---+-+++++ 40 6.43984299466058275e+31 -+++---+-++---++-+-+---------++-++--+-++
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
Starting at N = 29 using the values of -1 and + 1 given by Warren and using Maple with Digits = 1000, I get different values when I round his determinants to the nearest integer. For example, for N = 29 I get Maple's value = -668472148627227148288 Warren's value = 668472148627227148000 It seems that in Warren's numbers there are not enough significant digits above N = 28. Also in the case of N = 29 I get a different sign for the determinant. --Edwin On Fri, Aug 31, 2012 at 2:43 PM, Neil Sloane <njasloane@gmail.com> wrote:
Warren, how many of those terms can be relied on?
On Fri, Aug 31, 2012 at 1:52 PM, Warren Smith <warren.wds@gmail.com> wrote:
NxN circulant matrices with entries +-1 and maximum |determinant| (Matrices specified by stating top row.) N det example matrix 1 1 + 2 0 +- 3 4 -++ 4 -16 +--- 5 48 -++++ 6 -128 +----- 7 512 --+-+++ 8 2304 ++-+---- 9 6912 -+-++-+++ 10 22528 ++-+---+-- 11 273408 -+-+--+++++ 12 2097152 ++++--+-+++- 13 14929920 --+-+++++-+++ 14 -50331648 ++--+-+------- 15 390905856 +---++-+-+++++- 16 -1644167168 +---+-+++--+---- 17 12279939072 ++-+++--++-+---++ 18 69660573696 +++++-++--+-+-++-- 19 865782202368 +++--+++-+----++-++ 20 5566277615616 +-+--++-++++++--+++- 21 41248865910784 ---+-+++-++-++++-++++ 22 -215055782117376 +-+----+--+--++---+++- 23 2385859554836480 +-+---+-++-++++-+++--++ 24 25783171861708800 ++++-++-+-+---+--+++++-- 25 146322302697472000 +-+----++-++++--+++-++-++ 26 1107244165160239104 ++-++---+-++-+-+-----+---- 27 11063259546716733440 -+--+-+---+++++-++--+++-+++ 28 -76787161889935196160 +---+++---+--+++-+--+-+-----
29 6.68472148627227148e+20 -+-+-++-++-----+++----+---+-- 30 5.81509024420837982e+21 -+-+-+-+--+--+-------++++--++- 31 7.30634230169889910e+22 --+-+++-+++---++++++-+-++-+--+- 32 6.07251019096056018e+23 -+-+++-++--------++----+++--+--+ 33 6.83936575994044069e+24 -+---+++-++----+-++-++---+-+----- 34 4.49603940530125316e+25 ---++-------+-+--++++---+-+--++--+ 35 5.73365205894426472e+26 -+++-+-+--+--++-----++-+----+---+++ 36 6.80750852248195719e+27 -++-++++-+-+-+----++--+++++--+--++++ 37 5.41106751627075914e+28 --++-+---+---+-++---+++-++-+-++------ 38 4.39152787578415089e+29 -++-++---+---+-+--++----+-----++++-+-+ 39 6.32198265057225110e+30 --+-+++-+++--++++-+-++-+----+---+-+++++ 40 6.43984299466058275e+31 -+++---+-++---++-+-+---------++-++--+-++
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates:
Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Warren Smith <warren.wds@gmail.com> [Sep 01. 2012 11:55]:
N=40 det=6.439842994660582748450 e31 circ=-+++---+-++---++-+-+---------++-++--+-++
think I'll quit finding them now.
----
In summary, all 2^N different NxN circulant sign matrices can have their determinants computed in O(N) arithmetic operations per matrix using the fourier trick combined with the gray code trick.
If however we were to generate "binary necklaces" via a "3-gray code" for them, Mark Weston & Vincent Vajnovszki: Gray codes for necklaces and Lyndon words of arbitrary base, Pure Mathematics and Applications 17, 1-2 (2006) 175-182. http://homelinux.capitano.unisi.it/~puma/17_1_2/weston.pdf
T.Ueda: Gray codes for necklaces, Discrete Maths. 219,1-3 (2000) 235-248.
IIRC these are only conjectured to have <=3 changes per update. There are no Gray codes for even n >= 8 (fxtbook p.408). For all (feasible, n<=35) odd n I could find Gray codes (for the necklaces, not bracelets). n==37 would have taken 13 days (and 64GB + eps of RAM), the computation was stopped as the machine died at t_0 + 12.5 days (and I have not had access to a machine with enough RAM since). Given A215723(n) is divisible by 2^(n-1), I created A215897 = A215723(n) / 2^(n-1). Now a power of 2 is neatly handled by the floating point exponent, but with printing I suggest to divide by 2^(n-1). Could you indicate how fast your search is?
T.M.Y. Wang and C.D. Savage: A Gray code for necklaces of fixed density, SIAM J. Discrete Maths 9,4 (1996) 654-673.
then we could effectively compute the determinants of all NxN circulant sign matrices in O(1) arithmetic operations per matrix, which would have enabled me to reach, not N=40, but in fact about N=44, with the same amount of computing. Perhaps somebody will program that refinement.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Joerg Arndt -
Neil Sloane -
W. Edwin Clark -
Warren Smith