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.

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).

Quadratic character and Jacobsthal matrix

The quadratic character χ(a) indicates whether the given finite field element a is a perfect square or not. Specifically, χ(0)=0, χ(a) = 1 if a=b² for some non-zero finite field element b, and χ(a) = −1 if a is not the square of any finite field element. For example, in GF(7) the non-zero squares are 1² = 6² = 1, 2² = 5² = 4, and 3² = 4² = 2. Hence χ(0) = 0, χ(1) = χ(2) = χ(4) = 1, and χ(3) = χ(5) = χ(6) = −1.

The Jacobsthal matrix Q for GF(q) is the q×q matrix with rows and columns indexed by finite field elements such that the entry in row a and column b is χ(a−b). For example, in GF(7), if the rows and columns of the Jacobsthal matrix are indexed by the field elements 0, 1, 2, 3, 4, 5, 6, then

$Q={\begin{bmatrix}0&-1&-1&1&-1&1&1\\1&0&-1&-1&1&-1&1\\1&1&0&-1&-1&1&-1\\-1&1&1&0&-1&-1&1\\1&-1&1&1&0&-1&-1\\-1&1&-1&1&1&0&-1\\-1&-1&1&-1&1&1&0\end{bmatrix}}.$

The Jacobsthal matrix has the properties QQ^T = qI−J and QJ = JQ = 0 where I is the q×q identity matrix and J is the q×q all-1 matrix. If q is congruent to 1 (mod 4) then −1 is a square in GF(q) which implies that Q is a symmetric matrix. If q is congruent to 3 (mod 4) then −1 is not a square, and Q is a skew-symmetric matrix.

Paley construction I

If q is congruent to 3 (mod 4) then

$H=I+{\begin{bmatrix}0&j^{T}\\-j&Q\end{bmatrix}}$

is a Hadamard matrix of size q + 1. Here j is the all-1 column vector of length q and I is the (q+1)×(q+1) identity matrix.

Paley construction II

If q is congruent to 1 (mod 4) then the matrix obtained by replacing all 0 entries in

${\begin{bmatrix}0&j^{T}\\j&Q\end{bmatrix}}$

with the matrix

${\begin{bmatrix}1&-1\\-1&-1\end{bmatrix}}$

and all entries ±1 with the matrix

$\pm {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}$

is 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 up to 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.