Primeiro, algumas definições.

Uma matriz Hadamard é uma matriz quadrada cujas entradas são +1 ou -1 e cujas linhas são mutuamente ortogonais. A conjectura de Hadamard propõe que existe uma matriz Hadamard de ordem 4k para todo número inteiro positivo k.

Uma matriz circulante é um tipo especial de matriz em que cada vetor de linha é girado um elemento para a direita em relação ao vetor de linha anterior. Essa é a matriz é definida por sua primeira linha.

É conhecido que, com excepção de quatro por quatro matrizes, existem há matrizes de Hadamard circulantes .

Uma matriz com m linhas e n> = m colunas é circulante parcial , se for a primeira m linhas de alguma matriz circulante.

A tarefa

Para cada número inteiro par n começando em 2, imprima o tamanho da maior matriz circulante parcial com entradas + -1 en colunas que possui a propriedade de que todas as suas linhas são mutuamente ortogonais.

Ponto

Sua pontuação é a mais alta, de nmodo que, para todos k <= n, ninguém postou uma resposta correta mais alta que você. Claramente, se você tiver todas as respostas ideais, obterá a pontuação mais alta que nvocê postar. No entanto, mesmo que sua resposta não seja a ideal, você ainda pode obter a pontuação se ninguém mais conseguir vencê-la.

Línguas e bibliotecas

Você pode usar qualquer idioma e bibliotecas disponíveis que desejar. Sempre que possível, seria bom poder executar seu código; portanto, inclua uma explicação completa de como executar / compilar seu código no Linux, se possível.

Entradas principais

• 64 por Mitch Schwartz em Python

Python 2

Tabela até n = 64, verificada ideal com força bruta até 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

onde 0representa -1. Se nnão é divisível por 4, então m = 1é ideal. Gerado usando esse código (ou pequenas variações dele), mas com mais tentativas para maiores 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:]

A abordagem é uma pesquisa aleatória simples com subidas, aproveitando um padrão observado por pequenos n. O padrão é que, para otimizar m, a segunda metade da primeira linha geralmente tem uma pequena distância de edição da negação (em bits) da primeira metade. Os resultados para o código acima são bons para pequenos, nmas começam a se deteriorar não muito tempo depois que a força bruta se torna inviável; Eu ficaria feliz em ver uma abordagem melhor.

Algumas observações:

• Quando né ímpar, m = 1é ideal porque um número ímpar de unidades e unidades negativas não podem somar zero. (Ortogonal significa que o produto escalar é zero.)
• Quando n = 4k + 2, m = 1é ideal porque, para m >= 2isso, precisamos ter exatamente n/2inversões de sinal entre {(a1,a2), (a2,a3), ... (a{n-1},an), (an,a1)}, e um número ímpar de inversões de sinal implicaria a1 = -a1.
• O produto escalar de duas linhas ie jem uma matriz circulante é determinado por abs(i-j). Por exemplo, se row1 . row2 = 0então row4 . row5 = 0. Isso ocorre porque os pares de elementos para o produto escalar são iguais, apenas rotacionados.
• Conseqüentemente, para verificar a ortogonalidade mútua, precisamos apenas verificar linhas sucessivas na primeira linha.
• Se representarmos uma linha como uma string binária com 0no lugar de -1, podemos verificar a ortogonalidade de duas linhas usando xor bit a bit e comparando o popcount com n/2.
• Podemos fixar os dois primeiros elementos da primeira linha arbitrariamente, porque (1) Negar uma matriz não afeta se os produtos pontuais são iguais a zero e (2) Sabemos que deve haver pelo menos dois elementos adjacentes com o mesmo sinal e dois elementos adjacentes com sinal diferente, para que possamos rotacionar para colocar o par desejado no início.
• Uma solução (n0, m0)fornecerá automaticamente soluções (k * n0, m0)arbitrárias k > 1, concatenando (repetidamente) a primeira linha para si mesma. Uma conseqüência é que podemos obter facilmente m = 4qualquer ndivisível por 4.

É natural conjeturar que n/2é um limite superior apertado para mquando n > 4, mas não sei como isso seria provado.