A complex Hadamard matrix of order 94

本文通过改进 Kharaghani 和 Seberry 的基本块构造法，利用计算机辅助方法发现特定的 47 阶循环矩阵，首次成功构造出了 94 阶复 Hadamard 矩阵。

要点

这篇论文讲述了一个关于数学拼图的精彩故事。为了让你轻松理解，我们可以把这篇论文想象成一位建筑师（作者 Ferenc Szöllősi）在尝试建造一座完美的“数学大厦”。

1. 什么是“完美大厦”？（什么是复 Hadamard 矩阵？）

想象一下，你要设计一个巨大的方阵（像棋盘一样），里面填满了数字。

• 普通版（实 Hadamard 矩阵）： 你只能用 1 和 -1 这两个数字。要求是：每一行和每一列如果互相“碰撞”（做数学上的点积运算），结果必须完美抵消，变成 0。这就像两支队伍在拔河，力量必须完全平衡，不能有一方占优。
• 升级版（复 Hadamard 矩阵）： 这次更高级了，你不仅可以用 1 和 -1，还可以用虚数单位 i（就像在二维平面上旋转了 90 度）和 -i。这就像是在三维甚至四维空间里做平衡，难度更大，但构建出的结构更精妙。

论文的目标： 作者成功建造了一座94 层（94 阶）的这样的大厦。在这之前，没人知道怎么在 94 层的高度上把这种平衡做得完美无缺。

2. 过去的困境：找不到合适的“砖块”

要盖这座 94 层的大厦，传统的建筑方法（叫 Williamson 方法）需要一种特殊的“砖块”。

• 这种砖块必须是对称的（像镜子一样，左右一样）。
• 这种砖块的大小必须是47 块（因为 94 = 2 × 47）。

问题出在哪里？
数学家们发现，对于 47 块大小的对称砖块，根本不存在！就像你想盖楼，但发现市场上卖的所有 47 号砖块都是歪的，或者根本买不到。这就是为什么 94 层的大厦一直盖不起来的原因。

3. 作者的妙招：改造“建筑图纸”

既然买不到完美的对称砖块，作者没有放弃，而是做了一件很聪明的事：修改建筑图纸（算法）。

• 旧图纸（Kharaghani 和 Seberry 的方法）： 要求所有 4 种砖块都必须是“对称”的。
• 新图纸（作者的方法）： 作者发现，只要其中两种砖块是对称的，另外两种可以“不对称”，只要通过一种特殊的“镜像翻转”技巧（论文中提到的矩阵 R，你可以想象成把砖块在镜子里照一下再拼上去），依然能盖出完美的大厦。

比喻：
以前大家觉得做蛋糕必须用 4 个一模一样的模具。作者说：“不，只要其中 2 个模具是圆的，另外 2 个模具虽然形状怪一点，但我把它们翻转一下再放进去，蛋糕依然能烤得完美！”

4. 电脑大搜索：在沙子里找金粒

虽然图纸改好了，但还需要找到那 4 块特定的砖块（47 阶的循环矩阵）。

• 这些砖块由 1 和 -1 组成，排列组合的可能性多如宇宙中的星星。
• 靠人脑去试，就算从宇宙大爆炸开始试，也试不完。

作者做了什么？
他写了一个超级聪明的电脑程序（像是一个不知疲倦的寻宝机器人）：

1. 设定规则： 告诉电脑，我们要找 4 个数字串，它们加起来要满足特定的“能量守恒”（数学上的正交条件）。
2. 快速筛选： 电脑先快速生成一堆候选者，用“哈希函数”（一种快速指纹识别技术）把它们分类。
3. 大海捞针： 电脑在几亿甚至几十亿次的尝试中，终于找到了两对完美的组合（论文中的 Example 1 和 Example 2）。

这就像是在一个巨大的图书馆里，电脑在几秒钟内翻遍了所有书，终于找到了那两本能拼成完美图案的说明书。

5. 最终成果：94 层大厦落成

一旦找到了这两组特殊的“砖块”，作者把它们代入自己修改后的“新图纸”中。

• 结果： 一座完美的、94 层的复 Hadamard 矩阵大厦拔地而起！
• 意义： 这是人类历史上第一次成功构建出 94 阶的这种矩阵。

总结

这篇论文的核心故事是：

1. 难题： 想盖一座 94 层的数学大厦，但缺一种特殊的对称砖块。
2. 创新： 作者没有死磕砖块，而是改进了建筑图纸，允许使用“不对称但可翻转”的砖块。
3. 执行： 利用强大的电脑算力，在海量可能性中找到了那几块缺失的拼图。
4. 成就： 成功填补了数学领域的一个空白，证明了 94 阶的复 Hadamard 矩阵是存在的。

这就好比在说：“虽然我们要找的那个完美零件找不到，但我们发明了一种新的组装方式，只要用几个稍微不同的零件，配合一点‘镜像魔法’，就能造出比原来更棒的东西！”

技术摘要

以下是基于 Ferenc Szöllősi 的论文《A COMPLEX HADAMARD MATRIX OF ORDER 94》（94 阶复 Hadamard 矩阵）的详细技术总结：

1. 研究背景与问题 (Problem)

