A complex Hadamard matrix of order 94

In diesem Papier wird eine modifizierte Fundamentalkonstruktion von Kharaghani und Seberry vorgestellt, die unter Verwendung computerunterstützter Methoden erstmals eine komplexe Hadamard-Matrix der Ordnung 94 aus bestimmten zirkulanten $\{-1,1\}$-Matrizen der Ordnung 47 konstruiert.

Das Wesentliche

Stellen Sie sich vor, Sie sind ein Architekt, der versucht, ein riesiges, perfektes Mosaik zu bauen. Dieses Mosaik hat eine ganz besondere Eigenschaft: Wenn Sie es mit sich selbst „überlagern" (eine mathematische Operation namens Transponieren und Multiplizieren), verschwinden alle Fehler und es bleibt nur eine perfekte, leere Leinwand übrig. In der Mathematik nennen wir dieses perfekte Mosaik eine Hadamard-Matrix.

Bisher war es sehr einfach, solche Mosaiken aus schwarzen und weißen Steinen (den Zahlen -1 und +1) zu bauen, solange die Größe des Mosaiks eine gerade Zahl war. Aber es gab eine große Lücke: Niemand konnte ein perfektes Mosaik der Größe 94 bauen.

Hier ist die Geschichte, wie der Autor dieses Papier, Ferenc Szöllősi, diese Lücke geschlossen hat, erklärt mit einfachen Bildern:

1. Das Problem: Der fehlende Baustein

Stellen Sie sich vor, Sie wollen ein großes Haus (das Mosaik der Größe 94) bauen. Die alten Baupläne (die sogenannten Williamson-Matrixen) sagten: „Du brauchst vier identische, symmetrische Ziegelsteine, die perfekt ineinander passen."
Das Problem: Für die Größe 47 (die Hälfte von 94) gab es diese perfekten, symmetrischen Ziegelsteine einfach nicht. Man hat sie gesucht, aber sie existierten nicht. Es war, als würde man versuchen, ein Puzzle zu lösen, bei dem die Eckstücke fehlen.

2. Die neue Idee: Ein cleverer Trick mit Spiegeln

Der Autor hat sich gedacht: „Okay, wir können keine perfekten, symmetrischen Steine finden. Aber was, wenn wir die Baupläne ein bisschen umbiegen?"

Stellen Sie sich vor, Sie haben zwei Arten von Steinen:

• Symmetrische Steine: Sie sehen von links und rechts gleich aus (wie ein Schmetterling).
• Spiegelsteine: Sie sehen aus wie das Spiegelbild eines anderen Steins.

In der alten Bauanleitung mussten alle vier Steine symmetrisch sein. Der Autor hat nun eine neue Bauanleitung (Theorem 4) entwickelt. Er sagt: „Wir brauchen nur noch zwei symmetrische Steine. Die anderen beiden dürfen einfach nur Spiegelbilder voneinander sein."

Er benutzt dabei einen mathematischen „Spiegel" (eine Matrix namens $R$), der die Steine umdreht, ähnlich wie ein Spiegel im Flur. Durch diesen Trick kann er die fehlenden perfekten Steine durch eine Kombination aus einem normalen Stein und seinem Spiegelbild ersetzen.

3. Die Jagd nach den Steinen (Der Computer-Einsatz)

Jetzt hatte er die neue Bauanleitung, aber er brauchte immer noch die konkreten Steine für die Größe 47. Da diese Steine in keinem Buch zu finden waren, musste er sie selbst suchen.

Stellen Sie sich vor, Sie suchen nach einem bestimmten Satz von Wörtern in einer Bibliothek mit unendlich vielen Büchern.

• Die Suche: Der Autor programmierte einen Computer, der Milliarden von Kombinationen durchprobte. Es war wie ein riesiges Lotteriespiel, bei dem der Computer jede mögliche Anordnung von -1 und +1 testete.
• Der Filter: Der Computer prüfte nicht jedes Mosaik von Hand. Er benutzte einen cleveren „Fingerabdruck" (einen Hash-Wert), um schnell zu erkennen, ob zwei Steine zusammenpassen könnten.
• Der Erfolg: Nach einem Tag voller Rechnungen und dem Verbrauch von viel Speicherplatz (wie ein riesiger Keller voller Akten) fand der Computer endlich zwei Sätze von Steinen, die passten.

