大小为NxN的Hadamard矩阵的存在性

Question

给定一个整数N，其中N <= 100。是否存在一个大小为NxN的Hadamard矩阵，使得：

• 矩阵的每个元素都是1或-1。
• 任意两行对应元素的积之和为零，即对于任何a<=N和b<=N，M[a][1] * M[b][1] + M[a][2] * M[b][2]...M[a][n] * M[b][n] = 0（考虑基于1的索引）。

---

我所做的：

我尝试了一种暴力解决方案。每个元素可以是1或-1。因此最多可能有2^(n^2)个矩阵。我尝试检查所有这些矩阵，但算法速度太慢了。实际上是O(n^2 * (2^(n^2)))。我的计算机对于n = 5没有显示任何输出，我不得不终止程序。

有人能否建议更好的方法来解决这个问题？

编辑：您不仅需要回答是或否，还要枚举一个这样的矩阵。显然，当N为奇数时，答案是不可能的。 N = 1是一个微不足道的情况，答案为1或-1。

- lassaendie

---

其实，我认为答案是：“是的，当且仅当N是偶数时。” - RBarryYoung

考虑以下内容：假设A是这样一个矩阵，那么A * A^T（A的转置）的结果是什么？应该会得到N * I（N倍的对角线为1，其余为0的矩阵）。目前我只了解到这个程度。 - Piotr Jaszkowski

对于N=2^k，有通用的解决方案。设A是N=2^{k-1}时候的解，那么N的解是：第一行为|AA|，第二行为|A - A|。你可以将4个小矩阵组合成一个大矩阵。现在我们需要证明对于不是2的幂的N，不能创建这样的矩阵。基本上，如果你有k的解，则这是N=2k的解。 - Piotr Jaszkowski

是的。让我们考虑A中长度为k的两行a和b。现在我们有4个行，aa，a-a，bb，b-b，其中a和b有k/2个不同的值。显然aa和a-a有k个不同的值，aa和bb也是如此，aa和b-b也有k个不同的值，因为a和-b也有k/2个不同的值。 - Piotr Jaszkowski

在这里研究的矩阵（所有条目都为-1或+1，行正交）称为哈达玛矩阵。这对文献搜索应该有所帮助。 维基百科表示，哈达玛矩阵的阶数必须是1、2或4×n。 - njuffa

Answer 1

正如评论所指出的，具有描述特性的矩阵称为“哈达玛矩阵”。维基百科上写道：

“哈达玛矩阵的阶数必须是1、2或4的倍数。” “哈达玛猜想”认为对于每个正整数k，都存在一个阶数为4k的哈达玛矩阵。” 截至2008年，已知有13个4的倍数小于或等于2000的阶数没有哈达玛矩阵。^[8]它们是：668、716、892、1004、1132、1244、1388、1436、1676、1772、1916、1948和1964。

由于您的问题中写道 N ≤ 100，判断这样的矩阵是否存在的算法很简单：测试 N==1 || N==2 || (N%4)==0。

当然，这并不能告诉您如何生成这样的矩阵。阅读更多维基百科的内容后，建议您将 Sylvester's construction 用于 N = 2^k，将 Payley's construction 用于 N = q + 1，其中 q = p^k，p 是某个质数，且 q ≡ 3 (mod 4)（确保 N 是4的倍数）。

在范围 N ≤ 100 内，两种算法都无法使用的唯一 N 是 N = 92。因此，您可以添加Williamson's construction或为该特定情况硬编码一个矩阵。

在搜索构造方法的名称时，我发现 Eric Tressler 的《Hardamard 猜想调查》 描述了构造算法，并包含一个将数字分解为 Sylvester 或 Payley 构造尽可能远的表格。评论还提到了 Sloane 的《Hadamard 矩阵库》，其中包含通过不同方法获得的实际矩阵的链接。如果您想硬编码 N = 92 情况，可以将其用作来源。

- MvG