Number Theory: An Introduction to Mathematics

2 Hadamard Matrices 231

[

11

1 − 1

]

.

There is one rather simple procedure for constructingH-matrices. IfA=(αjk)is
ann×mmatrix andB=(βi)aq×pmatrix, then thenq×mpmatrix
⎡
⎢
⎢
⎣

α 11 B α 12 B ··· α 1 mB

α 21 B α 22 B ··· α 2 mB

··· ···

αn 1 B αn 2 B ··· αnmB

⎤

⎥

⎥

⎦,

with entriesαjkβi, is called theKronecker productofAandBand is denoted by
A⊗B. It is easily verified that

(A⊗B)(C⊗D)=AC⊗BD

and

(A⊗B)t=At⊗Bt.

It follows directly from these rules of calculation that ifA 1 is ann 1 ×m 1 H-matrix and
A 2 ann 2 ×m 2 H-matrix, thenA 1 ⊗A 2 is ann 1 n 2 ×m 1 m 2 H-matrix. Consequently,
since there exist Hadamard matrices of orders 1 and 2, there also exist Hadamard
matrices of order any power of 2. This was already known to Sylvester (1867).

Proposition 5Let A=(αjk)be an n×m H -matrix. If n> 1 , then n is even and any
two distinct columns of A have the same entries in exactly n/ 2 rows. If n> 2 ,thenn
is divisible by 4 and any three distinct columns of A have the same entries in exactly
n/ 4 rows.

Proof Ifj=k,then

α 1 jα 1 k+···+αnjαnk= 0.

Sinceαijαik=1ifthej-th andk-th columns have the same entry in thei-th row and
=−1 otherwise, the number of rows in which thej-th andk-th columns have the same
entry isn/2.
Ifj,k,are all different, then

∑n

i= 1

(αij+αik)(αij+αi)=

∑n

i= 1

αij^2 =n.

But(αij+αik)(αij+αi)=4ifthej-th,k-th and-th columns all have the same
entry in thei-th row and=0 otherwise. Hence the number of rows in which thej-th,
k-th and-th columns all have the same entry is exactlyn/4.

Thus the ordernof a Hadamard matrix must be divisible by 4 ifn >2. It is
unknown if a Hadamard matrix of ordernexists for everyndivisible by 4. However,
it is known forn≤424 and for several infinite families ofn. We restrict attention here
to the family of Hadamard matrices constructed by Paley (1933).
The following lemma may be immediately verified by matrix multiplication.