阿达马矩阵

数学中,阿达马矩阵(英语:Hadamard matrix)是一种特殊的正交矩阵,具有一些重要的性质和应用。它的特点是每个元素只能是+1或-1,并且每行(或每列)之间的内积为0,表示彼此正交。Hadamard矩阵的大小为2的幂次方,即维度为

。阿达马矩阵常用于纠错码,如 Reed-Muller码英语Reed-Muller code。阿达马矩阵的命名来自于法国数学家雅克·阿达马

历史

阿达玛矩阵的历史可以追溯到1893年,当时法国数学家雅克·阿达玛(Jacques Hadamard)发现了一些具有特殊性质的方阵。他找到了阶数为12和20的方阵,这些方阵的元素均为+1或−1,并且它们的每一行和每一列都正交。

阿达玛并非第一个对此研究的人,J.J Sylvester在1867年的发表中就曾发表过相关研究。

在1960年代,美国喷气推进实验室(JPL)致力于建造Mariner和Voyager太空探测器,以探索火星及太阳系的其他行星。那些早期观看月球背面黑白照片的人们可能记得照片上缺失了整条线。第一次登月的黑白电视图片质量极差。而如今,我们已经习惯了木星、土星、天王星、海王星及其卫星的高质量彩色图片。

简单来说,这些高质量的彩色图片是通过依次用红、绿、蓝滤镜拍摄三张黑白照片得到的。每张照片被视为由1000 x 1000个黑白像素组成的矩阵。根据灰度级别,每张照片被分级为1到16的范围,例如白色为1,黑色为16。这些级别用来选择一个基于Hadamard矩阵(例如阶数为32的阿达玛矩阵)的八错误校正码中的码字。码字被传输到地球,进行错误校正,重建三张黑白照片,然后由电脑重建彩色图片。

性质与定义

n 阶的阿达马矩阵 H 满足以下条件

1. 

这意味着 H 与其转置矩阵  的乘积等于 h 倍的单位矩阵 Ih​。这表明阿达玛矩阵的行向量是正交的。

2. 

阿达玛矩阵的行列式的绝对值等于 h 的 h/2 次方。

3. 

这表示阿达玛矩阵是对称的,即其行向量与列向量之间具有相同的内积关系。

4.阿达玛矩阵可以通过重新排列行和列以及将行和列乘以 ±1 来变换为其他阿达玛矩阵:这意味着通过行列的置换和乘以 ±1,可以从一个阿达玛矩阵生成其他阿达玛矩阵。

5.通过适当的变换,可以将一个Hadamard矩阵转换为另一个等价的Hadamard矩阵,但并非所有同阶数的Hadamard矩阵都是等价的。然而,所有的Hadamard矩阵都可以转换为第一行和第一列全部为1的正规化形式。

6.如果 H是阶数为 4n的正规化Hadamard矩阵,则除了第一行和第一列外,每一行和每一列包含 2n 个 +1 和 2n 个 -1。

7.阿达玛矩阵的阶数必须为2的次方数

西尔维斯特构造法

阿达马矩阵最初的构造的例子是由詹姆斯·西尔维斯特给出的。假设H是一个n阶的阿达马矩阵,则下面的矩阵

 

给出一个2n阶的阿达马矩阵。连续使用这个方法,我们可以给出下面的一系列矩阵:

 (最基本的阿达玛矩阵,其他阿达玛矩阵都基于此来建造)
 
 

利用这种方法,西尔维斯特成功地构造了任何2k 阶阿达马矩阵,其中k为非负整数。

西尔维斯特给出的矩阵有些特殊的性质。他们都是对称矩阵,并且这些矩阵的都是0。第一行和第一列的元素都是+1,其他各行各列的元素都是一半+1,一半-1。这些矩阵和沃尔什函数有密切的关系。

不同排列方式的阿达玛矩阵

根据不同的应用与需求,n值相同的阿达玛矩阵具有不同的形式,主要根据变号的次数做调整,以8为例子。

分别是:Sequency ordering(用于信号处理)、Dyadic ordering(用于控制系统)、Natural ordering(用于数学计算以及研究)

Sequency ordering

每一行的变号次数依序为0,1,2...7

 

Dyadic ordering

每一行的变号次数为 0, 1, 3, 2, 7, 6, 4, 5

 

Natural ordering

每一行的变号次数为0, 7, 3, 4, 1, 6, 2, 5

若使用Matlab code :hadamard(8)则会得到此矩阵。

 

阿达玛矩阵的应用

1.错误更正

阿达玛矩阵在错误更正码的构造中应用广泛,如阿达玛码。这些码在电信和数据存储系统中用于高效地检测和修正错误。

2.信号处理

阿达玛矩阵应用于展频技术中,例如CDMA(分码多重进接)系统,用于信号的传输和接收。

3.影像压缩

阿达玛矩阵应用于影像压缩技术中,将影像转换为频域,实现高效的存储和传输。

4.组合数学

阿达玛矩阵与排列矩阵密切相关,在组合数学中研究其在组合设计和配置中的性质

5.量子计算

在量子计算中,阿达玛闸由阿达玛矩阵表示。它们用于创建超位置状态和量子算法,如格罗弗算法(Grover's algorithm)。

阿达玛猜想

阿达马猜想(Hadamard conjecture)是一个关于Hadamard矩阵的数学猜想。这个猜想是由法国数学家雅克·阿达马(Jacques Hadamard)在1893年提出的。具体内容如下:

阿达马猜想: 对于所有的正整数 n是否存在阶数为 4n 的阿达玛矩阵。

也就是说,对于每一个正整数 n,存在一个元素为 ±1 的 4n×4n 矩阵,使得该矩阵的行和列互相正交(即任意两行或两列的内积为0)。

这个猜想至今仍未被完全证明,但已知对于很多特定的 n 值,存在满足条件的阿达玛矩阵。研究表明,当 n 为某些特定形式(例如幂次方或某些素数形式)时,阿达玛矩阵的构造是可能的。然而,对于一般情况,这个猜想仍然是一个未解决的数学难题。

阿达马猜想在数学和工程领域具有重要意义,特别是在编码理论、信号处理和实验设计等方面。Hadamard矩阵的正交性质使其在这些应用中能够有效地减少干扰和错误,提高数据处理的效率和准确性。

西尔维斯特构造法给出了阶数为1, 2, 4, 8, 16, 32 等等的阿达马矩阵,之后阿达马本人给出了阶数为12和20的阿达马矩阵。雷蒙·巴雷英语Raymond Paley随后给出了任何q+1 阶的阿达马矩阵的方法,其中q 是任何模4为3的质数任意次幂。他也给出了形式为2(q+1)的阿达马矩阵的方法,其中q 是任何模4为1的质数任意次幂。他使用了有限域的办法得出了这些结论。阿达马猜想很可能就是Paley提出的。现在有了更多的构造阿达马矩阵的办法。

2004年6月21日,Hadi Kharaghani和Behruz Tayfeh-Rezaie宣布构造出了428阶的阿达马矩阵。[1]现在最小的尚未被构造出来的4k阶阿达马矩阵是668阶。

参考资料

  1. ^ Kharaghani, H.; Tayfeh-Rezaie, B. A Hadamard matrix of order 428 (pdf). Journal of Combinatorial Designs. 2005, 13 (6): 435–440 [2005-06-26]. doi:10.1002/jcd.20043. (原始内容存档 (PDF)于2011-07-22) (英语). 

2. Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2024

3.Evangelaras, Haralambos, Christos Koukouvios, and Jennifer Seberry. "Applications of Hadamard matrices." Journal of telecommunications and information Technology 2 (2003): 3-10.