Paley Construction

The type I Paley construction produces Hadamard matrices using a finite field GF(), where is a prime number with and is an odd positive integer. Choose a primitive element of the finite field. Color white the zero element and all nonzero quadratic residues, namely the even powers , , ..., . Color the other field elements and the border symbol black. For example,

(1)

is of this form with and . Since , we are dealing with GF(11), so pick and compute its residues (mod 11), which are

			(2)
			(3)
			(4)
			(5)
			(6)
			(7)
			(8)
			(9)
			(10)
			(11)
			(12)

Picking the even powers of and adding 0 gives 0, 1, 3, 4, 5, 9, which should then be colored in the matrix obtained by writing out the residues increasing to the left and up along the border (0 through , followed by ), then adding horizontal and vertical coordinates to get the residue to place in each square.

[infty infty infty infty infty infty infty infty infty infty infty infty; 10 0 1 2 3 4 5 6 7 8 9 infty; 9 10 0 1 2 3 4 5 6 7 8 infty; 8 9 10 0 1 2 3 4 5 6 7 infty; 7 8 9 10 0 1 2 3 4 5 6 infty; 6 7 8 9 10 0 1 2 3 4 5 infty; 5 6 7 8 9 10 0 1 2 3 4 infty; 4 5 6 7 8 9 10 0 1 2 3 infty; 3 4 5 6 7 8 9 10 0 1 2 infty; 2 3 4 5 6 7 8 9 10 0 1 infty; 1 2 3 4 5 6 7 8 9 10 0 infty; 0 1 2 3 4 5 6 7 8 9 10 infty]

(13)

To construct , consider the representations . For the type I construction, use the first form, with and . We therefore use GF(19), and color 9 residues plus 0 white.

Now consider a more complicated case. For , the only form having is the first, so use the GF() field. Take as the modulus the irreducible polynomial , written 1021. A four-digit number can always be written using only three digits, since and . Now look at the moduli starting with 10, where each digit is considered separately. Then