A complex Hadamard matrix of order 94

Este artigo descreve uma modificação na construção fundamental de Kharaghani e Seberry que, combinada com métodos computacionais para encontrar matrizes circulares específicas de ordem 47, permite pela primeira vez a construção de uma matriz de Hadamard complexa de ordem 94.

O essencial

Imagine que você está tentando montar um quebra-cabeça matemático gigante e perfeito, onde cada peça deve se encaixar de uma maneira muito específica para que, no final, a imagem inteira faça sentido. Esse é o trabalho de um matemático que estuda Matrizes de Hadamard.

Vamos simplificar o que este artigo do Ferenc Szőllősi está dizendo, usando uma analogia de uma orquestra de músicos.

O Problema: A Orquestra Perfeita

Pense em uma Matriz de Hadamard como uma orquestra onde cada músico (número na matriz) toca uma nota.

• Se a orquestra é "Real", os músicos só podem tocar notas simples: 1 (um som agudo) ou -1 (um som grave).
• Se a orquestra é "Complexa", eles podem tocar notas mais exóticas: 1, -1, i (imagina um som de flauta) e -i (um som de clarinete).

O objetivo é organizar esses músicos em uma grade (uma matriz) de tamanho $N$ de forma que, quando você compara qualquer linha com qualquer outra, elas não "briguem" (são ortogonais). Se tudo estiver perfeito, a orquestra cria uma harmonia matemática perfeita.

O Desafio do Número 94

Por muito tempo, os matemáticos tentaram montar essa orquestra perfeita para o tamanho 94.

• Eles sabiam como fazer para tamanhos menores.
• Eles sabiam como fazer para tamanhos maiores.
• Mas o número 94 era um "fantasma". Ninguém conseguia encontrar a combinação certa de peças.

O método tradicional (chamado de método de Williamson) exigia que todos os blocos de músicos fossem "simétricos" (como um espelho perfeito). Para o tamanho 94, isso era impossível. Era como tentar montar um quebra-cabeça onde uma peça obrigatória simplesmente não existia.

A Solução Criativa: O "Espelho Mágico"

O autor, Ferenc, teve uma ideia brilhante. Ele disse: "E se eu não precisar de todos os músicos sendo espelhos perfeitos? E se eu puder usar um truque?"

1. A Modificação: Ele pegou uma construção antiga (de Kharaghani e Seberry) e a modificou. Em vez de exigir que quatro blocos fossem simétricos, ele mostrou que bastava que dois fossem simétricos e os outros dois pudessem ser "torcidos" de uma maneira específica usando uma matriz especial chamada R (que é como inverter a ordem dos músicos, como se você lesse uma frase de trás para frente).
2. O Truque: Ao usar essa inversão (a matriz R) nos blocos que não eram simétricos, ele conseguiu criar a harmonia perfeita necessária para a orquestra complexa, mesmo sem ter as peças "perfeitas" tradicionais.

A Caça ao Tesouro (A Busca Computacional)

A teoria estava pronta, mas faltava a peça física: os números exatos para o tamanho 47 (que, combinados, formam o 94).

• Encontrar esses números manualmente é como tentar achar uma agulha em um palheiro, mas o palheiro é do tamanho de um planeta.
• O autor usou um computador para fazer uma busca exaustiva. Ele criou um algoritmo (um programa de busca) que testou milhões e milhões de combinações de números.
• Foi como se ele tivesse um robô que testava bilhões de arranjos de músicos por dia, descartando os que faziam "barulho" (erros matemáticos) e guardando os que soavam bem.

O Resultado: A Primeira Vez!

Depois de mais de um dia de computação pesada e usando cerca de 20 GB de memória (o equivalente a ter uma biblioteca inteira de dados na cabeça do computador), o robô encontrou a combinação!

Ele descobriu dois conjuntos de números (chamados de Exemplo 1 e Exemplo 2) que funcionam perfeitamente.

• Com esses números, ele aplicou a sua "receita" modificada (o Teorema 4).
• Resultado: Pela primeira vez na história, uma Matriz de Hadamard Complexa de ordem 94 foi construída.

Resumo em uma Frase

O autor pegou uma receita antiga que não funcionava para o tamanho 94, inventou um novo truque de cozinha (usando espelhos e inversões) para adaptar a receita, e usou um computador superpotente para encontrar os ingredientes exatos que faltavam, resolvendo um mistério matemático que estava aberto há décadas.

Por que isso importa?
Matrizes de Hadamard são usadas em tudo, desde códigos de correção de erros em celulares e satélites até em experimentos de física quântica. Resolver o caso 94 significa que agora temos mais ferramentas para construir sistemas de comunicação mais eficientes e seguros.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "A Complex Hadamard Matrix of Order 94" de Ferenc Szöllősi, apresentado em português.

Resumo Técnico: Uma Matriz de Hadamard Complexa de Ordem 94

1. O Problema

O artigo aborda um problema fundamental na teoria das matrizes de Hadamard: a existência de matrizes de Hadamard complexas de ordem específica.