• 核心问题：构造特定阶数的复 Hadamard 矩阵。Hadamard 矩阵是元素为 $\{-1, 1\}$ 且行向量相互正交的方阵。复 Hadamard 矩阵将元素扩展为 $\{-1, -i, 1, i\}$。
• 具体目标：构造一个94 阶的复 Hadamard 矩阵。
• 现有困难：
  • 传统的 Williamson 方法需要四个对称的循环 $\{-1, 1\}$ 矩阵（Williamson 矩阵）来构造 $4p$阶实 Hadamard 矩阵。然而，对于$p=47$（即目标$2p=94$ 的基础），已证明不存在 Williamson 矩阵。
  • Kharaghani 和 Seberry 曾提出利用 Williamson 矩阵构造 $2p$ 阶复 Hadamard 矩阵的方法，但这同样依赖于对称矩阵的存在。
  • 在 $p=47$ 时，已知的对称矩阵组合（如 Williamson 矩阵、Good 矩阵、G-矩阵）均不存在，导致无法直接应用现有理论构造 94 阶复 Hadamard 矩阵。

2. 方法论 (Methodology)

作者提出了一种修改后的构造方法，并结合了计算机辅助搜索算法：

A. 理论构造的改进 (Theoretical Modification)

• 修改 Kharaghani-Seberry 构造：
  • 作者修改了 Kharaghani 和 Seberry 的块构造法。原方法要求所有四个矩阵均为对称的。
  • 新定理 (Theorem 4)：作者证明了只需其中两个矩阵是对称的，另外两个可以是任意循环矩阵（通过引入反向对角矩阵 $R$ 进行变换），即可构造出 $2p$ 阶的复 Hadamard 矩阵。
  • 构造逻辑：
    1. 设 $A, B, C, D$ 为 $p$ 阶循环 $\{-1, 1\}$ 矩阵，满足 $AA^T + BB^T + CC^T + DD^T = 4pI_p$。
    2. 要求 $A$ 和 $B$ 为对称矩阵。
    3. 利用 $R$（反向单位矩阵）构建块矩阵 $K$，其中包含形如 $(C+DR)/2$ 的项。
    4. 通过验证块矩阵的正规性和互易性（amicability），证明该构造生成的矩阵是复 Hadamard 矩阵。

B. 计算机辅助搜索 (Computer-Aided Search)

由于 $p=47$ 时不存在全对称的矩阵组合，作者针对对称类型 (ssxx)（即两个对称，两个非对称/非斜对称）进行了搜索：

• 搜索策略：
  • 利用行和（row sums）$\sigma_A, \sigma_B, \sigma_C, \sigma_D$ 的约束条件（$\sum \sigma^2 = 4p$）缩小搜索空间。
  • 利用特征值界限（Lemma 5）过滤不满足条件的向量。
  • 哈希加速：定义了一个基于周期自相关系数（periodic autocorrelation coefficients）的哈希函数 $h(x)$。
    • 先生成满足行和约束的对称向量 $a, b$，计算其自相关和 $\Sigma = I(a) + I(b)$ 并存储。
    • 随机生成非对称向量 $c, d$，计算 $\Delta = -I(c) - I(d)$。
    • 检查 $\Delta$ 是否存在于哈希表中，若存在则找到匹配解。
• 计算资源：使用 C++ 实现，预计算素数和余数表。对于 $p=47$，内存消耗约 20GB，进行了约 $8 \times 10^9$ 次尝试，耗时一天多。

3. 关键贡献 (Key Contributions)

1. 理论突破：提出了Theorem 4，放宽了构造 $2p$阶复 Hadamard 矩阵的条件，从“四个对称矩阵”降低为“两个对称矩阵 + 两个任意循环矩阵（配合$R$变换）”。这解决了$p=47$ 时因缺乏全对称矩阵而无法构造的瓶颈。
2. 首次构造：首次成功构造了94 阶复 Hadamard 矩阵。
3. 发现新矩阵：通过计算机搜索，发现了 $p=47$ 阶的满足特定对称类型 (ssxx) 的循环矩阵组（见 Example 1 和 Example 2），填补了该阶数下矩阵存在的空白。

4. 主要结果 (Results)

• 定理 1 (Theorem 1)：存在一个 94 阶的复 Hadamard 矩阵。
• 具体实例：
  • Example 1：行和分别为 $\sigma_A=3, \sigma_B=7, \sigma_C=7, \sigma_D=9$。自相关和的范数 $\|\Sigma\|=796$，峰值为 14。
  • Example 2：行和分别为 $\sigma_A=-1, \sigma_B=-5, \sigma_C=9, \sigma_D=9$。自相关和的范数 $\|\Sigma\|=1116$，峰值为 18。
  • 这两个例子中的矩阵 $A, B$ 是对称的，$C, D$ 是非对称的，且满足 Williamson 方程 (1)。
• 结合应用：将 Example 1 中的矩阵代入 Theorem 4 的构造公式，即得到 94 阶复 Hadamard 矩阵。

5. 意义与影响 (Significance)

• 填补序列空白：在 $p=35$（70 阶）之后，94 阶（$p=47$）是下一个已知的复 Hadamard 矩阵存在的阶数。此前 $p=47$ 被认为是难点，因为 Williamson 矩阵不存在。
• 方法论推广：该论文展示的“部分对称 + 计算机搜索”策略为构造其他高阶 Hadamard 矩阵提供了新路径。作者指出，未来可能利用超级计算机和更先进的算法突破 $p=59$（118 阶）等更高阶数的限制。
• 数学结构深化：加深了对 Goethels-Seidel 阵列和复 Hadamard 矩阵构造中“互易性”（amicability）与对称性关系的理解。

总结：这篇论文通过理论创新（放宽对称性要求）与计算实验（大规模哈希搜索）的完美结合，成功解决了长期悬而未决的 94 阶复 Hadamard 矩阵构造问题，是组合数学和矩阵理论领域的一项重要进展。