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 an 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 $\scriptstyle m\,\equiv \,0\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.