A complex Hadamard matrix of order 94

In dit artikel wordt een fundamentele constructie van Kharaghani en Seberry aangepast om, met behulp van computeronderzoek naar circulaire matrices van orde 47, voor het eerst een complexe Hadamard-matrix van orde 94 te construeren.

De kern

Stel je voor dat wiskunde een gigantische puzzel is, en de puzzelstukjes die we zoeken zijn speciale vierkante tabellen met getallen erin. In dit artikel gaat de auteur, Ferenc Szöllősi, op zoek naar een heel specifiek, moeilijk te vinden puzzelstuk: een "Complexe Hadamard-matrix" van de orde 94.

Dat klinkt als heel veel wiskundig jargon, maar laten we het eens vertalen naar alledaags taal met een paar creatieve vergelijkingen.

1. Het Doel: Een Perfecte Dans

Stel je voor dat je een dansgroep hebt met 94 mensen. Je wilt ze zo opstellen dat ze allemaal perfect synchroon bewegen, maar zonder elkaar aan te raken of te storen. In de wiskundige wereld noemen we zo'n perfecte opstelling een Hadamard-matrix.

• Echte matrices: Dit zijn de "normale" dansers. Ze dragen alleen rode of blauwe kleding (de getallen +1 en -1).
• Complexe matrices: Dit zijn de "magische" dansers. Ze kunnen ook paars of groen dragen (de getallen +1, -1, +i, -i, waarbij 'i' de imaginaire eenheid is). Ze zijn iets flexibeler, maar het is nog steeds een enorme uitdaging om ze perfect op te stellen.

De uitdaging is: Bestaat er een perfecte dansopstelling voor precies 94 dansers? Tot nu toe was het antwoord "niet bekend". Dit artikel zegt: "Ja, het bestaat!"

2. Het Probleem: De Gebroken Sleutel

Voor de "normale" dansers (de echte matrices) hebben wiskundigen al een oude, bewezen formule om ze te bouwen. Het werkt als een Lego-set: je neemt vier speciale blokken (die we circulante matrices noemen) en plakt ze aan elkaar.

Maar er is een probleem:

• Om de formule voor 94 dansers te gebruiken, heb je vier blokken nodig van 47 stukjes elk.
• De oude formule vereist dat al deze blokken "symmetrisch" zijn (zoals een vlinder, links en rechts hetzelfde).
• Het probleem is dat voor het getal 47, deze perfecte symmetrische blokken niet bestaan. Het is alsof je probeert een auto te bouwen, maar de motor die je nodig hebt, is er niet in de winkel.

3. De Oplossing: Een Nieuwe Bouwtechniek

De auteur zegt: "Oké, als de perfecte symmetrische blokken er niet zijn, laten we dan een nieuwe bouwtechniek bedenken."

Hij pakt een bestaande methode (ontwikkeld door Kharaghani en Seberry) en past deze aan. In plaats van te eisen dat alle blokken perfect symmetrisch zijn, zegt hij:

"Het is genoeg als slechts twee van de vier blokken symmetrisch zijn. De andere twee mogen een beetje 'scheef' zijn, zolang we ze maar slim omdraaien met een speciale spiegel (de matrix R)."

Dit is alsof je in plaats van vier perfecte vleugels voor een vliegtuig, twee perfecte vleugels en twee vleugels gebruikt die je met een haakje vastmaakt. Het werkt nog steeds, maar het vereist een andere constructie.

4. De Jacht: De Digitale Schatzoeker

Nu de nieuwe bouwtechniek klaar is, moet de auteur de vier specifieke blokken van 47 stukjes vinden. Omdat deze niet in de boeken staan, moet hij ze zelf vinden.

Hij gebruikt een computer als een gigantische schatzoeker.

• De zoektocht: De computer probeert miljarden combinaties van +1 en -1.
• De filter: De computer heeft een "geheugen" (een hash-functie) om te onthouden welke combinaties al zijn geprobeerd en welke veelbelovend zijn.
• De uitdaging: Het is alsof je in een oceaan van zandkorrels zoekt naar één specifiek korreltje dat de juiste vorm heeft. De computer heeft ongeveer 8 miljard pogingen nodig en heeft een dag lang non-stop gewerkt met 20 gigabytes aan geheugen (een heel zware last voor een computer).

