The Construction of Hadamard Matrices from Paley Difference Sets
Recall from the Paley Difference Sets page that if $q = 4n - 1$ is a prime power and if $(\mathbb{Z}_q, +)$ is the additive group of integers modulo $q$ then the corresponding Paley difference set for this group is the subset $D \subset \mathbb{Z}_q$ of nonzero squares modulo $q$.
Remarkably enough, it is possible to construct Hadamard matrices from Paley Difference sets for certain $q$, in particular, when $q = 4n - 1$ and $q$ is prime. The procedure is outlined inthe following algorithm:
Algorithm 1 (The Construction of a Hadamard Matrix from a Paley Difference Set): Let $q = 4n - 1$ and let $q$ be prime. We denote $(\mathbb{Z}_q, +)$ to be the additive group of integers modulo $q$ and $D \subset \mathbb{Z}_q$ the set of nonzero squares modulo $q$. |
---|
Step 1: Obtain $\mathrm{Dev} (D)$, i.e., the set of all translates of $D$. Thus $\mathrm{Dev} (D) = \{ D, D + 1, ..., D + (q - 1) \}$. |
Step 2: Construct a $q \times q$ incidence matrix $H*$ for $\mathrm{Dev} (D)$ where column $j \in \{ 0, 1, ..., q - 1 \}$ represents $D + j \in \mathrm{Dev} (D)$ and $h*_{ij} = \left\{\begin{matrix} +1 & \mathrm{if} i \in D + j\\ -1 & \mathrm{if} i \not \in D + j \end{matrix}\right.$. |
Step 3: Construct a $(q +1) \times (q + 1)$ matrix $H$ as $H_{(q+1)\times(q+1)} = \begin{bmatrix} 1_{1 \times 1} & 1_{1 \times q} \\ 1_{q \times 1} & H*_{q \times q} \end{bmatrix}$ where $1_{1\times 1}$, $1_{1 \times q}$, and $1_{q \times 1}$ denote the matrices whose entries are all $1$s of the respective sizes. The resulting matrix $H$ is a Hadamard matrix. |
Let $q = 7$ ($q = 4(2) - 1$ and $q$ is prime). We use the Algorithm above to construct a Hadamard matrix of order $q + 1 = 8$.
The set of nonzero squares modulo $7$ are:
(1)The set of all translates of $D$ are:
(2)We construct the $q \times q = 7 \times 7$ incidence matrix $H*$ where $h*_{ij} = 1$ if $i \in D + j$ and $h*_{ij} = -1$ if $i \not \in D + j$:
(3)Finally we construct the Hadamard matrix $H = \begin{bmatrix} 1_{1 \times 1} & 1_{1 \times 7} \\ 1_{7 \times 1} & H*_{7 \times 7} \end{bmatrix}$:
(4)It can be verified that $H$ is indeed a Hadamard matrix as $H H^T = 8I_8$.