Hadamard Matrix

Posted on Tue 06 March 2018 in Linear Algebra

簡介

Hadamard matrix 是一種只包含$(-1,+1)$的矩陣，其特性是取任兩行或是列放在一起比較，則會有一半是同號，另一半則是不同號。
當要畫出該矩陣時，定義$+1$代表黑色，而$-1$代表白色。

${n \times n}$的 Hadamard matrix $H_n$會有$n \frac{n(n-1)}{2}$個$(-1)$方塊以及$\frac{n(n+1)}{2}$個$(+1)$的方塊。
令$H_n$為$n$階的 Hadamard matrix，則其定義為：

$$H_n{H_n}^T=nI_n,$$

其中$I_n$為$n \times n$的單位矩陣。

假設$H_n$為$n$階的 Hadamard matrix，則可以藉由分區矩陣：

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

來形成$2n$階的的 Hadamard matrix，這個方法被稱為 Sylvester's construction，對於$2\leqslant k \in N$，其通式為：

$$H_{2^k}=\begin{bmatrix} H_{2^{k-1}} & H_{2^{k-1}} \\ H_{2^{k-1}} & -H_{2^{k-1}} \end{bmatrix}=H_2 \otimes H_{2^{k-1}},$$

其中$\otimes$為 Kronecker product。

在 Scipy 的函式庫有用 Sylvester’s construction 實作，輸入必須為$2$的次方整數，回傳$n$階的 Hadamard matrix，以下為文件中的範例：

import scipy as sp
from scipy.linalg import hadamard
hadamard(4)

其輸出為：

array([[ 1,  1,  1,  1],
        [ 1, -1,  1, -1],
        [ 1,  1, -1, -1],
        [ 1, -1, -1,  1]])

若根據定義將其圖形化出：

import matplotlib.pyplot as plt
H = hadamard(4)
H = -H

plt.figure
plt.imshow(H, 'gray', origin='lower')
plt.show()

hadamard