5. Het Resultaat: De Gouden Vondst

Na al dat rekenen vond de computer twee sets van blokken die precies deden wat ze moesten doen.

• Voorbeeld 1: Een set blokken die, als je ze in de nieuwe formule stopt, een perfecte dans van 94 mensen oplevert.
• Voorbeeld 2: Een tweede, alternatieve set.

Door deze blokken in de nieuwe formule (Theorema 4) te stoppen, bewijst de auteur dat een Complexe Hadamard-matrix van orde 94 echt bestaat.

Waarom is dit belangrijk?

In de wiskunde zijn sommige getallen "moeilijk" en andere "makkelijk". Het getal 94 was een van die lastige, onopgeloste mysteries.

• Het is als het vinden van een ontbrekende schakel in een keten.
• Het bewijst dat we, zelfs als de "oude, makkelijke" weg geblokkeerd is, met creativiteit en slimme algoritmes nieuwe wegen kunnen vinden.
• Het opent de deur voor nog grotere getallen (zoals 118 dansers) in de toekomst.

Kortom: De auteur heeft een nieuwe manier bedacht om Lego-blokken te stapelen, een computer laten zoeken naar de juiste blokjes, en zo een onmogelijk ogend wiskundig raadsel opgelost.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "A COMPLEX HADAMARD MATRIX OF ORDER 94" van Ferenc Szöllősi, geschreven in het Nederlands.

Probleemstelling

Het artikel adresseert een fundamenteel probleem in de combinatoriek en de theorie van Hadamard-matrices: de constructie van een complexe Hadamard-matrix van orde 94.

• Een reële Hadamard-matrix van orde $n$ is een $\{-1, 1\}$-matrix $H$ waarvoor geldt dat $HH^T = nI_n$.
• Een complexe Hadamard-matrix is een matrix met elementen uit $\{-1, -i, 1, i\}$ waarbij de rijen paarsgewijs complex orthogonaal zijn.
• Historisch gezien werd de constructie van dergelijke matrices vaak gebaseerd op de methode van Williamson, die vereist dat vier symmetrische circulaire $\{-1, 1\}$-matrices van oneven orde $p$ bestaan die aan een specifieke somvoorwaarde voldoen.
• Het probleem is dat voor $p = 47$ (wat nodig zou zijn voor een orde van $4 \times 47 = 188$of een complexe matrix van orde$2 \times 47 = 94$), dergelijke Williamson-matrices **niet bestaan**. Eerdere pogingen om complexe Hadamard-matrices van orde$2p$te construeren faalden voor$p=47$ omdat de bestaande constructies (zoals die van Kharaghani en Seberry) symmetrische blokken vereisten die voor deze specifieke orde niet gevonden konden worden.

Methodologie

De auteur past een fundamentele constructie van Kharaghani en Seberry aan om de beperking van symmetrie op te heffen. De methode omvat de volgende stappen:

1. Modificatie van de Goethels-Seidel Array:

   • De auteur introduceert een nieuwe constructie (Theorema 4) die een array van complexe Hadamard-matrices vormt van orde $2p$.
   • In tegenstelling tot eerdere methoden die vier symmetrische matrices vereisten, vereist deze constructie slechts twee symmetrische circulaire matrices ($A$ en $B$) en twee andere circulaire matrices ($C$ en $D$).
   • De constructie maakt gebruik van de back-diagonale matrix $R$ (een matrix met enen op de anti-diagonaal en nullen elders) om de blokken te manipuleren. De matrix $K$ wordt opgebouwd uit combinaties van $A, B, C, D$ en $R$, waarbij complexe getallen ($i$) worden geïntroduceerd via lineaire combinaties zoals $(A+B)/2 + i(A-B)/2$.

2. Voorwaarde voor de Matrices:

   • De matrices $A, B, C, D$ moeten circulaire $\{-1, 1\}$-matrices van orde $p=47$ zijn.
   • Ze moeten voldoen aan de autocorrelatie-voorwaarde: $AA^T + BB^T + CC^T + DD^T = 4pI_p$.
   • Cruciaal is dat $A$ en $B$ symmetrisch zijn ($A=A^T, B=B^T$), terwijl $C$ en $D$ niet noodzakelijk symmetrisch hoeven te zijn. Dit type symmetrie wordt aangeduid als $(ssxx)$.