4. Das Ergebnis: Das Mosaik der Größe 94

Sobald er diese Steine hatte, legte er sie in seine neue Bauanleitung (die mit dem Spiegel-Trick). Und Zack! Es entstand ein perfektes, komplexes Mosaik der Größe 94.

Warum ist das wichtig?
Bisher war die Zahl 94 eine „verfluchte" Zahl in der Welt der Mathematik. Niemand konnte beweisen, dass so ein perfektes Mosaik existiert. Mit diesem Papier sagt der Autor: „Es existiert! Und hier ist der Bauplan."

Zusammenfassung in einem Satz

Der Autor hat einen alten, starren Bauplan für mathematische Muster so modifiziert, dass er weniger perfekte Steine braucht, und hat dann mit Hilfe eines Computers die ersten passenden Steine für das bisher unlösbare Puzzle der Größe 94 gefunden.

Es ist wie das Finden des letzten Puzzleteils für ein Bild, das man schon seit Jahrzehnten nicht mehr komplett sehen konnte.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers auf Deutsch:

Titel: Eine komplexe Hadamard-Matrix der Ordnung 94

Autor: Ferenc Szöllősi

---

1. Problemstellung und Hintergrund

Das Ziel der Arbeit ist die Konstruktion einer komplexen Hadamard-Matrix der Ordnung 94.

• Definition: Eine komplexe Hadamard-Matrix der Ordnung $n$ ist eine quadratische Matrix mit Einträgen aus $\{-1, -i, 1, i\}$, deren Zeilen paarweise komplex orthogonal sind (d.h. $HH^* = nI_n$).
• Kontext: Die Existenz reeller Hadamard-Matrizen (Einträge $\{-1, 1\}$) ist für viele Ordnungen bekannt, aber für komplexe Matrizen gibt es Lücken. Bisher waren komplexe Hadamard-Matrizen bis zur Ordnung 18 vollständig klassifiziert.
• Spezifisches Hindernis: Eine gängige Methode zur Konstruktion solcher Matrizen (basierend auf der Arbeit von Kharaghani und Seberry) erfordert die Existenz von vier symmetrischen, zirkulanten $\{-1, 1\}$-Matrizen der Ordnung $p$ (Williamson-Matrizen), die eine bestimmte Summenbedingung erfüllen. Für $p=47$ (was zu einer Ordnung von $2p=94$ führen würde) ist bekannt, dass solche symmetrischen Williamson-Matrizen nicht existieren.
• Fragestellung: Wie kann man eine komplexe Hadamard-Matrix der Ordnung 94 konstruieren, wenn die klassischen symmetrischen Bausteine fehlen?

2. Methodik und theoretischer Rahmen

Der Autor modifiziert eine fundamentale Blockkonstruktion von Kharaghani und Seberry, um die Anforderungen an die Symmetrie der zugrundeliegenden Matrizen zu lockern.

• Goethels-Seidel-Array: Die Arbeit nutzt das Goethels-Seidel-Array als Basis für reelle Hadamard-Matrizen der Ordnung $4p$, das zirkulante Matrizen verwendet, aber keine Symmetrie aller Blöcke voraussetzt.
• Modifikation für komplexe Matrizen (Theorem 4):
  • Der Autor zeigt, dass man eine komplexe Hadamard-Matrix der Ordnung $2p$konstruieren kann, wenn man vier zirkulante${-1, 1}$-Matrizen$A, B, C, D$der Ordnung$p$findet, die die Bedingung$AA^T + BB^T + CC^T + DD^T = 4pI_p$ erfüllen.
  • Wichtige Einschränkung: Im Gegensatz zu früheren Konstruktionen müssen nicht alle vier Matrizen symmetrisch sein. Es reicht aus, wenn mindestens zwei der Matrizen (hier $A$ und $B$) symmetrisch sind.
  • Die Konstruktion integriert die Rückdiagonalmatrix $R$ (Back-diagonal matrix), um die Orthogonalitätseigenschaften trotz fehlender Symmetrie bei $C$ und $D$ zu gewährleisten.
  • Die resultierende Matrix $K$ hat die Form:
    $$K = \begin{bmatrix} X & Y \\ -Y^* & X^* \end{bmatrix}$$
    wobei $X$ und $Y$ aus den zirkulanten Blöcken und $R$ abgeleitet werden.

