A complex Hadamard matrix of order 94

This paper presents the first construction of a complex Hadamard matrix of order 94 by modifying a fundamental block method to utilize specific circulant $\{-1,1\}$-matrices of order 47, which were identified through computer-aided search.

The Gist

Imagine you are a master architect trying to build a perfect, self-balancing tower. In the world of mathematics, this "tower" is called a Hadamard Matrix.

Think of a Hadamard Matrix as a giant grid of numbers where every row is a unique "friend" to every other row. They are so perfectly balanced that if you compare any two rows, their differences cancel out perfectly, leaving zero. This property is incredibly useful for things like error-correcting codes in your phone, medical imaging (MRI), and cryptography.

For a long time, mathematicians could only build these towers using Real Numbers (just $+1$ and $-1$). But in recent decades, they discovered that if you allow Complex Numbers (which include imaginary numbers like $i$, the square root of $-1$), you can build these towers in new, more flexible ways.

The Problem: The Missing Brick

The paper you're reading is about a specific, stubborn puzzle: Can we build a complex Hadamard tower of size 94?

To build a tower of size 94, mathematicians usually use a recipe that requires four special "bricks" (matrices) of size 47.

• The Old Recipe: For years, the best recipe (called the Williamson method) required all four bricks to be perfectly symmetrical (like a mirror image).
• The Bad News: For the size 47, mathematicians tried for decades to find these four symmetrical bricks. They didn't exist. It was like trying to build a house with a specific type of brick that simply wasn't manufactured.

Because the "perfect" bricks didn't exist, the tower of size 94 remained unbuilt.

The New Solution: A Clever Twist

The author, Ferenc Szöllősi, decided to stop looking for the perfect bricks and instead rewrite the blueprint.

He took an existing, slightly different recipe (originally by Kharaghani and Seberry) and tweaked it. His new idea was:

"What if we don't need all four bricks to be symmetrical? What if we only need two of them to be symmetrical, and we use a special 'flipping' tool (a mathematical mirror called matrix $R$) to handle the other two?"

It's like realizing you don't need four identical pillars to hold up a roof. If you have two strong, symmetrical pillars, you can use a clever lever system to make the other two work just as well, even if they aren't perfect mirrors.

The Hunt: A Digital Treasure Map

Now that he had the new blueprint, he still needed to find the two symmetrical bricks and the two "flipped" bricks for the size 47.

Since humans can't check every possible combination of $+1$ and $-1$ (there are more combinations than grains of sand on Earth), the author wrote a computer program to act as a digital treasure hunter.

1. The Search: The computer generated millions of random patterns of $+1$s and $-1$s.
2. The Filter: It checked if these patterns fit the strict rules of the new blueprint.
3. The Breakthrough: After running the computer for over a day, using about 20 gigabytes of memory (a lot for a single task!), it finally found the winning patterns.

The Result

The author found two different sets of these special bricks. When he plugged them into his new, modified blueprint, the math worked perfectly.

The Conclusion:
He successfully built the Complex Hadamard Matrix of Order 94 for the first time in history.

Why Does This Matter?

Think of this like solving a Sudoku puzzle that everyone thought was impossible.

• For Mathematicians: It proves that our understanding of these structures is deeper than we thought. It opens the door to finding solutions for even larger, harder numbers (like 118) in the future.
• For the World: While this specific matrix might not change your life tomorrow, the methods used to find it (how we search for patterns in massive data) help improve the algorithms we use for secure communications, better medical scans, and faster data processing.

In short: The author couldn't find the perfect ingredients, so he invented a new recipe that worked with the ingredients he could find, finally allowing him to bake the cake that everyone had been waiting for.

Technical Summary

Here is a detailed technical summary of the paper "A Complex Hadamard Matrix of Order 94" by Ferenc Szöllősi.

1. Problem Statement

The paper addresses the existence and construction of Complex Hadamard Matrices (CHMs).

• Definition: A complex Hadamard matrix of order $n$ is an $n \times n$ matrix with entries from $\{-1, -i, 1, i\}$ such that $HH^* = nI_n$ (where $H^*$ is the conjugate transpose).
• Context: Real Hadamard matrices (entries $\{-1, 1\}$) of order $n$ are well-studied. A classic construction method is Williamson's method, which uses four symmetric circulant $\{-1, 1\}$-matrices of odd order $p$ to construct a real Hadamard matrix of order $4p$.
• The Gap: It was long conjectured that Williamson matrices exist for all odd orders, but counterexamples were found for $p=35$ and $p=47$. Consequently, standard constructions for complex Hadamard matrices of order $2p$ (derived from Williamson matrices) fail for these orders.
• Specific Goal: The author aims to construct a complex Hadamard matrix of order 94 (where $p=47$). Prior to this work, the existence of such a matrix was an open problem, as no suitable symmetric circulant matrices of order 47 existed to satisfy the traditional requirements.

