Paley construction

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 square, or a non-square:

:

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² = 6², 4 = 2² = 5², and 2 = 3² = 4². 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\; =\; \backslash 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. 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.

If q is congruent to 3 mod 4 then

:$H\; =\; I\; +\; \backslash begin\{bmatrix\}$

0 & j^T \\

-j & Q \end{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 = 2I.

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

:$\backslash begin\{bmatrix\}$

0 & j^T \\

j & Q \end{bmatrix}

with the matrix

:$\backslash begin\{bmatrix\}$

1 & -1 \\

-1 & -1 \end{bmatrix}

and all entries ±1 with the matrix

:$\backslash pm\backslash begin\{bmatrix\}$

1 & 1 \\

1 & -1 \end{bmatrix}

is a Hadamard matrix of size 2(q + 1). It is a symmetric Hadamard matrix.

Applying Paley Construction I to the Jacobsthal matrix for GF(7), one produces the 8 × 8 Hadamard matrix,

:$\backslash 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 equivalent fields. Choosing x²+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)², −a+1 = (±a)², a−1 = (±(a+1))², and −1 = (±(a−1))². The Jacobsthal matrix is

:$Q\; =\; \backslash 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 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,

:$H\_2\; =\; \backslash begin\{bmatrix\}$

1 & 1 \\

1 & -1 \end{bmatrix},

Hadamard matrices of every permissible 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 $m\; \backslash ,\backslash equiv\backslash ,\; 0\; \backslash mod\; 4$ for m < 668.

• Paley biplane
• Paley graph

• {{cite journal

| last = Paley

| first = R.E.A.C.

| author-link = Raymond Paley

| doi = 10.1002/sapm1933121311

| title = On orthogonal matrices

| journal = Journal of Mathematics and Physics

| volume = 12

| pages = 311–320

| year = 1933

| issue = 1–4

| zbl = 0007.10004

}}

• {{cite journal | author=L. D. Baumert |author2=S. W. Golomb |author2-link=Solomon W. Golomb |author3=M. Hall Jr |author3-link=Marshall Hall (mathematician) | title=Discovery of an Hadamard matrix of order 92 | journal=Bull. Amer. Math. Soc. | volume=68 | year=1962 | pages=237–238 | doi=10.1090/S0002-9904-1962-10761-7 | issue=3 | doi-access=free }}
• {{cite book | author=F.J. MacWilliams | author-link=Jessie MacWilliams |author2=N.J.A. Sloane |author-link2=Neil Sloane | title=The Theory of Error-Correcting Codes | url=https://archive.org/details/theoryoferrorcor0000macw | url-access=registration | publisher=North-Holland | year=1977 | isbn=0-444-85193-3 | pages=[https://archive.org/details/theoryoferrorcor0000macw/page/47 47], 56 }}

Category:Matrices (mathematics)