Number Theory: An Introduction to Mathematics

232 V Hadamard’s Determinant Problem

Lemma 6Let C be an n×n matrix, with 0 ’s on the main diagonal and all other
entries 1 or− 1 , such that

CtC=(n− 1 )In.

If C is skew-symmetric (i.e. Ct=−C), then C+I is a Hadamard matrix of order
n, whereas if C is symmetric (i.e. Ct=C), then
[
C+IC−I
C−I −C−I

]

is a Hadamard matrix of order 2 n.

Proposition 7If q is a power of an odd prime, there exists a(q+ 1 )×(q+ 1 )matrix
C with 0 ’s on the main diagonal and all other entries 1 or− 1 , such that

(i)CtC=qIq+ 1 ,
(ii)C is skew-symmetric if q≡3mod4and symmetric if q≡1mod4.

Proof LetFbe a finite field containingqelements. Sinceqis odd, not all elements
ofFare squares. For anya∈F, put

χ(a)=

⎧

⎪⎨

⎪⎩

0ifa= 0 ,

1ifa=0anda=c^2 for somec∈F,

−1ifais not a square.

Ifq=pis a prime, thenFis the field of integers modulopandχ(a)=(a/p)is the
Legendre symbol studied in Chapter III. The following argument may be restricted to
this case, if desired.
Since the multiplicative group ofFis cyclic, we have

χ(ab)=χ(a)χ(b) for alla,b∈F.

Since the number of nonzero elements which are squares is equal to the number which
are non-squares, we also have

∑

a∈F

χ(a)= 0.

It follows that, for anyc=0,
∑

b∈F

χ(b)χ(b+c)=

∑

b= 0

χ(b)^2 χ( 1 +cb−^1 )=

∑

x= 1

χ(x)=− 1.

Let 0=a 0 ,a 1 ,...,aq− 1 be an enumeration of the elements ofFand define a
q×qmatrixQ=(qjk)by

qjk=χ(aj−ak)( 0 ≤j,k<q).

ThusQhas 0’s on the main diagonal and±1’s elsewhere. Also, by what has been said
in the previous paragraph, ifJmdenotes them×mmatrix with all entries 1, then