一種基于超立方體圖的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矩陣的構造難題，一個仍有待繼續努力的研究方向是尋找到一些更為新穎的、巧妙的矩陣設計思路。

3 基于超立方體圖的Hadamard矩陣構造法

針對Hadamard矩陣構造問題，本節提出一種新的方法。與之前許多從數論知識出發的構造法不同，本節所提出的構造法則是基于圖論的。由于該方法借助了超立方體圖的概念，因此，首先介紹超立方體圖的定義[15]如下：

定義2 在n維實空間中，取坐標如公式（4）所示的 2n個點{x0，x1，x2，… ，x2n-1}作為頂點集合，對滿足公式（5）的頂點對xi和xj之間連一條邊，所得到的無向圖即為n階超立方體圖。

下圖展示了一個四維的超立方體圖：

以下詳細介紹一種基于圖論的n階Hadamard矩陣構造法。構造法的共分為以下三個步驟：

第一步，構造一個具有n個頂點的超立方體圖G。

第二步，對超立方體圖G上任意兩個點xi和xj，計算它們之間的圖上最短路徑距離dij。（不失一般性，本文規定超立方體圖上的每條邊長度均為1。）

第三步，根據第二步的計算結果，按照公式（6）設置矩陣H中的每一個元素的值。

至此，矩陣H即為所要構造的Hadamard矩陣。

4 構造舉例

本節以二維超立方體圖為例，展示如何構造出四階Hadamard矩陣。

首先，按照定義2構造出一個二維的超立方體圖如下：

接著，可按照圖論方法計算得到如下的最短距離矩陣d：

最后，按照公式（6）最終得到如下的四階矩陣H：

通過計算HHT，不難驗證該矩陣確為四階Hadamard矩陣。

與此類似地，我們可以根據圖1構造出十六階的Hadamard矩陣如下（為了節省篇幅，+1縮寫為“+”號，-1 縮寫為“-”號）：

5 結束語

本文針對Hadamard矩陣的構造問題提出了一種新的基于圖論的構造方法，并通過實例展示了這種構造方法的可行性。不可避免地，與之前提出的所有構造方法一樣，本文所提出構造方法也只能在某些特定階數下有效。因此，本文的下一步工作是考慮將該方法嘗試在階數上進行推廣或者是考慮采用其他圖結構來派生出相應的Hadamard矩陣。

[1] J.J.Sylvester.Thoughts on inverse orthogonal matrices,simultaneous sign successions,and tesselated pavements in two or more colours,with applications to Newton's rule,ornamental tile-work,and the theory of numbers[J].Philosophical Magazine,1867,34：461-475.

[2] Douglas R.Stinson.Combinatorial Designs：Constructions and Analysis[M].Berlin：Springer-Verlag,2004.

[3] Bowyer,D.E,Walsh Functions.Hadamard Matrices and Data Compression[J].IEEE Transactions on Electromagnetic Compatibility,1971,EMC-13(3)：33-37.

[4] 喬陽，潘志斌，喬瑞萍，李東平，蔡騁.基于Hadamard變換和矢量分割的快速搜索算法[J].2009,14(11)：2269-2275.

[5] 尹安容,謝湘,匡鏡明.Hadamard糾錯碼結合支持向量機在多分類問題中的應用[J].電子學報,2008,36(1)：122-126.

[6] 夏戈明,黃遵國,王志英.基于對稱平衡不完全區組設計的無線傳感器網絡密鑰預分配方案 [J].計算機研究與發展,2008,45(1)：154-164.

[7]Steele,R.Introduction to digital cellular radio.In：Mobile radio communications[M],2nd ed.,IEEE Press,New York,1999.

[8] Michael A.Nielsen.Cluster-state quantum computation[J].Reports on Mathematical Physics,2006,57(1)：147-161.

[9] Michio Ozeki.Hadamard Matrices and Doubly Even Self-Dual Error-Correcting Codes[J].Journal of Combinatorial Theory,Series A,1987,44(2)：274-287.

[10] Marshall Hall.Combinatorial theory[M].2nd Edition.New York：A Wiley InterScience Publication,1998

[11] 沈灝.組合設計理論 (第一版)[M].上海：上海交通大學出版社,1996.

[12] R.E.A.C.Paley.On Orthogonal Matrices[J],Mathematical Physics,1933,(12)：311-320.

[13] JWilliamson.Hadamard's determinant theorem and the sum of four squares[J].Duke Mathematical Journal,1944,11：65-81.

[14]Jennifer Seberry,Mieko Yamada.Hadamard matrices,Sequences,and block designs[M]//Jeffery H.Dinitz and Douglas R.Stinson.Contemporary Design Theory：A Collection of surveys,1992：431-560.

[15] Youcef Saad,Martin H.Schultz.Topological Properties of Hypercubes[J].IEEE TRANSACTIONSON COMPUTERS,1988，37(7)：867-872.