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 modulo 4. They are commonly known as Paley type I (for q congruent to 3 mod 4) and Paley type II (for q congruent to 1 mod 4).

Quadratic character and Jacobsthal matrix

Let q be a power of an odd prime. In the finite field GF(q) the quadratic character χ(a), which for prime q is the Legendre symbol, indicates whether the element a is zero, a non-zero square, or a non-square:

${\displaystyle \chi (a)={\begin{cases}0&{\text{if }}a=0\\1&{\text{if }}a=b^{2}{\text{ for some non-zero }}b\in \mathrm {GF} (q)\\-1&{\text{if }}a{\text{ is not the square of any element in }}\mathrm {GF} (q).\end{cases}}}$

For example, in GF(7) the non-zero squares are 1 = 1² = 6², 4 = 2² = 5², and 2 = 3² = 4². 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 elements of GF(q) 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

${\displaystyle 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. The first of these follows from the character sum

${\displaystyle \sum _{z\in \mathrm {GF} (q)}\chi (z-x)\chi (z-y)={\begin{cases}q-1&{\text{if }}x=y\\-1&{\text{if }}x\neq y.\end{cases}}}$

Transposing exchanges the two indices, so Q^T = χ(−1)Q = (−1)^{(q − 1)/2}Q. 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. When q is a prime number and rows and columns are indexed by field elements in the usual 0, 1, 2, … order, Q is a circulant matrix. That is, each row is obtained from the row above by cyclic permutation.

Conference matrices

A conference matrix of size n is an n × n matrix C with zero diagonal and entries ±1 off the diagonal satisfying CC^T = (n − 1)I_n. Bordering the Jacobsthal matrix gives one of size q + 1, the sign of the border being determined by whether Q is symmetric or skew-symmetric. Throughout, j denotes the all-1 column vector of length q.

If q is congruent to 3 mod 4, let

${\displaystyle C_{-}={\begin{bmatrix}0&j^{T}\\-j&Q\end{bmatrix}}.}$

Then C₋ is skew-symmetric and C₋C₋^T = qI_q+1. If q is congruent to 1 mod 4, let

${\displaystyle C_{+}={\begin{bmatrix}0&j^{T}\\j&Q\end{bmatrix}}.}$

Then C₊ is symmetric and C₊² = qI_q+1. These two matrices are the skew-symmetric and symmetric Paley conference matrices. Each Paley construction turns one of them into a Hadamard matrix, which separates the computation in GF(q) from the final passage to a ±1 matrix.

Paley construction I

If q is congruent to 3 mod 4 then

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

is a Hadamard matrix of size q + 1, where I is the (q+1)×(q+1) identity matrix. Since C₋ is skew-symmetric with C₋C₋^T = qI, it follows that HH^T = (I + C₋)(I − C₋) = (q + 1)I. The matrix H is a skew Hadamard matrix, which means it satisfies H + H^T = 2I.

Paley construction II

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

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

with the matrix

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

and all entries ±1 with the matrix

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

is a Hadamard matrix of size 2(q + 1). It is a symmetric Hadamard matrix.

Examples

Applying Paley Construction I to the Jacobsthal matrix for GF(7), one produces the 8 × 8 Hadamard matrix,

${\displaystyle {\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}}.}$

For an example of the Paley II construction when q is a prime power rather than a prime number, consider GF(9). This is an extension field of GF(3) obtained by adjoining a root of an irreducible quadratic. Different irreducible quadratics produce isomorphic fields. Choosing x²+x−1 and letting a be a root of this polynomial, the nine elements of GF(9) may be written 0, 1, −1, a, a+1, a−1, −a, −a+1, −a−1. The non-zero squares are 1 = (±1)², −a+1 = (±a)², a−1 = (±(a+1))², and −1 = (±(a−1))². The Jacobsthal matrix is

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

It is a symmetric matrix consisting of nine 3 × 3 circulant blocks. Paley Construction II produces the symmetric 20 × 20 Hadamard matrix,