3. Geautomatiseerde Zoekopdracht:

   • Omdat dergelijke matrices niet in de bestaande literatuur te vinden waren, ontwikkelde de auteur een computer-geassisteerd zoekalgoritme.
   • Voorbereiding: Het gebruik van wiskundige lemmata (Lemma 4 en 5) om de mogelijke rij-sommen ($\sigma$) en eigenwaarden te beperken, wat de zoekruimte drastisch verkleint.
   • Hashing en Autocorrelatie: Het algoritme genereert vectoren, berekent hun periodieke autocorrelatievectoren $I(a)$, en gebruikt een hash-functie gebaseerd op priemgetallen om sommen van autocorrelaties ($I(a) + I(b)$) op te slaan in een lookup-tabel.
   • Zoekstrategie: Het systeem zoekt naar paren vectoren $(c, d)$ waarvan de negatieve autocorrelatiesum ($\Delta = -I(c) - I(d)$) overeenkomt met een opgeslagen som van een paar $(a, b)$.
   • Computatiekracht: De zoekopdracht voor $p=47$ vereiste ongeveer $8 \cdot 10^9$ pogingen, liep ongeveer een dag op een single-threaded processor, en gebruikte ongeveer 20 GB geheugen.

Belangrijkste Bijdragen

1. Nieuwe Constructie (Theorema 4): De auteur bewijst dat het mogelijk is om een complexe Hadamard-matrix van orde $2p$ te construeren met slechts twee symmetrische circulaire blokken, in plaats van vier. Dit opent de deur voor constructies waar de klassieke Williamson-methode faalt.
2. Oplossing voor Orde 94: Voor het eerst wordt een complexe Hadamard-matrix van orde 94 geconstrueerd. Dit lost een langdurig openstaand probleem op in de reeks van bekende complexe Hadamard-matrices.
3. Ontdekking van $(ssxx)$-matrices: De paper presenteert expliciete voorbeelden van vier circulaire matrices van orde 47 met symmetrie-type $(ssxx)$ (twee symmetrisch, twee niet) die voldoen aan de noodzakelijke somvoorwaarde. Twee specifieke voorbeelden (Voorbeeld 1 en 2) worden gepresenteerd met hun respectievelijke rij-sommen en autocorrelatie-eigenschappen.

Resultaten

• Theorema 1: Er bestaat een complexe Hadamard-matrix van orde 94.
• Concrete Constructie: Door de matrices gevonden in Voorbeeld 1 (met rij-sommen $\sigma_A=3, \sigma_B=7, \sigma_C=7, \sigma_D=9$) en Voorbeeld 2 in de array van Theorema 4 te plaatsen, wordt de matrix van orde 94 gegenereerd.
• Statistieken: Voor het eerste voorbeeld werd een lookup-tabel met bijna 137 miljoen entries gegenereerd. De som van de autocorrelatiecoëfficiënten piekte op 14 (voorbeeld 1) en 18 (voorbeeld 2), wat binnen de theoretische grenzen valt.

Betekenis en Toekomstperspectief

• Doorbraak in Bestaande Grenzen: Voorheen waren complexe Hadamard-matrices alleen bekend tot orde 18, en specifieke constructies waren beperkt tot gevallen waar Williamson-matrices bestonden. Dit werk breidt de bekende orde uit naar 94.
• Mogelijke Uitbreidingen: De auteur suggereert dat de array uit Theorema 4 verder kan worden gemodificeerd om zelfs maar één symmetrische matrix te vereisen (wat de zoekruimte voor hogere orden zou vergroten).
• Toekomstige Onderzoek: Het is aannemelijk dat met supercomputers en geavanceerdere zoekalgoritmen constructies voor nog hogere orden (zoals $p=59$, wat zou leiden tot orde 118) in de toekomst haalbaar zullen zijn.

Samenvattend transformeert dit artikel de theorie van Hadamard-matrices door een nieuwe algebraïsche constructie te introduceren die de afhankelijkheid van volledig symmetrische blokken doorbreekt, en bevestigt de existentie van een complexe Hadamard-matrix van orde 94 via een geavanceerde computationele zoektocht.