Paley construction

In mathematics, the Paley construction is a method for constructing Hadamard matrices using finite fields.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 10 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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: \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 2 = 6 2 , 4 = 2 2 = 5 2 , and 2 = 3 2 = 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 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 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 \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 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 C_+ = \begin{bmatrix} 0 & j^T \\ j & Q \end{bmatrix}. Then C + is symmetric and C + 2  = 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 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 \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). 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, \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 2 +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) 2 , −a+1 = (±a) 2 , a−1 = (±(a+1)) 2 , and −1 = (±(a−1)) 2 . The Jacobsthal matrix is 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---

The matrix Q also describes several other objects named after Paley. If q is congruent to 1 mod 4, then 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, 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. 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 T A = 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.

As of 2025, Hadamard matrices are known to exist for every size m \,\equiv\, 0 \mod 4 with m  m  × 509203 for any m, a limitation of the constructions rather than a statement about the existence of Hadamard matrices of those sizes.

See also

Quadratic residue code

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374027378 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001374027378 · captured 1788943762.0 · version history

Cite this page as: encyclopegia.org, “Paley construction”, snapshot enwiki-001374027378. https://encyclopegia.org/a/paley-construction

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.