阿hadamard矩阵的压缩存储

文章背景与核心概要

本文探讨了阿达玛矩阵（Hadamard matrices）的性质——即所有元素均为 \(\pm 1\) 的正交矩阵——并讨论了对其进行压缩和高效存储的策略。虽然最朴素的存储方法需要 \(n^2\) 个比特，但通过算法生成的结构化矩阵（如西尔维斯特（Sylvester）或佩利（Paley）构造法）或者利用代数性质（如对称性或斜对称性）的零星矩阵，可以用显著更少的内存来进行表示。

通过这篇译文，读者可以深入了解如何结合数学代数结构与算法规则，实现对特殊正交矩阵的高效数据压缩。

Summary

This article explores the nature of Hadamard matrices—orthogonal matrices with entries of \(\pm 1\)—and discusses efficient strategies for compressing and storing them. While a naive storage approach requires \(n^2\) bits, structured matrices generated by algorithmic methods (such as Sylvester's or Paley's constructions) or sporadic matrices leveraging algebraic properties (like symmetry or skew-symmetry) can be represented using significantly less memory.

Introduction

Hadamard matrices are in the news following the recent announcement of a newly discovered Hadamard matrix. I’ve written three posts on Hadamard matrices recently, one as a sort of introduction and two on applications: the error correcting code used in the Mariner 9 probe and constructing sphere packings.

阿达玛矩阵在最近关于新发现阿达玛矩阵的公告发布后成为了热点新闻。我最近写了三篇关于阿达玛矩阵的博文，其中一篇作为简介，另外两篇关于其应用：水手9号探测器中使用的纠错码，以及构造球堆积。

A Hadamard matrix is an orthogonal matrix with all entries equal to \(\pm 1\). Jacques Hadamard conjectured that there exist Hadamard matrices of order \(4n\) for all positive integers \(n\). It’s necessary that the order be divisible by 4, and Hadamard conjectured that this is sufficient [1].

阿达玛矩阵是一个所有元素都等于 \(\pm 1\) 的正交矩阵。雅克·阿达玛（Jacques Hadamard）曾推测，对于所有正整数 \(n\)，存在阶数为 \(4n\) 的阿达玛矩阵。矩阵的阶数必须能被 4 整除，阿达玛推测这也是充分条件 [1]。

How could you compactly represent a Hadamard matrix? Since the entries are all either \(1\) or \(-1\), each entry could be represented by a single bit, and \(n^2\) bits could store an \(n \times n\) Hadamard matrix. But we can do better.

你将如何紧凑地表示一个阿达玛矩阵？由于矩阵元素全为 \(1\) 或 \(-1\)，每个元素可以用单个比特表示，\(n^2\) 个比特就可以存储一个 \(n \times n\) 的阿达玛矩阵。但我们可以做得更好。

Methodical Matrices

If the matrix can be produced by an algorithm, you only need to store the name of the algorithm and the argument to the algorithm. So, for a \(1024 \times 1024\) matrix applied by iterating Sylvester’s algorithm, it could be stored by saying “Apply Sylvester’s algorithm 10 times” rather than storing a megabyte of data.

如果该矩阵可以通过算法生成，你只需要存储算法的名称及其算法参数。因此，对于通过迭代西尔维斯特算法生成的 \(1024 \times 1024\) 矩阵，只需记录“应用西尔维斯特算法 10 次”，而无需存储整整一兆字节的数据。

Paley’s method can create a Hadamard matrix corresponding to every prime power. So you could determine a Paley-type matrix by storing the prime and the exponent.

佩利方法可以为每一个素数的幂次创建一个对应的阿达玛矩阵。因此，你可以通过存储素数及其指数来确定一个佩利类型的矩阵。

Next in complexity would be hybrid algorithms, such as starting with the Paley method applied to \(37^6\) and then applying Sylvester’s algorithm 3 times.

复杂度排在下一步的是混合算法，例如先对 \(37^6\) 应用佩利方法，然后应用 3 次西尔维斯特算法。

There are more methods of creating Hadamard matrices than Sylvester’s method and Paley’s method, though they’re harder to describe and parameterize.

除了西尔维斯特方法和佩利方法之外，还有更多创建阿达玛矩阵的方法，尽管它们更难描述和参数化。

Sporadic Matrices

If a Hadamard matrix cannot be constructed using an algorithm, you can still store the matrix in fewer than \(n^2\) bits. Since the rows are orthogonal, the last row of the matrix is determined by all the previous rows, up to sign. So you could store a Hadamard matrix using \(n(n - 1) + 1\) bits.

如果一个阿达玛矩阵无法通过算法构造，你仍然可以将其存储在少于 \(n^2\) 个比特中。由于各行正交，矩阵的最后一行由前面所有的行（在正负号的意义上）唯一确定。因此，你可以使用 \(n(n - 1) + 1\) 个比特来存储一个阿达玛矩阵。

Some Hadamard matrices are symmetric or skew. A symmetric matrix is determined by its diagonal and the elements above the diagonal. So a symmetric Hadamard matrix could be represented by \(\frac{n(n + 1)}{2}\) bits.

某些阿达玛矩阵是对称的或斜对称的。对称矩阵由其对角线及对角线上方的元素决定。因此，对称阿达玛矩阵可以用 \(\frac{n(n + 1)}{2}\) 个比特表示。

A skew Hadamard matrix isn’t quite skew-symmetric. A matrix \(M\) is skew-symmetric if:

\[M^T = -M\]

This implies the diagonal elements are \(0\), and Hadamard matrices cannot contain \(0\)s. A Hadamard matrix \(H\) is called skew if:

\[H + H^T = 2I\]

This implies the diagonal elements are all \(1\)s and the elements below the diagonal have the opposite sign of the elements above the diagonal. Since the elements on the diagonal are determined, a skew Hadamard matrix can be stored using \(\frac{n(n - 1)}{2}\) bits.

斜阿达玛矩阵（skew Hadamard matrix）并不完全等同于反对称矩阵（skew-symmetric matrix）。如果矩阵 \(M\) 满足下式，则它是反对称的：

这意味着对角线元素为 \(0\)，而阿达玛矩阵不能包含 \(0\)。如果阿达玛矩阵 \(H\) 满足：

则称其为斜阿达玛矩阵。这意味着对角线元素全为 \(1\)，且对角线下方的元素与对角线上方的元素符号相反。由于对角线上的元素已确定，斜阿达玛矩阵可以使用 \(\frac{n(n - 1)}{2}\) 个比特进行存储。

Incidentally, there is a conjecture that there exist skew Hadamard matrices of order \(4n\) for all positive \(n\).

顺便提一句，有一个猜想认为，对于所有正整数 \(n\)，均存在阶数为 \(4n\) 的斜阿达玛矩阵。

Footnotes

[1] There are Hadamard matrices of order 1 and 2, but larger orders must be divisible by 4.

[1] 存在 1 阶和 2 阶的阿达玛矩阵，但更大的阶数必须能被 4 整除。

The post Compressing a Hadamard matrix first appeared on John D. Cook.