TOPICS
Search

Paley Construction


Hadamard matrices H_n can be constructed using finite field GF(p^m) when p=4l-1 and m is odd. Pick a representation r relatively prime to p. Then by coloring white |_(p-1)/2_| (where |_x_| is the floor function) distinct equally spaced residues mod p (r^0, r, r^2, ...; r^0, r^2, r^4, ...; etc.) in addition to 0, a Hadamard matrix is obtained if the powers of r (mod p) run through <|_(p-1)/2_|. For example,

 n=12=11^1+1=2(5+1)=2^2(2+1)
(1)

is of this form with p=11=4×3-1 and m=1. Since m=1, we are dealing with GF(11), so pick p=2 and compute its residues (mod 11), which are

p^0=1
(2)
p^1=2
(3)
p^2=4
(4)
p^3=8
(5)
p^4=16=5
(6)
p^5=10
(7)
p^6=20=9
(8)
p^7=18=7
(9)
p^8=14=3
(10)
p^9=6
(11)
p^(10)=12=1.
(12)

Picking the first |_11/2_|=5 residues and adding 0 gives: 0, 1, 2, 4, 5, 8, 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 p-1, followed by infty), 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 H_(20), consider the representations n=20=19+1=2(3^2+1)=2^2(2^2+1). Only the first form can be used, with p=19=4×5-1 and m=1. We therefore use GF(19), and color 9 residues plus 0 white.

Now consider a more complicated case. For n=28=3^3+1=2(13+1), the only form having p=4l-1 is the first, so use the GF(3^3) field. Take as the modulus the irreducible polynomial x^3+2x+1, written 1021. A four-digit number can always be written using only three digits, since 1000-1021=0012 and 2000-2012=0021. Now look at the moduli starting with 10, where each digit is considered separately. Then

 x^0=1  x^1=10  x^2=100 ; x^3=1000=12  x^4=120  x^5=1200=212 ; x^6=2120=111  x^7=1100=122  x^8=1220=202 ; x^9=2020=11  x^(10)=110  x^(11)=1100=112 ; x^(12)=1120=102  x^(13)=1020=2  x^(14)=20 ; x^(15)=200  x^(16)=2000=21  x^(17)=210 ; x^(18)=2100=121  x^(19)=1210=222  x^(20)=2220=211 ; x^(21)=2110=101  x^(22)=101=22  x^(23)=220 ; x^(24)=2200=221  x^(25)=2210=201  x^(26)=2010=1
(14)

Taking the alternate terms gives white squares as 000, 001, 020, 021, 022, 100, 102, 110, 111, 120, 121, 202, 211, and 221.


See also

Hadamard Graph, Hadamard Matrix, Paley Class, Paley Graph, Paley's Theorem

Explore with Wolfram|Alpha

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 107-109 and 274, 1987.Beth, T.; Jungnickel, D.; and Lenz, H. Design Theory, 2nd ed. rev. Cambridge, England: Cambridge University Press, 1998.Geramita, A. V. and Seberry, J. Orthogonal Designs: Quadratic Forms and Hadamard Matrices. New York: Dekker, 1979. Kitis, L. "Paley's Construction of Hadamard Matrices." http://library.wolfram.com/infocenter/MathSource/499/.

Referenced on Wolfram|Alpha

Paley Construction

Cite this as:

Weisstein, Eric W. "Paley Construction." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PaleyConstruction.html

Subject classifications