Paley's theorem
Encyclopedia
In mathematics
, the Paley construction is a method for constructing Hadamard matrices
using finite field
s. 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).
χ(a) indicates whether the given finite field element a is a perfect square. Specifically, χ(0) = 0, χ(a) = 1 if a = b2 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 = 12 = 62, 4 = 22 = 52, and 2 = 32 = 42. 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
The Jacobsthal matrix has the properties QQT = 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
. When q is a prime number, Q is a circulant matrix
. That is, each row is obtained from the row above by cyclic permutation.
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. The matrix H is a skew Hadamard matrix, which means it satisfies H+HT = 2I.
with the matrix
and all entries ±1 with the matrix
is a Hadamard matrix of size 2(q + 1). It is a symmetric Hadamard matrix.
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 equivalent fields. Choosing x2+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
It is a symmetric matrix consisting of nine 3×3 circulant blocks. Paley Construction II produces the symmetric 20×20 Hadamard matrix,
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,
Hadamard matrices of every allowed size up to 100 except for 92 are produced. 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.” 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. Currently, Hadamard matrices have been shown to exist for all
for m < 668.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Paley construction is a method for constructing Hadamard matrices
Hadamard matrix
In mathematics, an Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal...
using finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
s. The construction was described in 1933 by the English
England
England is a country that is part of the United Kingdom. It shares land borders with Scotland to the north and Wales to the west; the Irish Sea is to the north west, the Celtic Sea to the south west, with the North Sea to the east and the English Channel to the south separating it from continental...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Raymond Paley
Raymond Paley
Raymond Edward Alan Christopher Paley was an English mathematician. Paley was born in Bournemouth, England. He was educated at Eton. From there he entered Trinity College, Cambridge where he showed himself the most brilliant student among a remarkable collection of fellow undergraduates...
.
The Paley construction uses quadratic residues in a finite field GF(q) where q is a power of an odd prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
. 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 characterCharacter (mathematics)
In mathematics, a character is a special kind of function from a group to a field . There are at least two distinct, but overlapping meanings...
χ(a) indicates whether the given finite field element a is a perfect square. Specifically, χ(0) = 0, χ(a) = 1 if a = b2 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 = 12 = 62, 4 = 22 = 52, and 2 = 32 = 42. 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
The Jacobsthal matrix has the properties QQT = 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
Skew-symmetric matrix
In mathematics, and in particular linear algebra, a skew-symmetric matrix is a square matrix A whose transpose is also its negative; that is, it satisfies the equation If the entry in the and is aij, i.e...
. When q is a prime number, Q is a circulant matrix
Circulant matrix
In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. In numerical analysis, circulant matrices are important because they are diagonalized by a discrete Fourier transform, and hence...
. That is, each row is obtained from the row above by cyclic permutation.
Paley construction I
If q is congruent to 3 (mod 4) thenis 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. The matrix H is a skew Hadamard matrix, which means it satisfies H+HT = 2I.
Paley construction II
If q is congruent to 1 (mod 4) then the matrix obtained by replacing all 0 entries inwith the matrix
and all entries ±1 with the matrix
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,
11111111
-1--1-11
-11--1-1
-111--1-
--111--1
-1-111--
--1-111-
---1-111.
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
Field extension
In abstract algebra, field extensions are the main object of study in field theory. The general idea is to start with a base field and construct in some manner a larger field which contains the base field and satisfies additional properties...
of GF(3) obtained
by adjoining a root of an irreducible quadratic
Irreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
. Different irreducible quadratics produce equivalent fields. Choosing x2+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
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 Hadamard conjecture
The size of a Hadamard matrix must be 1, 2, or a multiple of 4. The Kronecker productKronecker product
In mathematics, the Kronecker product, denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It gives the matrix of the tensor product with respect to a standard choice of basis. The Kronecker product should not be confused with the usual matrix...
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,
Hadamard matrices of every allowed size up to 100 except for 92 are produced. 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.” This appears to be the first published statement of the Hadamard conjecture. A matrix of size 92 was eventually constructed by Baumert, Golomb
Solomon W. Golomb
Solomon Wolf Golomb is an American mathematician and engineer and a professor of electrical engineering at the University of Southern California, best known to the general public and fans of mathematical games as the inventor of polyominoes, the inspiration for the computer game Tetris...
, and Hall
Marshall Hall (mathematician)
Marshall Hall, Jr. was an American mathematician who made contributions to group theory and combinatorics.- Career :...
, using a construction due to Williamson combined with a computer search. Currently, Hadamard matrices have been shown to exist for all
for m < 668.