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)

\begin{align} \quad D = \{ 1, 2, 4 \} \end{align}

The set of all translates of $D$ are:

(2)

\begin{align} \quad \mathrm{Dev} (D) = \{ \underbrace{\{ 1, 2, 4 \}}_{D}, \underbrace{\{ 2, 3, 5 \}}_{D+1}, \underbrace{\{3, 4, 6 \}}_{D+2}, \underbrace{\{0, 4, 5 \}}_{D+3}, \underbrace{\{ 1, 5, 6 \}}_{D+4}, \underbrace{\{0, 2, 6 \}}_{D+5}, \underbrace{\{0, 1, 3 \}}_{D+6} \} \end{align}

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)

\begin{align} \quad H* = \begin{bmatrix} h_{0,0} & h_{0,1} & h_{0,2} & h_{0,3} & h_{0,4} & h_{0,5} & h_{0,6} \\ h_{1,0} & h_{1,1} & h_{1,2} & h_{1,3} & h_{1,4} & h_{1,5} & h_{1,6} \\ h_{2,0} & h_{2,1} & h_{2,2} & h_{2,3} & h_{2,4} & h_{2,5} & h_{2,6} \\ h_{3,0} & h_{3,1} & h_{3,2} & h_{3,3} & h_{3,4} & h_{3,5} & h_{3,6} \\ h_{4,0} & h_{4,1} & h_{4,2} & h_{4,3} & h_{4,4} & h_{4,5} & h_{4,6} \\ h_{5,0} & h_{5,1} & h_{5,2} & h_{5,3} & h_{5,4} & h_{5,5} & h_{5,6} \\ h_{6,0} & h_{6,1} & h_{6,2} & h_{6,3} & h_{6,4} & h_{6,5} & h_{6,6} \\ \end{bmatrix} = \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 \\ \end{bmatrix} \end{align}

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)

\begin{align} \quad H_{8 \times 8} = \begin{bmatrix} 1_{1 \times 1} & 1_{1 \times 7} \\ 1_{7 \times 1} & H*_{7 \times 7} \end{bmatrix} = \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} \end{align}

It can be verified that $H$ is indeed a Hadamard matrix as $H H^T = 8I_8$.