2. Methodology

The author employs a two-pronged approach: theoretical modification of existing constructions and computer-aided search.

A. Theoretical Modification (The Goethels–Seidel Array)

The paper modifies the fundamental block construction of Kharaghani and Seberry.

• Standard Approach: Traditionally, Kharaghani and Seberry used four pairwise amicable matrices (often requiring all four to be symmetric) to build a CHM of order $2p$.
• The Innovation: The author proves Theorem 4, which relaxes the symmetry requirements. Instead of requiring all four matrices to be symmetric, the construction only requires two of the four circulant $\{-1, 1\}$-matrices ($A$ and $B$) to be symmetric. The other two ($C$ and $D$) can be general circulant matrices, provided they satisfy the fundamental sum-of-squares condition:
  $$AA^T + BB^T + CC^T + DD^T = 4pI_p$$
• Mechanism: The construction utilizes the back-diagonal matrix $R$ and specific linear combinations of the matrices to form a block matrix $K$ of order $2p$. The proof relies on showing that the resulting blocks are normal and satisfy orthogonality conditions using properties of amicable matrices and circulant structures.

B. Computer-Aided Search

Since no known matrices of order 47 satisfied the new criteria, the author implemented a search algorithm.

• Symmetry Type: The search focused on finding a quadruple of circulant matrices with symmetry type (ssxx), meaning two symmetric ($s$) and two non-symmetric/non-skew ($x$) matrices.
• Constraints:
  • Row Sums: The row sums $\sigma_A, \sigma_B, \sigma_C, \sigma_D$ must satisfy $\sigma_A^2 + \sigma_B^2 + \sigma_C^2 + \sigma_D^2 = 4p$.
  • Eigenvalue Bounds: The matrices must satisfy specific bounds on their eigenvalues (derived from the Hadamard embedding).
  • Autocorrelation: The search minimizes the norm of the sum of periodic autocorrelation vectors.
• Algorithm:
  1. Generate candidate vectors for the symmetric matrices ($A, B$) satisfying row sum and eigenvalue constraints.
  2. Precompute their autocorrelation vectors $I(a)$ and $I(b)$.
  3. Store sums $I(a) + I(b)$ in a hash table based on a custom hash function.
  4. Randomly generate candidates for the non-symmetric matrices ($C, D$).
  5. Check if $-I(c) - I(d)$ exists in the hash table. If a match is found, the quadruple satisfies the necessary condition (1).
• Resources: The search for $p=47$ required approximately $8 \times 10^9$ trials, utilized ~20GB of memory, and ran for over a day on a single thread.

3. Key Contributions

1. Theoretical Generalization: The paper provides a new construction (Theorem 4) for complex Hadamard matrices of order $2p$ that requires only two symmetric circulant blocks, rather than the four required by previous methods. This significantly expands the pool of potential matrix quadruples.
2. Discovery of Order 94: The paper presents the first known construction of a complex Hadamard matrix of order 94.
3. Explicit Examples: Two distinct sets of circulant matrices of order 47 (symmetry type ssxx) are provided in Example 1 and Example 2, which satisfy the necessary autocorrelation conditions.
   • Example 1: Row sums $(3, 7, 7, 9)$; peak autocorrelation sum = 14.
   • Example 2: Row sums $(-1, -5, 9, 9)$; peak autocorrelation sum = 18.

4. Results

• Main Theorem (Theorem 1): There exists a complex Hadamard matrix of order 94.
• Construction: By combining the specific circulant matrices found in Example 1 with the array defined in Theorem 4, the author explicitly constructs the matrix.
• Search Efficiency: The hash-based search algorithm successfully navigated the vast search space of order 47, identifying valid configurations where previous exhaustive searches for symmetric-only (Williamson) or skew-symmetric (Good/G-matrices) types had failed.

5. Significance

• Resolution of an Open Problem: The existence of a CHM of order 94 was a known open problem. This paper resolves it, pushing the boundary of known complex Hadamard matrices.
• Advancement in Matrix Theory: The work demonstrates that relaxing symmetry constraints (from 4 symmetric blocks to 2) is a viable strategy for constructing Hadamard matrices in orders where traditional methods fail.
• Future Directions:
  • The author suggests the method could be extended to find matrices with only one symmetric block (symmetry type sxxx).
  • The next outstanding order for a complex Hadamard matrix is likely $p=59$ (order 118). The paper posits that with supercomputing resources and refined algorithms, the search could eventually succeed for $p=59$.
• Historical Context: This work builds upon the legacy of Kharaghani, Seberry, and Dokovi´c, continuing the effort to classify complex Hadamard matrices, which are fully known only up to order 18.

In summary, Szöllősi successfully bridges a gap in combinatorial design theory by modifying a fundamental construction to accommodate less restrictive matrix symmetries and using computational power to discover the specific instances required to prove the existence of a complex Hadamard matrix of order 94.