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

Question

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

• 矩阵的每个元素不是 1 就是 -1。
• 任何两行对应元素的乘积之和为零，即对于任何 a <= N 和 b <= NM[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 ^{(n 2 )} ) 。我的计算机没有显示 n = 5 的任何输出，我不得不终止程序。

有人能提出更好的方法来解决这个问题吗？

编辑：您不仅必须回答“是”或“否”，而且还必须枚举一个这样的矩阵。显然，当 N 为奇数时，答案是不可能的。N = 1 是一个简单的情况，答案为 1 或 -1。

Answer 1

正如评论所指出的，具有所描述属性的矩阵称为Haramard 矩阵。维基百科在这些内容上写道：

\n\n

\n

Hadamard 矩阵的阶数必须是 1、2 或 4 的倍数。

\n\n

[\xe2\x80\xa6]

\n\n

Hadamard猜想提出对于每个正整数k都存在一个 4 k阶的 Hadamard 矩阵

\n\n

[\xe2\x80\xa6]

\n\n

截至 2008 年，有 13 个小于或等于 2000 的 4 的倍数，尚无该阶的哈达玛矩阵。^{[ 8 ]}它们是：668、716、892、1004、1132、1244、1388、1436、1676、1772、1916、1948和1964。

\n

\n\n

由于您的问题是N \xe2\x89\xa4 100，因此决定这样一个矩阵是否存在的算法很简单：测试N==1 || N==2 || (N%4)==0。

\n\n

当然，这并没有告诉您如何生成这样的矩阵。阅读更多维基百科建议您可以结合Sylvester 的N = 2 ^k构造和Payley 的N = q + 1 构造，其中q = p ^k对于某些素数p和q \xe2\x89\xa1 3 (mod 4) (确保N是4的倍数)。

\n\n

在N \xe2\x89\xa4 100范围内，这两种算法都不起作用的唯一N是N = 92。因此，您还可以添加Williamson 的构造或针对这种特定情况硬编码一个矩阵。

\n\n

在搜索构造方法的名称时，我找到了Eric Tressler 的Hardamard 猜想调查，其中描述了构造算法，并且还包含尽可能分解 Sylvester 或 Payley 构造的数字的表格。评论还提到了斯隆的哈达玛矩阵库，其中包含通过不同方法获得的实际矩阵的链接。如果您想对其进行硬编码，可以将其用作N = 92 情况的源。

\n