3. Computergestützte Suche nach den Bausteinen

Da analytische Methoden für $p=47$ versagten, wurde ein computergestützter Suchalgorithmus entwickelt, um die notwendigen zirkulanten Matrizen mit der Symmetrie-Klasse (ssxx) (zwei symmetrisch, zwei beliebig) zu finden.

• Suchraum-Einschränkung:
  • Nutzung von Lemma 4 und Lemma 5, um die Zeilensummen ($\sigma$) und die Eigenwerte der Matrizen einzuschränken.
  • Berechnung der periodischen Autokorrelationskoeffizienten $I(a)$.
  • Verwendung einer Hash-Funktion basierend auf Primzahlen, um Vektoren der Autokorrelation effizient zu speichern und zu vergleichen.
• Algorithmus (Schritte A1–A6):
  1. Wahl der Parameter $p=47$ und einer Suchgrenze $B$.
  2. Generierung von Vektoren für $A$ und $B$ (symmetrisch) und Prüfung auf Eigenwert-Boundaries.
  3. Berechnung der Summe der Autokorrelationen $\Sigma = I(a) + I(b)$ und Speicherung in einer Hash-Tabelle.
  4. Zufällige Generierung von Vektoren für $C$ und $D$ und Berechnung von $\Delta = -I(c) - I(d)$.
  5. Suche nach einem Kollisionseintrag in der Hash-Tabelle ($\Sigma = \Delta$).
  6. Wiederherstellung der Vektoren und Ausgabe der Matrizen.
• Ressourcen: Die Suche für $p=47$ erforderte ca. $8 \cdot 10^9$ Versuche, benötigte etwa 20 GB Arbeitsspeicher und dauerte etwas mehr als einen Tag (Single-Threaded).

4. Ergebnisse

Der Autor präsentiert zwei konkrete Beispiele für die gefundene Konfiguration (Symmetrie-Typ ssxx) für $p=47$:

• Beispiel 1:
  • Zeilensummen: $\sigma_A = 3, \sigma_B = 7, \sigma_C = 7, \sigma_D = 9$.
  • Die Autokorrelations-Summe $\Sigma$ hat einen Peak bei 14 und eine Norm $\|\Sigma\| = 796$.
  • Die entsprechenden Matrizen wurden durch zyklisches Verschieben der Zeilen einer spezifischen $4 \times 47$-Matrix (mit 0 durch -1 ersetzt) gewonnen.
• Beispiel 2:
  • Zeilensummen: $\sigma_A = -1, \sigma_B = -5, \sigma_C = 9, \sigma_D = 9$.
  • Die Autokorrelations-Summe $\Sigma$ hat einen Peak bei 18 und eine Norm $\|\Sigma\| = 1116$.

Hauptergebnis (Theorem 1): Durch die Kombination der in Beispiel 1 gefundenen Matrizen mit der modifizierten Konstruktion aus Theorem 4 wird die Existenz einer komplexen Hadamard-Matrix der Ordnung 94 bewiesen.

5. Bedeutung und Ausblick

• Durchbruch: Dies ist der erste Nachweis einer komplexen Hadamard-Matrix der Ordnung 94.
• Überwindung von Limitierungen: Die Arbeit zeigt, dass die Existenz von Williamson-Matrizen (vollständig symmetrisch) keine zwingende Voraussetzung für komplexe Hadamard-Matrizen ist. Die Lockerung der Symmetrie-Anforderungen auf nur zwei Blöcke erweitert den Suchraum erheblich.
• Reihenfolge: Vor dieser Entdeckung war die Ordnung 70 ($p=35$) der letzte bekannte Fall. Die nächste offene Ordnung ist nun 118 ($p=59$).
• Zukunftsaussichten: Der Autor schlägt vor, die Array-Konstruktion weiter zu modifizieren, um sogar nur eine symmetrische Matrix zu benötigen, oder fortschrittlichere Suchalgorithmen und Supercomputer einzusetzen, um die Grenze bei $p=47$ zu überwinden und höhere Ordnungen zu erreichen.

Zusammenfassend leistet dieser Beitrag einen wesentlichen Fortschritt in der kombinatorischen Matrixtheorie, indem er eine neue Konstruktionsklasse etabliert und ein langjähriges offenes Problem für die Ordnung 94 löst.