Number Theory: An Introduction to Mathematics

230 V Hadamard’s Determinant Problem

Proof We are going to construct inductively mutually orthogonal vectorsw 1 ,...,wm
such thatwkis a linear combination ofv 1 ,...,vkin which the coefficient ofvkis 1
( 1 ≤k≤m).Takew 1 =v 1 and supposew 1 ,...,wk− 1 have been determined. If we
take

wk=vk−α 1 w 1 −···−αk− 1 wk− 1 ,

whereαj =〈vk,wj〉,then〈wk,wj〉= 0 ( 1 ≤ j<k).Moreover,wk =0, since
v 1 ,...,vkare linearly independent. (This is the same process as in§10 of Chapter I,
but without the normalization.)
IfBis the matrix with columnsw 1 ,...,wmthen, by construction,

BtB=diag[δ 1 ,...,δm]

is a diagonal matrix with diagonal entriesδk=‖wk‖^2 andAT=Bfor some upper
triangular matrixTwith 1’s in the main diagonal. Since detT=1, we have

det(AtA)=det(BtB)=

∏m

k= 1

‖wk‖^2.

But

‖vk‖^2 =‖wk‖^2 +|α 1 |^2 ‖w 1 ‖^2 +···+|αk− 1 |^2 ‖wk− 1 ‖^2

and hence‖wk‖^2 ≤‖vk‖^2 , with equality only ifwk=vk. The result follows.

Corollary 4Let A=(αjk)be an n×m real matrix such that|αjk|≤ 1 for all j,k.
Then

det(AtA)≤nm,

with equality if and only ifαjk=± 1 for all j,k and AtA=nIm.

Proof We may assume that the columns of A are linearly independent, since
otherwise det(AtA)=0. Ifvkis thek-th column ofA,then‖vk‖^2 ≤n, with equality
if and only if|αjk|=1for1≤j≤n. The result now follows from Proposition 3.

Ann×mmatrixA=(αjk)will be said to be anH-matrixifαjk=±1forallj,k
andAtA=nIm. If, in addition,m=nthenAwill be said to be aHadamard matrix
oforder n.
IfAis ann×mH-matrix, thenm≤n.Furthermore,ifAis a Hadamard matrix
of ordernthen, for anym<n, the submatrix formed by the firstmcolumns ofAis an
H-matrix. (This distinction betweenH-matrices and Hadamard matrices is con-
venient, but not standard. It is an unproven conjecture that anyH-matrix can be
completed to a Hadamard matrix.)
The transpose Atof a Hadamard matrixAis again a Hadamard matrix, since
At =nA−^1 commutes withA.The1×1 unit matrix is a Hadamard matrix, and
so is the 2×2matrix