一种基于超立方体图的Hadamard矩阵构造法

王 岚 王敏峯

（1.福建广播电视大学 计算机系，福建 福州350003；2.中国人民大学 信息学院，北京 100872）

1引言

1867年，英国数学家詹姆斯·约瑟夫·西尔维斯特从正交性思想出发，提出了Hadamard矩阵[1]，至今已经有一百多年的历史。由于Hadamard矩阵具有优良的正交特性，使得它在区组设计[2]、数据压缩[3]、数字图象处理[4]、数据挖掘[5]、信息安全[6]、通信理论[7]、量子计算[8]、编码理论[9]等诸多领域有着重要的应用。

2 Hadamard矩阵的构造问题

首先给出Hadamard矩阵的定义[10][11]：

定义1 设Hn为一个完全以+1与-1为元素的n×n方阵，如果H满足：

则称Hn为一个n阶Hadamard矩阵。

对于给定的阶数n，若要判断n阶Hadamard矩阵是否存在，可根据如下定理[11]：

定理1 n阶Hadamard矩阵存在的必要条件为：n为自然数，并且满足：

或者

所谓的Hadamard矩阵构造问题即要求寻找到符合上述必要条件的任意阶Hadamard矩阵的构造方法。针对这一问题，几十年来许多学者提出各种各样的解决办法，其中较为著名的有Sylvester构造法[1]、Paley 第一构造法[12]、Paley 第二构造法[12]、Williamson构造法[13]、Turyn 构造法[14]、强直积构造法[14]等等。

尽管已经提出了许多种Hadamard矩阵构造方法，但是，Hadamard矩阵的构造问题仍未完全解决，有许多指定阶数的Hadamard矩阵至今找不到构造方法。其根本原因在于目前所有的矩阵构造方法都只能在某些特定阶数下有效。例如；Sylvester构造法要求阶数n为2的k次幂；Paley第一构造法要求阶数n满足n为素数幂且n+1是4的倍数；Paley第二构造法则局限于阶数n满足（n/2-1）为素数幂且（n/2-2）是4的倍数等等。因此，为了彻底解决Hadamard矩阵的构造难题，一个仍有待继续努力的研究方向是寻找到一些更为新颖的、巧妙的矩阵设计思路。……