An optimization version of the Hadamard problem

Question

First, some definitions.

A Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. The Hadamard conjecture proposes that a Hadamard matrix of order 4k exists for every positive integer k.

A circulant matrix is a special kind of matrix where each row vector is rotated one element to the right relative to the preceding row vector. That is the matrix is defined by its first row.

It is known that, except for 4 by 4 matrices, there are no circulant Hadamard matrices.

A matrix with m rows and n >= m columns is partial circulant, if it is the first m rows of some circulant matrix.

The task

For each even integer n starting at 2, output the size of the largest partial circulant matrix with +-1 entries and n columns that has the property that all its rows are mutually orthogonal.

Score

Your score is the highest n such that for all k <= n, no one else has posted a higher correct answer than you. Clearly if you have all optimum answers then you will get the score for the highest n you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.

Languages and libraries

You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.

Leading entries

• 64 by Mitch Schwartz in Python

Answer 1

Python 2

Table up to n = 64, verified optimal with brute force up to n = 32:

 4  4 0001
 8  4 00010001
12  6 000001010011
16  8 0000010011101011
20 10 00010001011110011010
24 12 000101001000111110110111
28 14 0001011000010011101011111011
32 14 00001101000111011101101011110010
36 18 001000101001000111110011010110111000
40 20 0010101110001101101111110100011100100100
44 18 00010000011100100011110110110101011101101111
48 24 001011011001010111111001110000100110101000000110
52 26 0011010111000100111011011111001010001110100001001000
56 28 00100111111101010110001100001101100000001010100111001011
60 30 000001101101100011100101011101111110010010111100011010100010
64 32 0001100011110101111111010010011011100111000010101000001011011001

where 0 represents -1. If n is not divisible by 4 then m = 1 is optimal. Generated using this code (or small variations of it) but with more trials for higher n:

from random import *

seed(10)

trials=10000

def calcm(x,n):
    m=1
    y=x
    while 1:
        y=((y&1)<<(n-1))|(y>>1)
        if bin(x^y).count('1')!=n/2:
            return m
        m+=1

def hillclimb(x,n,ns):
    bestm=calcm(x,n)

    while 1:
        cands=[]

        for pos in ns:
            xx=x^(1<<pos)
            m=calcm(xx,n)

            if m>bestm:
                bestm=m
                cands=[xx]
            elif cands and m==bestm:
                cands+=[xx]

        if not cands:
            break

        x=choice(cands)

    return x,bestm

def approx(n):
    if n<10: return brute(n)

    bestm=1
    bestx=0

    for trial in xrange(1,trials+1):
        if not trial&16383:
            print bestm,bin((1<<n)|bestx)[3:]

        if not trial&1:
            x=randint(0,(1<<(n/2-2))-1)
            x=(x<<(n/2)) | (((1<<(n/2))-1)^x)
            ns=range(n/2-2)

            if not trial&7:
                adj=randint(1,5)
                x^=((1<<adj)-1)<<randint(0,n/2-adj)
        else:
            x=randint(0,(1<<(n-2))-1)
            ns=range(n-2)

        x,m=hillclimb(x,n,ns)

        if m>bestm:
            bestm=m
            bestx=x

    return bestm,bestx

def brute(n):
    bestm=1
    bestx=0

    for x in xrange(1<<(n-2)):
        m=calcm(x,n)
        if m>bestm:
            bestm=m
            bestx=x

    return bestm,bestx

for n in xrange(4,101,4):
    m,x=approx(n)
    print n,m,bin((1<<n)|x)[3:]

The approach is simple randomised search with hill climbing, taking advantage of a pattern noticed for small n. The pattern is that for optimal m, the second half of the first row often has small edit distance from the (bitwise) negation of the first half. The results for the above code are good for small n but start deteriorating not long after brute force becomes unfeasible; I would be happy to see a better approach.

Some observations:

• When n is odd, m = 1 is optimal because an odd number of ones and negative ones can't add up to zero. (Orthogonal means dot product is zero.)
• When n = 4k + 2, m = 1 is optimal because in order for m >= 2 we need to have exactly n/2 sign reversals among {(a1,a2), (a2,a3), ... (a{n-1},an), (an,a1)}, and an odd number of sign reversals would imply a1 = -a1.
• The dot product of two rows i and j in a circulant matrix is determined by abs(i-j). For example, if row1 . row2 = 0 then row4 . row5 = 0. This is because the pairs of elements for the dot product are the same, just rotated.
• Consequently, for checking mutual orthogonality, we only need to check successive rows against the first row.
• If we represent a row as a binary string with 0 in place of -1, we can check orthogonality of two rows by taking bitwise xor and comparing the popcount with n/2.
• We can fix the first two elements of the first row arbitrarily, because (1) Negating a matrix does not affect whether the dot products equal zero, and (2) We know that there must be at least two adjacent elements with same sign and two adjacent elements with differing sign, so we can rotate to place the desired pair at the beginning.
• A solution (n0, m0) will automatically give solutions (k * n0, m0) for arbitrary k > 1, by (repeatedly) concatenating the first row to itself. A consequence is that we can easily obtain m = 4 for any n divisible by 4.

It is natural to conjecture that n/2 is a tight upper bound for m when n > 4, but I don't know how that would be proven.