一種基于超立方體圖的Hadamard矩陣構(gòu)造法

王 嵐 王敏峯

（1.福建廣播電視大學(xué) 計(jì)算機(jī)系，福建 福州350003；2.中國(guó)人民大學(xué) 信息學(xué)院，北京 100872）

1引言

1867年，英國(guó)數(shù)學(xué)家詹姆斯·約瑟夫·西爾維斯特從正交性思想出發(fā)，提出了Hadamard矩陣[1]，至今已經(jīng)有一百多年的歷史。由于Hadamard矩陣具有優(yōu)良的正交特性，使得它在區(qū)組設(shè)計(jì)[2]、數(shù)據(jù)壓縮[3]、數(shù)字圖象處理[4]、數(shù)據(jù)挖掘[5]、信息安全[6]、通信理論[7]、量子計(jì)算[8]、編碼理論[9]等諸多領(lǐng)域有著重要的應(yīng)用。

2 Hadamard矩陣的構(gòu)造問(wèn)題

首先給出Hadamard矩陣的定義[10][11]：

定義1 設(shè)Hn為一個(gè)完全以+1與-1為元素的n×n方陣，如果H滿足：

則稱Hn為一個(gè)n階Hadamard矩陣。

對(duì)于給定的階數(shù)n，若要判斷n階Hadamard矩陣是否存在，可根據(jù)如下定理[11]：

定理1 n階Hadamard矩陣存在的必要條件為：n為自然數(shù)，并且滿足：

或者

所謂的Hadamard矩陣構(gòu)造問(wèn)題即要求尋找到符合上述必要條件的任意階Hadamard矩陣的構(gòu)造方法。針對(duì)這一問(wèn)題，幾十年來(lái)許多學(xué)者提出各種各樣的解決辦法，其中較為著名的有Sylvester構(gòu)造法[1]、Paley 第一構(gòu)造法[12]、Paley 第二構(gòu)造法[12]、Williamson構(gòu)造法[13]、Turyn 構(gòu)造法[14]、強(qiáng)直積構(gòu)造法[14]等等。

盡管已經(jīng)提出了許多種Hadamard矩陣構(gòu)造方法，但是，Hadamard矩陣的構(gòu)造問(wèn)題仍未完全解決，有許多指定階數(shù)的Hadamard矩陣至今找不到構(gòu)造方法。其根本原因在于目前所有的矩陣構(gòu)造方法都只能在某些特定階數(shù)下有效。例如；Sylvester構(gòu)造法要求階數(shù)n為2的k次冪；Paley第一構(gòu)造法要求階數(shù)n滿足n為素?cái)?shù)冪且n+1是4的倍數(shù)；Paley第二構(gòu)造法則局限于階數(shù)n滿足（n/2-1）為素?cái)?shù)冪且（n/2-2）是4的倍數(shù)等等。因此，為了徹底解決Hadamard矩陣的構(gòu)造難題，一個(gè)仍有待繼續(xù)努力的研究方向是尋找到一些更為新穎的、巧妙的矩陣設(shè)計(jì)思路。

3 基于超立方體圖的Hadamard矩陣構(gòu)造法

針對(duì)Hadamard矩陣構(gòu)造問(wèn)題，本節(jié)提出一種新的方法。與之前許多從數(shù)論知識(shí)出發(fā)的構(gòu)造法不同，本節(jié)所提出的構(gòu)造法則是基于圖論的。由于該方法借助了超立方體圖的概念，因此，首先介紹超立方體圖的定義[15]如下：

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

下圖展示了一個(gè)四維的超立方體圖：

以下詳細(xì)介紹一種基于圖論的n階Hadamard矩陣構(gòu)造法。構(gòu)造法的共分為以下三個(gè)步驟：

第一步，構(gòu)造一個(gè)具有n個(gè)頂點(diǎn)的超立方體圖G。

第二步，對(duì)超立方體圖G上任意兩個(gè)點(diǎn)xi和xj，計(jì)算它們之間的圖上最短路徑距離dij。（不失一般性，本文規(guī)定超立方體圖上的每條邊長(zhǎng)度均為1。）

第三步，根據(jù)第二步的計(jì)算結(jié)果，按照公式（6）設(shè)置矩陣H中的每一個(gè)元素的值。

至此，矩陣H即為所要構(gòu)造的Hadamard矩陣。

4 構(gòu)造舉例

本節(jié)以二維超立方體圖為例，展示如何構(gòu)造出四階Hadamard矩陣。

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

接著，可按照?qǐng)D論方法計(jì)算得到如下的最短距離矩陣d：

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

通過(guò)計(jì)算HHT，不難驗(yàn)證該矩陣確為四階Hadamard矩陣。

與此類似地，我們可以根據(jù)圖1構(gòu)造出十六階的Hadamard矩陣如下（為了節(jié)省篇幅，+1縮寫(xiě)為“+”號(hào)，-1 縮寫(xiě)為“-”號(hào)）：

5 結(jié)束語(yǔ)

本文針對(duì)Hadamard矩陣的構(gòu)造問(wèn)題提出了一種新的基于圖論的構(gòu)造方法，并通過(guò)實(shí)例展示了這種構(gòu)造方法的可行性。不可避免地，與之前提出的所有構(gòu)造方法一樣，本文所提出構(gòu)造方法也只能在某些特定階數(shù)下有效。因此，本文的下一步工作是考慮將該方法嘗試在階數(shù)上進(jìn)行推廣或者是考慮采用其他圖結(jié)構(gòu)來(lái)派生出相應(yīng)的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] 喬陽(yáng)，潘志斌，喬瑞萍，李東平，蔡騁.基于Hadamard變換和矢量分割的快速搜索算法[J].2009,14(11)：2269-2275.

[5] 尹安容,謝湘,匡鏡明.Hadamard糾錯(cuò)碼結(jié)合支持向量機(jī)在多分類問(wèn)題中的應(yīng)用[J].電子學(xué)報(bào),2008,36(1)：122-126.

[6] 夏戈明,黃遵國(guó),王志英.基于對(duì)稱平衡不完全區(qū)組設(shè)計(jì)的無(wú)線傳感器網(wǎng)絡(luò)密鑰預(yù)分配方案 [J].計(jì)算機(jī)研究與發(fā)展,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] 沈?yàn)?組合設(shè)計(jì)理論 (第一版)[M].上海：上海交通大學(xué)出版社,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.