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. 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). The quadratic character χ(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 askew-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. If q is congruent to 3 (mod 4) then 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. If q is congruent to 1 (mod 4) then the matrix obtained by replacing all 0 entries in