• Contexto: Uma matriz de Hadamard real de ordem $n$ é uma matriz $\{-1, 1\}$ onde as linhas são ortogonais ($HH^T = nI_n$). Uma generalização para o domínio complexo permite entradas em $\{-1, -i, 1, i\}$, com ortogonalidade complexa ($HH^* = nI_n$).
• O Desafio Específico: Historicamente, a construção de matrizes de Hadamard complexas de ordem $2p$(onde$p$é ímpar) dependia fortemente do método de Williamson, que exigia quatro matrizes circulares simétricas${-1, 1}$de ordem$p$ satisfazendo uma condição de soma de autocorrelações.
• A Obstrução: Sabe-se que para certos valores de $p$, como $p=35$ e $p=47$, não existem matrizes de Williamson (quatro matrizes simétricas). Embora existam generalizações (como matrizes "good", "G-matrices" e "best matrices"), a construção de uma matriz de Hadamard complexa de ordem $2 \times 47 = 94$permanecia um caso em aberto até a publicação deste trabalho. O caso$p=47$ era particularmente difícil porque as construções anteriores exigiam simetrias que não existiam para este número.

2. Metodologia

O autor desenvolve uma abordagem híbrida combinando teoria algébrica de matrizes e busca computacional intensiva.

• Modificação Teórica (Construção de Bloco):

  • O autor modifica uma construção fundamental de Kharaghani e Seberry. Enquanto a construção original exigia que todas as quatro matrizes circulares fossem simétricas (caso de Williamson), Szöllősi demonstra que é possível construir uma matriz de Hadamard complexa de ordem $2p$ se apenas duas das quatro matrizes circulares forem simétricas.
  • A nova construção (Teorema 4) utiliza uma matriz de Goethels-Seidel modificada. Ela incorpora a matriz anti-diagonal $R$ e combina matrizes circulares $A, B, C, D$ de ordem $p$ que satisfazem a equação fundamental:
    $$AA^T + BB^T + CC^T + DD^T = 4pI_p$$
  • A condição crítica relaxada é que $A$ e $B$ devem ser simétricos, enquanto $C$ e $D$ podem ser apenas circulares (não necessariamente simétricos).

• Busca Computacional (Algoritmo de Hash):

  • Para encontrar as matrizes necessárias para $p=47$, foi desenvolvido um algoritmo de busca em C++ e Mathematica.
  • Estratégia: O algoritmo busca quadruplas de vetores circulares com o tipo de simetria (ssxx) (duas simétricas, duas sem simetria específica).
  • Otimização:
    • Uso de limites teóricos (Lemas 4 e 5) para filtrar vetores candidatos baseados na soma das linhas e nos autovalores.
    • Cálculo de coeficientes de autocorrelação periódica.
    • Implementação de uma função de hash baseada em potências de números primos para armazenar e buscar rapidamente vetores de autocorrelação em uma tabela de consulta.
    • O algoritmo gera pares de vetores simétricos ($A, B$), calcula a soma de suas autocorrelações e armazena em uma tabela. Em seguida, gera pares aleatórios ($C, D$) e verifica se a soma de suas autocorrelações (com sinal invertido) existe na tabela, completando assim a equação de soma de autocorrelações.

3. Contribuições Chave

1. Novo Teorema de Construção (Teorema 4): Estende o trabalho de Kharaghani e Seberry, provando que a simetria total das quatro matrizes circulares não é necessária para a construção de matrizes de Hadamard complexas de ordem $2p$. Apenas duas matrizes simétricas são suficientes.
2. Resolução do Caso $p=47$: A primeira construção explícita de uma matriz de Hadamard complexa de ordem 94.
3. Descoberta de Matrizes (ssxx): Identificação de quadruplas de matrizes circulares de ordem 47 com o tipo de simetria (ssxx) que satisfazem as condições de Hadamard, preenchendo uma lacuna na literatura onde apenas tipos (ssss), (ksss), (kkss) e (kkks) eram conhecidos ou buscados para este caso.

4. Resultados

O autor encontrou e apresentou dois exemplos concretos de matrizes circulares de ordem 47 que satisfazem as condições do Teorema 4:

• Exemplo 1:
  • Somas das linhas: $\sigma_A = 3$, $\sigma_B = 7$, $\sigma_C = 7$, $\sigma_D = 9$.
  • Vetores de autocorrelação combinados ($A+B$) com norma $\|\Sigma\| = 796$.
  • Descoberto após aproximadamente $8 \times 10^9$ tentativas, utilizando cerca de 20 GB de memória e um dia de processamento.
• Exemplo 2:
  • Somas das linhas: $\sigma_A = -1$, $\sigma_B = -5$, $\sigma_C = 9$, $\sigma_D = 9$.
  • Vetores de autocorrelação combinados com norma $\|\Sigma\| = 1116$.
  • Ambos os exemplos foram validados computacionalmente e, ao serem inseridos na estrutura do Teorema 4, geram a matriz de Hadamard complexa de ordem 94.

5. Significado e Impacto

• Avanço na Teoria de Hadamard: Este trabalho resolve um problema em aberto de longa data, demonstrando que a ordem 94 é realizável no domínio complexo, mesmo na ausência de matrizes de Williamson clássicas para $p=47$.
• Generalização de Métodos: A modificação da construção de Kharaghani-Seberry abre novas portas para a construção de matrizes de Hadamard complexas em outras ordens onde apenas matrizes simétricas parciais existem.
• Perspectivas Futuras: O autor sugere que a metodologia pode ser estendida para buscar matrizes com apenas uma simetria (tipo sxxx) ou que, com recursos de supercomputação e algoritmos mais sofisticados, seja possível superar o caso $p=47$ e atingir ordens maiores, como $p=59$ (ordem 118), que é o próximo grande desafio não resolvido.

Em suma, o artigo combina uma inovação teórica elegante (relaxamento das condições de simetria) com uma busca computacional robusta para expandir o conhecimento sobre a existência e construção de matrizes de Hadamard complexas.