阿达马矩阵

在数学中，阿达马矩阵（英語：Hadamard matrix）是一種特殊的正交矩陣，具有一些重要的性質和應用。它的特點是每個元素只能是+1或-1，並且每行（或每列）之間的內積為0，表示彼此正交。Hadamard矩陣的大小為2的冪次方，即維度為$2^{n}\times 2^{n}$

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

歷史

阿達瑪矩陣的歷史可以追溯到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.$HH^{\mathrm {T} }=nI_{n}$

這意味著 H 與其轉置矩陣 $H^{\mathrm {T} }$的乘積等於 h 倍的單位矩陣 Ih​。這表明阿達瑪矩陣的行向量是正交的。

2.$|\operatorname {det} (M)|\leq n^{n/2}.$

阿達瑪矩陣的行列式的絕對值等於 h 的 h/2 次方。

3.$HH^{\mathrm {T} }=H^{\mathrm {T} }H$

這表示阿達瑪矩陣是對稱的，即其行向量與列向量之間具有相同的內積關係。

4.阿達瑪矩陣可以通過重新排列行和列以及將行和列乘以 ±1 來變換為其他阿達瑪矩陣：這意味著通過行列的置換和乘以 ±1，可以從一個阿達瑪矩陣生成其他阿達瑪矩陣。

5.通過適當的變換，可以將一個Hadamard矩陣轉換為另一個等價的Hadamard矩陣，但並非所有同階數的Hadamard矩陣都是等價的。然而，所有的Hadamard矩陣都可以轉換為第一行和第一列全部為1的正規化形式。

6.如果 H是階數為 4n的正規化Hadamard矩陣，則除了第一行和第一列外，每一行和每一列包含 2n 個 +1 和 2n 個 -1。

7.阿達瑪矩陣的階數必須為2的次方數

西尔维斯特构造法

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

${\begin{bmatrix}H&H\\H&-H\end{bmatrix}}$

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

$H_{2}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}$(最基本的阿達瑪矩陣，其他阿達瑪矩陣都基於此來建造)

$H_{4}={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}$

$H_{4}={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}$

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

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

不同排列方式的阿達瑪矩陣

根據不同的應用與需求，n值相同的阿達瑪矩陣具有不同的形式，主要根據變號的次數做調整，以8為例子。

分別是:Sequency ordering(用於信號處理)、Dyadic ordering(用於控制系統)、Natural ordering(用於數學計算以及研究)

Sequency ordering

每一行的變號次數依序為0,1,2...7

$H_{8}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&-1&1&1&-1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{bmatrix}}$

Dyadic ordering

每一行的變號次數為 0, 1, 3, 2, 7, 6, 4, 5

$H_{8}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&1&1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\end{bmatrix}}$

Natural ordering

每一行的變號次數為0, 7, 3, 4, 1, 6, 2, 5

若使用Matlab code :hadamard(8)則會得到此矩陣。

$H_{8}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{bmatrix}}$

阿達瑪矩陣的應用

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的阿达马矩阵。雷蒙·巴雷随后给出了任何q+1 阶的阿达马矩阵的方法，其中q 是任何模4为3的质数任意次幂。他也给出了形式为2(q+1)的阿达马矩阵的方法，其中q 是任何模4为1的质数任意次幂。他使用了有限域的办法得出了这些结论。阿达马猜想很可能就是Paley提出的。现在有了更多的构造阿达马矩阵的办法。

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

参考资料

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.