algorithm - 存在大小为 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⁽ⁿ²⁾ 矩阵。我尝试检查所有这些矩阵，但算法太慢了。 O(n² * (2⁽ⁿ²⁾) 实际上。我的电脑没有显示 n = 5 的任何输出，我不得不终止程序。

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

编辑:您不仅要回答是或否，还要列举一个这样的矩阵。显然，当 N 为奇数时，答案是不可能的。 N = 1 是一个简单的情况，答案为 1 或 -1。

Answer 1

正如评论所指出的，具有所描述属性的矩阵称为 Haramard 矩阵。关于这些Wikipedia writes :

The order of a Hadamard matrix must be 1, 2, or a multiple of 4.

[…]

The Hadamard conjecture proposes that a Hadamard matrix of order 4k exists for every positive integer k

[…]

As of 2008, there are 13 multiples of 4 less than or equal to 2000 for which no Hadamard matrix of that order is known.^[8] They are: 668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, and 1964.

因为你的问题是N ≤ 100，判断这样一个矩阵是否存在的算法很简单:test for 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或针对此特定情况对矩阵进行硬编码。

Searching我找到的构造方法的名称Eric Tressler's Survey of the Hardamard Conjecture其中描述了构造算法，还包含一个表格，尽可能地分解西尔维斯特或佩利构造的数字。评论还提到 Sloane's Library of Hadamard Matrices它链接到通过不同方法获得的实际矩阵。如果您想对其进行硬编码，则可以将其用作 N = 92 情况的来源。