Number Theory: An Introduction to Mathematics

3 The Art of Weighing 233

QJq= 0 , QtQ=qIq−Jq.

Furthermore, sinceχ(− 1 )=(− 1 )(q−^1 )/^2 ,Qis symmetric ifq≡1 mod 4 and skew-

symmetric ifq≡3 mod 4. Ifemdenotes the 1×mmatrix with all entries 1, it follows

that the matrix

C=

[

0 eq

±etq Q

]

,

where the±sign is chosen according asq ≡±1 mod 4, satisfies the various

requirements. 

By combining Lemma 6 with Proposition 7 weobtain Paley’s result that, for any

odd prime powerq, there exists a Hadamard matrix of orderq+1ifq≡3 mod 4 and

of order 2(q+ 1 )ifq≡1 mod 4. Together with the Kronecker product construction,

this establishes the existence of Hadamard matrices for all ordersn≡0 mod 4 with

n≤100, exceptn=92.

A Hadamard matrix of order 92 was found by Baumert, Golomb and Hall (1962),

using a computer search and the following method proposed byWilliamson(1944).

LetA,B,C,Dbed×dmatrices with entries±1andlet

H=

⎡

⎢

⎢

⎣

ADBC

−DA−CB

−BC A−D

−C −BD A

⎤

⎥

⎥

⎦,

i.e.H =A⊗I+B⊗i+C⊗ j+D⊗k,wherethe4×4 matricesI,i,j,kare
matrix representations of the unit quaternions. It may be immediately verified thatH
is a Hadamard matrix of ordern= 4 dif

AtA+BtB+CtC+DtD= 4 dId

and

XtY=YtX

for every two distinct matricesX,Yfrom the set{A,B,C,D}. The first infinite class

of Hadamard matrices of Williamson type was found by Turyn (1972), who showed

that they exist for all ordersn= 2 (q+ 1 ),whereqis a prime power andq≡1 mod 4.

Lagrange’s theorem that any positive integer is a sum of four squares suggests that

Hadamard matrices of Williamson type may exist for all ordersn≡0 mod 4.

The Hadamard matrices constructed by Paley are either symmetric or of the form

I+S,whereSis skew-symmetric. It has been conjectured that in fact Hadamard

matrices of both these types exist for all ordersn≡0 mod 4.

3 TheArtofWeighing.........................................

It was observed by Yates (1935) that, if several quantities are to be measured, more

accurate results may be obtained by measuring suitable combinations of them than