[math-fun] Maximum |determinant| for NxN circulant sign matrix?
What is the maximum |determinant| of an NxN circulant matrix whose defining first row consists entirely of +1's and -1's? (Related question: each entry lies between -1 and +1 inclusive?) -------- The answer is <=N^(N/2), but this upper bound is achieved only when N=1 and N=4 (by -1,1,1,1). When N=5 the best matrix is (-1,1,1,1,1). Thus the sequence begins 1,0,4,16,48 and the next entry perhaps is 128 from (-1,1,1,1,1,1). The NxN circulant matrix (-1,1,1,...,1) has det = N * (-2)^(N+1) = -1,0,+4,-16,+48,-128... but this formula definitely stops yielding maximum |det| at N=7 because formula would yield 320 whereas the matrix (-1,1,-1,-1,1,1,1) has det=512. [Possible calculational tricks: The first entry is +1 wlog saving you a factor of 2. The second entry is >= the last entry, saving further factor. The determinant of an NxN circulant can be calculated by taking the FFT of the first row, scaling, then product of FFT entries, see http://en.wikipedia.org/wiki/Circulant_matrix which runs in O(NlogN) operations. Using however the slow discrete FT instead of fast FT we can improve to time O(N) per matrix by examining matrices in gray-code order.] -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
On Sat, Aug 18, 2012 at 12:43 PM, Warren Smith <warren.wds@gmail.com> wrote:
What is the maximum |determinant| of an NxN circulant matrix whose defining first row consists entirely of +1's and -1's? (Related question: each entry lies between -1 and +1 inclusive?)
By changing slightly my (brute force) Maple program for http://oeis.org/A144926 for your question I get the following: 1, 1, [-1] 2, 0, 3, 4, [-1, -1, 1] 4, 16, [-1, -1, -1, 1] 5, 48, [-1, -1, -1, -1, 1] 6, 128, [-1, -1, -1, -1, -1, 1] 7, 512, [-1, -1, -1, 1, -1, 1, 1] 8, 2304, [-1, -1, -1, -1, 1, -1, 1, 1] 9, 6912, [-1, -1, -1, -1, -1, 1, -1, 1, 1] 10, 22528, [-1, -1, -1, -1, -1, -1, 1, -1, 1, 1] 11, 273408, [-1, -1, -1, -1, -1, 1, -1, -1, 1, 1, 1] 12, 2097152, [-1, -1, -1, -1, -1, 1, -1, 1, -1, -1, 1, 1] 13, 14929920, [-1, -1, -1, -1, -1, -1, 1, -1, 1, -1, -1, 1, 1] 14, 50331648, [-1, -1, -1, -1, -1, -1, -1, 1, -1, 1, -1, -1, 1, 1] 15, 390905856, [-1, -1, -1, -1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1] The sequence 1, 0, 4, 16, 48, 128, 512, 2304, 6912, 22528, 273408, 2097152, 14929920, 50331648, 390905856 is apparently not in the OEIS.
This is a related problem to the maximum determinant problem: http://www.indiana.edu/~maxdet/ The maximum determinant problem was the subject of a programming contest run by Lars Bakstrom in 2005: http://recmath.org/contest/Determinant/matrix.html [This contest was similar in spirit to the Al Zimmermann contests that used to be held regularly; I miss them greatly.] Recirculant matrices played a significant role in the results, and many tricks like the FFT trick were discussed. It's a great problem. On Sat, Aug 18, 2012 at 10:34 AM, W. Edwin Clark <wclark@mail.usf.edu>wrote:
On Sat, Aug 18, 2012 at 12:43 PM, Warren Smith <warren.wds@gmail.com> wrote:
What is the maximum |determinant| of an NxN circulant matrix whose defining first row consists entirely of +1's and -1's? (Related question: each entry lies between -1 and +1 inclusive?)
By changing slightly my (brute force) Maple program for http://oeis.org/A144926 for your question I get the following:
1, 1, [-1] 2, 0, 3, 4, [-1, -1, 1] 4, 16, [-1, -1, -1, 1] 5, 48, [-1, -1, -1, -1, 1] 6, 128, [-1, -1, -1, -1, -1, 1] 7, 512, [-1, -1, -1, 1, -1, 1, 1] 8, 2304, [-1, -1, -1, -1, 1, -1, 1, 1] 9, 6912, [-1, -1, -1, -1, -1, 1, -1, 1, 1] 10, 22528, [-1, -1, -1, -1, -1, -1, 1, -1, 1, 1] 11, 273408, [-1, -1, -1, -1, -1, 1, -1, -1, 1, 1, 1] 12, 2097152, [-1, -1, -1, -1, -1, 1, -1, 1, -1, -1, 1, 1] 13, 14929920, [-1, -1, -1, -1, -1, -1, 1, -1, 1, -1, -1, 1, 1] 14, 50331648, [-1, -1, -1, -1, -1, -1, -1, 1, -1, 1, -1, -1, 1, 1] 15, 390905856, [-1, -1, -1, -1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1]
The sequence 1, 0, 4, 16, 48, 128, 512, 2304, 6912, 22528, 273408, 2097152, 14929920, 50331648, 390905856 is apparently not in the OEIS. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Oops, I mean Lars Backstrom. Please forgive me, Lars.
contest run by Lars Bakstrom in 2005:
-- -- http://cube20.org/ -- http://golly.sf.net/ --
On 8/18/12, W. Edwin Clark <wclark@mail.usf.edu> wrote:
On Sat, Aug 18, 2012 at 12:43 PM, Warren Smith <warren.wds@gmail.com> wrote:
What is the maximum |determinant| of an NxN circulant matrix whose defining first row consists entirely of +1's and -1's? (Related question: each entry lies between -1 and +1 inclusive?)
By changing slightly my (brute force) Maple program for http://oeis.org/A144926 for your question I get the following:
--I confirm your findings. My own program is in C and is rather stupid in the sense it uses a general purpose determinant routine, not specialized for circulants. Anyway, it finds N det example matrix 1 1.00 + 2 0.00 +- 3 4.00 -++ 4 -16.00 +--- 5 48.00 -++++ 6 -128.00 +----- 7 512.00 --+-+++ 8 2304.00 ++-+---- 9 6912.00 -+-++-+++ 10 22528.00 ++-+---+-- 11 273408.00 -+-+--+++++ 12 2097152.00 ++++--+-+++- 13 14929920.00 --+-+++++-+++ 14 -50331648.00 ++--+-+------- 15 390905856.00 +---++-+-+++++- 16 -1644167168.00 +---+-+++--+---- 17 12279939072.00 ++-+++--++-+---++ 18 69660573696.00 +++++-++--+-+-++-- 19 865782202368.00 +++--+++-+----++-++ 20 5566277615616.00 +-+--++-++++++--+++- 21 41248865910784.02 ---+-+++-++-++++-++++ 22 -215055782117376.19 +-+----+--+--++---+++- 23 2385859554836482.50 +-+---+-++-++++-+++--++ 24 25783171861708820.00 ++++-++-+-+---+--+++++-- 25 146322302697472192.00 +-+----++-++++--+++-++-++ where I have stopped it here since clearly the limits of double-precision IEEE reals have been reached (the true answer is always an integer), and probably exceeded. If anybody writes an actually-good program they should be able to reach N in the 40-50 range... and compute the exact-integer answers.
participants (3)
-
Tom Rokicki -
W. Edwin Clark -
Warren Smith