阿達馬矩陣

在數學中，阿達馬矩陣（英語：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.