Paley construction

In mathematics, the Paley construction is a method for constructing Hadamard matrices using finite fields. The construction was described in 1933 by the English mathematician Raymond Paley, although a version of it was already known to Scarpis.

The Paley construction uses quadratic residues in a finite field $GF(q)$ where $q$ is a power of an odd prime number. There are two versions of the construction depending on whether $q$ is congruent to 1 or 3 (mod 4).

Construction I

If $q$ is congruent to 3 (mod 4) the Paley construction produces a Hadamard matrix of size $q+1$.

Construction II

If $q$ is congruent to 1 (mod 4) the Paley construction produces a Hadamard matrix of size $2(q+1)$.

The Hadamard conjecture

The size of a Hadamard matrix must be 1, 2, or a multiple of 4. The tensor product of two Hadamard matrices of sizes $m$ and $n$ is a Hadamard matrix of size $mn$. By forming tensor products of matrices from the Paley construction and the 2×2 matrix,

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

Hadamard matrices of every allowed size less than 100 except for 92 are produced. This led Paley to conjecture that Hadamard matrices exist for every size which is a multiple of 4. A matrix of size 92 was eventually constructed by Baumert, Golomb, and Hall, using a construction due to Williamson combined with a computer search. Currently, Hadamard matrices have been shown to exist for all $m\equiv 0\mathrm {\,mod\,} 4$ for $m<668.$

References

• Paley, R.E.A.C. (1933). "On orthogonal matrices". J. Math. Phys. 12: 311–320.
• L. D. Baumert, S. W. Golomb, M. Hall Jr., Discovery of an Hadamard matrix of order 92, Bull. Amer. Math. Soc. 68 (1962) 237-238.