Paley construction

Paley construction   (Redirected from Paley's theorem) Jump to navigation Jump to search 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).

Contents 1 Quadratic character and Jacobsthal matrix 2 Paley construction I 3 Paley construction II 4 Examples 5 The Hadamard conjecture 6 See also 7 References Quadratic character and Jacobsthal matrix Let q be a power of an odd prime. In the finite field GF(q) the quadratic character χ(a) indicates whether the element a is zero, a non-zero perfect 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 finite field element }}b\-1&{text{if }}a{text{ is not the square of any finite field element.}}end{cases}}} 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 {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&0end{bmatrix}}.} The Jacobsthal matrix has the properties Q QT = q I − J and Q J = J Q = 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 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.

Paley construction I If q is congruent to 3 (mod 4) then {displaystyle H=I+{begin{bmatrix}0&j^{T}\-j&Qend{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. 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 in {displaystyle {begin{bmatrix}0&j^{T}\j&Qend{bmatrix}}} with the matrix {displaystyle {begin{bmatrix}1&-1\-1&-1end{bmatrix}}} and all entries ±1 with the matrix {displaystyle pm {begin{bmatrix}1&1\1&-1end{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, 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 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 {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&0end{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 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 an 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&-1end{bmatrix}},} 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 {displaystyle scriptstyle m,equiv ,0mod 4} for m < 668. See also Paley biplane Paley graph References Paley, R.E.A.C. (1933). "On orthogonal matrices". Journal of Mathematics and Physics. 12: 311–320. doi:10.1002/sapm1933121311. Zbl 0007.10004. L. D. Baumert; S. W. Golomb; M. Hall Jr (1962). "Discovery of an Hadamard matrix of order 92". Bull. Amer. Math. Soc. 68 (3): 237–238. doi:10.1090/S0002-9904-1962-10761-7. F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 47, 56. ISBN 0-444-85193-3. Categories: Matrices

Si quieres conocer otros artículos parecidos a Paley construction puedes visitar la categoría Matrices.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información