Number Theory: An Introduction to Mathematics

244 V Hadamard’s Determinant Problem

Proof We may assume det(AtA)=0 and thusm≤n.ThenAtA=G=(γjk)is a
positive definite real symmetric matrix. For allj,k,

γjk=α 1 jα 1 k+···+αnjαnk

is an integer andγjj=n. Moreoverγjkis odd for allj,k, being the sum of an odd
number of±1’s. Hence the matrixGsatisfies the hypotheses of Proposition 16 with
α=n−1andβ=1. Everything now follows from Proposition 16, except for the
remark that if equality holds we must haven≡1 mod 4.
But ifG =(n− 1 )Im+Jm,thenγjk=1forj=k.Itnowfollows,bythe
argument used in the proof of Proposition 5, that any two distinct columns ofAhave
the same entries in exactly (n+ 1 )/2 rows, and any three distinct columns ofAhave
the same entries in exactly(n+ 3 )/4 rows. Thusn≡1 mod 4.

Even ifn≡1 mod 4 there is no guarantee that that the upper bound in Propo-
sition 18 is attained. However the question may be reduced to the existence of
H-matrices ifm =n. For supposem ≤n−1 and there exists an(n− 1 )×m
H-matrixB. If we put

A=

[

B

em

]

,

whereemagain denotes a row ofm1’s, thenAtA=(n− 1 )Im+Jm.
On the other hand ifm=n, then equality in Proposition 18 can hold only under
very restrictive conditions. For in this case

(detA)^2 =detAtA=(n− 1 )n−^1 ( 2 n− 1 )

and, sincenis odd, it follows that 2n−1 is the square of an integer. It is an open
question whether the upper bound in Proposition 18 is always attained whenm=n
and 2n−1 is a square. However the nature of an extremal matrix, if one exists, can be
specified rather precisely:

Proposition 19If A=(αjk)is an n×n matrix with n> 1 odd andαjk=± 1 for all
j,k, then

det(AtA)≤(n− 1 )n−^1 ( 2 n− 1 ).

Moreover if equality holds, then n≡1mod4, 2 n− 1 =s^2 for some integer s and,
after changing the signs of some rows and columns of A, the matrix A must satisfy

AtA=(n− 1 )In+Jn, AJn=sJn.

Proof By Proposition 18 and the preceding remarks, it only remains to show that if
there exists anAsuch thatAtA=(n− 1 )In+Jnthen, by changing the signs of some
rows, we can ensure that alsoAJn=sJn.
Since det(AAt)=det(AtA), it follows from Proposition 18 that there exists a
diagonal matrixDwithD^2 =Insuch that

DAAtD=(n− 1 )In+Jn=AtA.