1- 111111 111111 111111
-- 1-1-1- 1-1-1- 1-1-1-

11 1-1111 ----11 --11--
1- --1-1- -1-11- -11--1
11 111-11 11---- ----11
1- 1---1- 1--1-1 -1-11-
11 11111- --11-- 11----
1- 1-1--- -11--1 1--1-1

11 --11-- 1-1111 ----11
1- -11--1 --1-1- -1-11-
11 ----11 111-11 11----
1- -1-11- 1---1- 1--1-1
11 11---- 11111- --11--
1- 1--1-1 1-1--- -11--1

11 ----11 --11-- 1-1111
1- -1-11- -11--1 --1-1-
11 11---- ----11 111-11
1- 1--1-1 -1-11- 1---1-
11 --11-- 11---- 11111-
1- -11--1 1--1-1 1-1---

Related combinatorial objects

The matrix Q also describes several other objects named after Paley. If q is congruent to 1 mod 4, then

${\displaystyle A={\tfrac {1}{2}}\left(Q+J-I_{q}\right)}$

has zero diagonal and entries 0 and 1, and is the adjacency matrix of the Paley graph on GF(q), in which two field elements are joined when their difference is a square. Here I_q and J are the q × q identity and all-1 matrices. If q is congruent to 3 mod 4 the same rule orients edges rather than creating them: exactly one of x − y and y − x is a square, because −1 is a non-square, and directing an edge from x to y whenever x − y is a square gives the Paley tournament.

Negating rows and columns of a Hadamard matrix again gives a Hadamard matrix, so a matrix from Paley construction I may be normalized to have its first row and first column consist of 1s. Deleting that row and column and replacing each −1 by 0 then gives the incidence matrix of a symmetric Hadamard 2-design with parameters 2-(q, (q − 1)/2, (q − 3)/4), the design counterpart of the difference set formed by the non-zero squares of GF(q). For q = 11 this design is the Paley biplane.

The Hadamard conjecture

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

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

Hadamard matrices of every permissible size up to 100 except for 92 are produced. Continuing to 200, the permissible sizes not obtainable in this way are 92, 116, 156, 172, 184, and 188.^[1] In his 1933 paper, Paley says “It seems probable that, whenever m is divisible by 4, it is possible to construct an orthogonal matrix of order m composed of ±1, but the general theorem has every appearance of difficulty.” Paley used "orthogonal" in the sense then common, meaning a square matrix with mutually orthogonal rows, rather than one normalized so that A^TA = I. This appears to be the first published statement of the Hadamard conjecture. A matrix of size 92 was eventually constructed by Baumert, Golomb, and Hall, using a construction due to Williamson combined with a computer search.^[1] As of 2025, Hadamard matrices are known to exist for every size ${\displaystyle m\,\equiv \,0\mod 4}$ with m < 668, and 668 is the smallest permissible size for which none has been constructed.^[2]

Generalizations and invariants

The Paley matrices remain a standard source of examples in algebraic combinatorics. Goldberger and Dula placed the Paley conference matrices and the construction I matrices in a wider family of cohomology-developed matrices, built from low-dimensional group cohomology together with an automorphism action.^[3] Sin determined the Smith normal form of every construction II matrix: for q congruent to 1 mod 4 the invariant factors are 1, followed by q copies of 2, then q copies of q + 1, and finally 2(q + 1).^[4]

Krčadinac, Pavčević and Tabak extended the quadratic-character construction to three-dimensional Hadamard matrices, obtaining an array of size q + 1 for every odd prime power q; when q is congruent to 3 mod 4, its two-dimensional layers are equivalent to construction I matrices.^[5]

Cati and Pasechnik implemented both constructions in a reproducible database of Hadamard matrices in SageMath. Relating the reach of the method to Riesel numbers, they also showed that no symmetric or skew-symmetric Paley-type construction has size 2^m × 509203 for any m, a limitation of the constructions rather than a statement about the existence of Hadamard matrices of those sizes.^[2]

See also

• Quadratic residue code

References