Paley construction

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.

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).

Quadratic character and Jacobsthal matrix

The quadratic character χ("a") indicates whether the given finite field element "a" is a perfect square. Specifically, χ(0)=0, χ("a") = 1 if "a"="b"2 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

:Q = egin{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 "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. 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.

Paley construction I

If "q" is congruent to 3 (mod 4) then

:H=I+egin{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"+"H"T=2"I".

Paley construction II

If "q" is congruent to 1 (mod 4) then the matrix obtained by replacing all 0 entries in

:egin{bmatrix}0 & j^T\j & Qend{bmatrix}

with the matrix

:egin{bmatrix}1 & -1\-1 & -1end{bmatrix}

and all entries ±1 with the matrix

:pmegin{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) obtainedby adjoining a root of an irreducible quadratic. Different irreducible quadratics produce equivalent 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 = egin{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--111 111-11 11---- ----111- 1---1- 1--1-1 -1-11-11 11111- --11-- 11----1- 1-1--- -11--1 1--1-1

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

11 ----11 --11-- 1-11111- -1-11- -11--1 --1-1-11 11---- ----11 111-111- 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 tensor product 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,

:H_2 = egin{bmatrix}1 & 1 \1 & -1 end{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 scriptstyle m ,equiv, 0 mod 4 for "m" < 668.

References

* cite journal
last = Paley
first = R.E.A.C.
authorlink = Raymond Paley
title = On orthogonal matrices
journal = J. Math. Phys.
volume = 12
issue =
pages = 311&ndash;320
publisher =
location =
date = 1933
url =
doi =
id =
accessdate =
*
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Paley graph — infobox graph name = Paley graph image caption = The Paley graph of order 13 namesake = Raymond Paley vertices = edges = chromatic number = chromatic index = properties = Strongly regularIn mathematics, and specifically graph theory, Paley graphs …   Wikipedia

  • Reid Paley — (* in Brooklyn, New York City) ist ein US amerikanischer Rockmusiker. Er sang zunächst für eine Band namens The Five, die er in den 1980ern in Pittsburgh und Boston gegründet hatte. Er trat später solo auf, begleitete seinen Gesang mit einer… …   Deutsch Wikipedia

  • Edward Graham Paley — (1823 1895) was an architect based in Lancaster, England. He designed a number of the more notable buildings in that city and in the surrounding counties. A clergyman’s son from Easingwold, Yorkshire, and a grandson of the philosopher William… …   Wikipedia

  • Graphe de Paley — Le graphe de Paley d ordre 13 modifier  …   Wikipédia en Français

  • William Paley — Pour les articles homonymes, voir Paley (homonymie). William Paley William Paley (juillet 1743 à Peterborough – 25 mai 1805 à Bishopwearmouth) est un …   Wikipédia en Français

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Conference matrix — In mathematics, a conference matrix (also called a C matrix) is a square matrix C with 0 on the diagonal and +1 and −1 off the diagonal, such that CTC is a multiple of the identity matrix I. Thus, if the matrix has order n, CTC = (n−1)I …   Wikipedia

  • Watchmaker analogy — Part of a series of articles on Intelligent design …   Wikipedia

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • Whewell’s philosophy of science and ethics — Struan Jacobs ON SCIENCE Introduction Among the most prodigious of English minds of the nineteenth century, William Whewell (1794–1866) was at various times, and among other things, philosopher, intellectual historian, scientist, educationist,… …   History of philosophy

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”