Lecture Notes in
Mathematics
Edited by A. Dold and B. Eckmann
Subseries: USSR
Adviser: L. D. Faddeev, Leningrad

S. S. Agaian

Hadamard Matrices and
Their Applications

Springer-Verlag
Berlin Heidelberg New York Tokyo


www.pdfgrip.com
Author
S.S. Agaian
Computer Center of the Academy of Sciences
Sevak str. 1, Erevan 44, USSR

Consulting Editor
D.Yu, Grigorev
Leningrad Branch of the Steklov Mathematical Institute
Fontanka 27, 191011 Leningrad, D-11, USSR

Mathematics Subject Classification (1980): 05XX; 0 5 B X X
ISBN 3-540-16056-6 Springer-Verlag Berlin Heidelberg New York Tokyo
ISBN 0-387-16056-6 Springer-Verlag New York Heidelberg Berlin Tokyo

This work is subject to copyright.All rights are reserved,whetherthe whole or part of the material

is concerned,specificallythose of translation,reprinting,re-useof illustrations,broadcasting,
reproductionby photocopyingmachineor similarmeans,and storage in data banks. Under
§ 54 of the GermanCopyrightLaw where copies are madefor other than privateuse, a fee is
payableto "VerwertungsgesellschaftWort", Munich.
© by Springer-VerlagBerlin Heidelberg1985
Printed in Germany
Printing and binding:Beltz Offsetdruck, Hemsbach/Bergstr.
2146/3140-543210


www.pdfgrip.com

CONTENTS

Introduction
§ I
Chapter

I

definitions,

CONSTRUCTION
Methods

§3

Some problems

§ 4


New method

2

notations

OF CLASSIC

§2

Chapter

of construction

HADAMARD
for

§6

Construction

of high-dimensional

APPLICATION

OF HADAMARD

3


Hadamard

matrices

and problems

§ 8. H a d a m a r d

matrices

and design

Appendix

1. U N A N S W E R E D

Appendix

2. T A B L E S

References
Subject

........

78

. . . . . . . . 103

Theory


matrices

.134

. . . . . . . . . . . . . . 171

MATRICES

178

(PLANE

OF ORDER

(4n) .180

......................................................

Index

134

. . . . . . . . . . . . . . . . . . 166

BLOCK-SYMMETRIC

HADAMARD

103


...114

.................................

OF BLOCK-CIRCULANT,

AND HIGH-DIMENSIONAL)

49

matrices

information

11

..

....................

theory

of H a d a m a r d

PROBLEMS

of

5

11

........

matrices

MATRICES

Hadamard

MATRICES

matrices

applications

...

........................

§ 7. H a d a m a r d

§ 9. O t h e r

matrices

construction

HADAMARD


Generalized

results

............

for Hadamard

matrices

OF GENERALIZED

MATRICES

Hadamard

of c o n s t r u c t i o n

for H a d a m a r d

CONSTRUCTION

and auxiliary

§ 5

Chapter

1


....................................................

Basic

...................................................

192
216


www.pdfgrip.com

Introduction

The
matics

importance

of

orthouonal

a n d its a p p l i c a t i o n s

matrices

is well known;

(for example,


for c o n s t r u c t i o n

of d i s c r e t e

or o r t h o g o n a l

transformations)

one needs

orthogonal
elements

matrices

and

-I and +I.

and +I are c a l l e d

in p a r t i c u l a r ,

Square

orthogonal

Hadamard


Investigations

of H a d a m a r d

tion

coding,
ction

optimal

out that there

with

the a p p l i c a t i o n s

information
training

(information

detection

compression

are also

through


noise,

fruitful.

configurations,
graphs.

correcting

These

of d i f f e r e n t

Hadamard

matrices

interrelations

objects

using

matele-

of ques-

constru-

Besides


codes,

with

and n o i s e l e s s

such as b l o c k - d e s i g n s ,

gate the p r o p e r t i e s

-I

by n o n - l i n e

configurations

regular

the

of deter-

and with a n u m b e r

of a signal

chanels)

transfer


rent c o m b i n a t o r i a l

strongly

with

of H a d a m a r d

between

ties,

integer

maximum

interrelations

F-square

fast

initially

are

orthogonal

problems


the e l e m e n t s

finding

theory

of m u l t i p l e - a c c e s s

with

with

with a u t o m a t o n

linear

matrices

of

matrices

(for example,

connected

from i n f o r m a t i o n

consideration


orthogonal

mathe-

realizing

connected

Later on it turned out that

waves,

equipments

were

minant).

ctromagnetic

applied

matrices

algebra problems

in q u e s t i o n s

for many


discrete

matrices.

a linear

rices

in m o d e r n

it turned
and diffe-

Latin

finite

square~

geomet-

a l l o w to i n v e s t i -

the analogy

in their

structures.
Recently


a considerable

damard matrices
neralized,

has occured.

high-dimensional)

till now

it is not known

for all

n

divisible

Historically,
Sylvester
Hadamard

who

increase

investigation


Some p r o b l e m s
Hadamard

if there

connected

matrices

exist

are

devoted
with

to Ha-

(classic,

ge-

still unanswered;

Hadamard

matrices

of order


to H a d a m a r d

matrices

was due to

so,
n

by 4.

first work

devoted

in 1867 p r o p o s e d

matrices

of

of order

2 k.

a recurrent

method

In XIX century


for c o n s t r u c t i o n

the f o l l o w i n g

papers

of


www.pdfgrip.com

also appeared:
or p = l ( m o d
order

4)

p+1

is a p r i m e

and p+3,

the f o l l o w i n g
lai,jl ~ M ,

the work of Scarpis

result


ai, j

result

gives

tement

by

4. There

pic u n d e r

discussion

terest

are

some r e a s o n s

This p r o b l e m

1500 papers

that these

are books

surveys

a series

difficulty

torial p r o b l e m s

is the

damard matrices

of order

truction
For many

Hadamard

for H a d a m a r d

has p r o v e d

matrices.

This

matrix".

and


that

is till now
to it.

problem

Ryser

is di-

(1963);

the works

applications

sta-

(so-

unanswered

Introduction

included

of i n t e r e s t i n g


matrix

the reverse

Hadamard

(1970),

have not

lack of u n i f i e d

are a p p l i c a b l e
n

of this p r o b l e m

4n

for all

altho-

to the

to-

it should

of Soviet


stimulating

it is u s u a l l y

necessary

sometimes

using

papers

recurrent

methods

where

introduced.
number

practically
methods.

These m e t h o d s

theory,group
no p a p e r s


in-

by a c o m p u t e r

that the m i n i m a l
is not k n o w n

order

is 268.

. The k n o w n m e t h o d s
"rare"

to develop,

use the

for which

matrices

There

on

n

.
of


are only a few

for H a d a m a r d

following

to c o m b i n a t i o n

sequences

of Ha-

of c o n s -

a direct m e t h o d

access.

combinatorial

was given

combina-

for c o n s t r u c t i o n

of c o n s t r u c t i o n

The list of k n o w n H a d a m a r d


constructed

n

the machine

theory,

devoted

and many other

methods

only to r e l a t i v e l y

construction

tics:

Mnn n/2

is c a l l e d

Hall

where

n

if A = { a i , j } i , j = 1 ,

to assume

devoted

of

in this problem.

A principal

are

to

"Hadamard

4)

i, j, then the a b s o l u t e va-

reach only

or Paley problem)

are over

and also


the

equal

matrix

(1893)

stated that the order of any H a d a m a r d

ugh there

authors

for any

p=3(mod

is an H a d a m a r d

is stated:

to the term

Sylvester

be n o t e d

if


in p a r t i c u l a r

is less or

is also true.

metimes

there

that

the work of H a d a m a r d

is w i t h i n

rise

proving

respectively;

A

In 1933 P a l e y
visible

then

are real numbers


lue of d e t e r m i n a n t
that this b o u n d

number

(1898)

branches
analysis.

matrices

of m a t h e m a There exist

of direct

and r e c u r r e n t

of order

n, n ~ 4000,

in W a l l i s

the e x i s t e n c e

(1978),

where


he n o t e d

of an H a d a m a r d

matrix


www.pdfgrip.com

The k n o w n m e t h o d s
into W i l l i a m s o n ,
methods

of H a d a m a r d

This w o r k p r o v i d e s

results

Plotkin

in the topic.

Hadamard

Specifically,

of c o n s t r u c t i o n


of H a d a m a r d

des,

of c o n s t r u c t i o n

the m e t h o d

realization

The work p r e s e n t e d
§ 2 we will c o n s i d e r
ces u n i t i n g
Whiteman
Wallis

are a r b i t r a r y

propose

a recurrent

of n e w orders.

mard matrices
there e x i s t s
exist

generalize


for e x i s t e n c e

natural

numbers)

method

we will

solve

we will

construct

simple

The m e t h o d

allows

of o r d e r

fusation

of second P l o t k i n

hypothesis)


existence

of two H a d a m a r d

existence

of an H a d a m a r d

In §§ 2 - 4

we will

matrices,

arrays

matrix

of order

Baumert-Hall,
allowing

The block

method

and T - m a t r i c e s

methods


that

there

doesn't

(that

is, the re-

that

ml, m 2

of Hada-

firstly

for w h i c h

and secondly,

of o r d e r

• q2k2

in construction)

to state


this m a t r i x

from the

follows

the

m I • m2/2.

give also r e c u r r e n t

of n e w o r d e r s

matrices.

12

i=I,2

of all orders,

6-codes

construction.

Hada-

gi'


matrices

and r e c u r r e n t

matrices

in this

Hadamard

(sufficiently

matri-

Golay-Turyn,

for an a r b i t r a r y

of

In

and B a u m e r t -

2Sqlkl , 2Sqlkl

generating

of H a d a m a r d


Williamson

of type

D(12,4)

Whiteman

of H a d a m a r d

the direct

a partition

sections.

and s t r e n g t h e n

for c o n s t r u c t i o n

matrix

to a l l o w an

9

combined

a Hadamard


of W i l l i a m s o n

namely,

Besi-

of the computer.

and

to c o n s t r u c t i o n

methods

some n e w

properties.

and has

chapters

gene-

to the q u e s t i o n s

and m e m o r y

from the codes


In § 4 new b l o c k

is p r o p o s e d

3

a theorem allowing

limit

is p a i d

simple

In p a r t i c u l ar ,

problem:

prove

to find a lower

method

methods.

the reverse

m a r d matrices,


(k i

In § 3 we will

and P l o t k i n

section

a new approach

two a b o v e - m e n t i o n e d

method.

must be

of

(classic,

with p r e s c r i b e d

sence of rate

consists

to

and d i s c u s s e s


attention

matrices

in the

approaches.

devoted

matrices

can be d i v i d e d

Paley-Wallis-Whiteman

and J . W a l l i s

a survey of p a p e r s

high-dimensional)

effective

construction

Baumert-Hall-Goethals-Seidel,

and Golay-Turyn,


ralized,

matrix

formulae

Goethals-Seidel,
to c o n s t r u c t
posseses

of c o n s t r u c t i o n
Wallis,

infinite

a definite

Wallis-

classes

universa-


www.pdfgrip.com

lity a l l o w i n g
algorithms


to c o n s t r u c t

for c a l c u l a t i o n

§ 5 is d e v o t e d

existence

of partial

are given,

generalized

matrices

methods

systems.
matrices

conditions

of the

H(p,h)

matrices

fast


Hadamard

(p

of c o n s t r u c t i o n

Hadamard

providing

sums by these

some n e c e s s a r y

Hadamard

recurrent

Fourier

systems

of g e n e r a l i z e d

In p a r t i c u l a r ,

for g e n e r a l i z e d

block-circulant


orthogonal

to i n v e s t i g a t i o n

and B u t s o n problem.

number)

different

is not a prime

of circulant,

of new orders

are ob-

tained.
In § 6 the b l o c k
which

allows

method

to c o n s t r u c t

irregular


Hadamard

the upper

and lower b o u n d s

(classic

new classes

matrices.

of w e i g h t

pressing,

noiseless

noise,

Hadamard

construction

matrices

for c a l c u l a t i o n s
Finally,


delnikov,

where

the

of H a d a m a r d

some u n a n s w e r e d

The author
Yablonskiy

coding,

would

on whose

ries of v a l u a b l e

optimal

linear

and

is given,

density


of

are obtained.
(information

detection

of the

signals

access

leading

is p l a y e d by fast a l g o r i t h m s

part

channels

com-

of m u l t i p l e -

and so on)

transformations.
problems


initiative

notes.

matrices

case

regular

problem

and e x c e s s

some a p p l i c a t i o n s

like to express

V.A.Zinovjev,

of S c h l i c h t a

density

Hadamard

introduce

to a h i g h - d i m e n s i o n a l


of h i g h - d i m e n s i o n a l

A solution

and h i g h - d i m e n s i o n a l )

In §§ 7 - 9 we will

through

is e x t e n d e d

are
his

formulated.
sincere

gratitude

this work was p r e p a r e d

who have

read the m a n u s c r i p t

to S.V.

and to V . M . S i and made


a se-

of


www.pdfgrip.com

Đ

I.

Basic

definitions,

notations

and

auxiliary

results

NOTATIONSã
only

ones

I -


(in c a s e

is a u n i t
of

need

matrix;

the

J

- is

dimension

a

of

square

matrix

matrix
is

containing


indicated

by

a

subscript);

R

It

0 0

...

0

1

0 0

...

1 0

0

0 0

U

=

can

be

000...01
100...01

that

I. F o r

2.

Y2'

"'''
of

[120];~

AI,1
=

A2,1

we


have

every

s such
There

then

Yn

that

Hadamard

Am,2

n;

.-.
-.-

-.-

product

is

an


odd

number,

there

U k,

a matrix

P such

YI

0

...

0

0

0

Y2"'"

0

0


0 0

" " "Yn-1 0

0 0

...

different
T

a matrix

A2,2

(uS) 2=

n

that

PUP*=D

where

=

are


AI,2

k=1,2,...n-1,

exists

length
is

k,

is

n-th

Yn

roots

defined

XI
m
Y

:

A2, m

Am, m


[311 ],

of u n i t y , e n = ( 1 , 1 , . . . , 1 )

a transposition

product

At, m

0

i:I

Am,2

* is a n

(1)

0 0

shown

0

=

0 0


a row-vector

A ~ X

0

...

D

product

...

...

a unique

YI'

0 0

I 0

PROPERTY

and

I


...

01

PROPERTY
exists

I 0

X
m

that

is

sign;

x

is

is

a Kronecker

as
A I ,i


* Xl

A 2 ,i

* Xi

A

, X.
l

m,i

if A = ( a i , j ) ni,j=1,

(2)

B=(bi,~,j=1


www.pdfgrip.com

A * B =

L e t A,

B, C, D be

square


w[4]

=

(-I,

+1)

a Williamson

array

B

C

D

-B

A

-D

C

-C

D


=

Goethals-Seidel

BY[4]

B

BR
A

-CR

DTR

I

a Wallis-Whiteman

AI x BI

WA[4~A2Rx

denotes

A Radon

of o r d e r

B

C
A T -D

-C

DT

A

array

BT

4

~ 1 3 ],

D
C

(6)

-B T
AT

of o r d e r

4

[311],


A1 x B I

A T R x B4

- A 3 R × B3

array

of o r d e r

is d e f i n e d

d<3

and b

p(16)=9

and

p(2ab)=p(2a),

-I and

A

A4R x B 4

a=4c+d,


elements

BTR

A
-B T

(5)

-BTR

A3R x B 3

function

DEFINITION

cTR

A

A2R x B 2

B2

a Wallis

DR


-DTR

-D T -C

denotes

A

CR

-BR

array

=

(4)

A -B

-DR -cTR

denotes

Let

[318],

A


GZ[4]

matrices.

A

-D -C

denotes

4

such

and

(7)

[299].

by e q u a t i o n

is an o d d n u m b e r .

Note

that

p ( m ) = 8 c + 2 d, w h e r e
p(m)=m,


m=2ab,

if m = I , 2 , 4 , 8 ,

if b is an o d d n u m b e r .

1. An H a d a m a r d
+I

(3)

(ai, j • bi,j) ni , j = 1

that

matrix

of o r d e r

m is a m x m m a t r i x

H

m

with


www.pdfgrip.com


H H T = HTH
mm
mm

Expression
every

(8)

is e q u a l

two columns

of rows

to t h e

of matrix

or c o l u m n s

= mI

(8)

m

statement


that every

H m are orthogonal.

of H m a n d m u l t i p l i c a t i o n

two rows

Obviously,

and hence,

permutation

b y -I p r e s e r v e s

this

pro-

perty.
Following
on

(8).

If we a s s u m e

coordinates
nent


geometrical

on these

that row elements

of E u c l i d e a n

d e t H m is

interpretation

m-space

(up t o sign)

vectors.
is p r o d u c t

vertex.

An Hadamard

of

its e d g e s

+I


mxn

is s a i d to be a r e c t a n g u l a r

DEFINITION
damard

3 [120]

matrices,

matrices

with

that

then

determi-

constructed

the v o l u m e

originating

of the p a r a l l e -

f r o m the c o m m o n

type,

if

HT
m,n

m,n

matrix

= ni

H

m,n

+I.

Hadamard

of

-I a n d

matrix,

if

s a i d to be e q u i v a l e n t


P and Q are

Such

consisting

m

H I and H 2 are

if H 2 = P H I Q , w h e r e
-I a n d

(9)

(or i n c o m p l e t e )

Matrices

elements

base,

vector

Sm
T = -S m

2. A r e c t a n g u l a r


H

Hm represent

is s a i d to be of s k e w - s y m m e t r i c

H m = Im+Sm,

DEFINITION

for the e x p r e s s i -

of m-parallelepiped

(8) s h o w s

lengths

matrix

of m a t r i x
orthonormal

the v o l u m e

The p r o p e r t y

lepiped


with

m a y be g i v e n

a Hadamard

Ha-

monomial

permutation

matrix

is s a i d to b e

normalized.
The concept
given
n.

So,

order
in

ce of

n the n u m b e r


1961

for H a d a m a r d

of equivalence

Hall

matrices

3 classes

question

one

and Baumert

has

find

(1961),

ker and Deidel

proved

of order


that

of o r d e r

(1962),

Newman

Hadamard

there

16 a n d

in f o l l o w i n g

Baumert

(1970),

to the q u e s t i o n

of n o n - e q u i v a l e n t

for m a t r i c e s

can

leads


are

matrices

5 classes

for a

of order

of e q u i v a l e n c e

in

1965 he h a s

shown

20.

The b a s i c

results

in t h i s

Rutledge

(1952),


Stiffler

papers:
Wallis

(1971),

of f i n d i n g

and Wallis

Wallis

the e x i s t e n -

(1969),

Bussema-

(1971a) , (1971b) , (1972a),


www.pdfgrip.com

(1972b).
Other
ce,

concepts


weight

Norman
(1977)

and applications

equivalence)

(1976),

Longyear

and Y.Wallis

Let

(V,B)

of e q u i v a l e n c e

one can

find

(1978),

Cooper,

in f o l l o w i n g

Milas

and W a l l i s

of

sets

V={al,a2,

,a v}
" " "

DEFINITION
sign

a. and b l o c k
±

4.

(V,B)

or a B I B - d e s i g n
I. e a c h

block

papers:


equivalen-

Gordon

(1971),

(1978),

Yang

(1977).

be a p a i r

B.cV. e l e m e n t
l

(integral

B

B. are
3

is said
with

incident,

if a.6B..

l
3

to be a b a l a n c e d

parameters

incomplete

V,B,Z,K,S

contains

identical

a i belongs

to the

B={Bi} ci = ]

'

number

block

de-

if


of K - e l e m e n t s ,

3
2. e a c h

element

3. for e a c h
of b l o c k s

containing

A block

design

A set of
parameters
pair

integers

(v,k,s),

[61,

DEFINITION

mutative


that

about

DEFINITION
der

6.[4

1 3

3.

1
E G. is
i=I i

the

is c a l l e d

xi-xj~d(modn)
designs

a difference
there

set w i t h


are p r e c i s e l y

s

.

and

from

set

difference

sets

one

can

designs

A m of o r d e r

-x2,..
+

._+Xn }

(Sl,


m with

com-

provided

(0,-I,+I)

one

can

find

matrices

Gi,

i=I,2,...i

conditions:
1,2 ..... 1

i , j : 1 , 2 ..... 1

matrix

m of type


n
=iE--1 sl. x . tl m

3 1
(-I,+I)

of o r d e r

matrix

{0,-Xl,
+

orthogonal

i ~ j, i,j:
:0,

design

is a square

]. S q u a r e

following

1- G i , Gj=0,

2 GGT-GGT


the n u m b e r

if V = B , K = r .

df{1,2,...n-1}

An o r t h o g o n a l

elements

about

m satisfying

elements

is S.

block

i:1,2,...n

in p a i r s

information

r of b l o c k s ,

aj of v a r i o u s


symmetric,

AmA
The

number

311].

5.[125].

s 2 , . . . s n) , si>0,

ai,

D = { X l , X 2 , . . . x k}

such

120,

pair

if for e v e r y

information

in

this


pair

is c a l l e d

of x i , x j 6 D 2
The

find

non-ordered

same

of o r d e r

m.

in

[124-131].
of or-


www.pdfgrip.com

1
4.

r~


E G .G~
l

i=I

= mI

I

m

Will

be c a l l e d

The

1-elemental

a 1-elemental
hyperframe

hyperframe

of o r d e r

{G i} ii=i of o r d e r

m.


m has

following

proper-

km,

H is

ties:
I " {H×G~

i
i=I

an H a d a m a r d

is a 1 - e l e m e n t a l

matrix

of o r d e r

2. m = 0 ( m o d

2).

DEFINITION


7. M a t r i c e s

ments

(0,-I,+I)

will

S I * $2=

0

2.

SI+S 2

is a

of o r d e r

where

k.

S I and

be c a l l e d

I.


hyperframe

(-I,+I)

S 2 of o r d e r

S-matrices,

2n×n

consisting

of ele-

provided

matrix

T

3.

SIS

Let

+ S2S 2 = n I 2 n

us note


only

I. The o r d e r
2.

If t h e r e

a S-matrix

S-matrix

exists

mn are

I. Ai,

mx~

8.[295].

F-matrices

i=1,2,3,4
3

3

i,j=


i,

S-matrices.

satisfies

the c o n d i t i o n

matrix

of o r d e r

n~0(mod

m,

then

2).

there

exists

.
Square

(-I,+I)


matrices

A ~ Bi,

i=I,2,3,4

of

provided

are c i r c u l a n t

2. B BT = B BT
1

of

an H a d a m a r d
m

of o r d e r

DEFINITION
order

of

2 properties

(-I,+I)


matrices

of o r d e r

m.

1,2,3,4

4

3. E
(Aix B i)
i= I
DEFINITION
der

k are

X

9 [120].Square

is a

i~j,

E

X XT


i 3

matrices

i,j:I,2,3,4

(-I,+I)

matrix

l
i,j=1,2,3,4

4
i=I

(0,-I,+I)

provided

: 0,

3. X i X j = X j X i ,

4.

= 4toni
mn


T-matrices

I. X i * Xj
4
2. E
i=I

(Aix B i ) T

= kI k

of o r d e r

k.

XI,

X2,

X3,

X 4 of or-


www.pdfgrip.com

10

DEFINITION
supplementary


m-j
E
i=1

10. [ 114]. (-I,+I)

Sequences

Golay sequences

length

of

m

{a k} k=Im and {b k} k=1 are

m provided

(aiai+j + bibi+j ) = 0, j=1,2,...,m-1


www.pdfgrip.com

Chapter

I. C O N S T R U C T I O N


§ 2. M e t h o d s

In this
truction

del a n d

of c o n s t r u c t i o n

paragraph

of c l a s s i c

Williamson

OF C L A S S I C

method

you

can

Hadamard

and

matrices

for H a d a m a r d


find

is p r o p o s e d .

also

strengthen

in p a r t i c u l a r

the B a u m e r t - H a l l ,

orders

from which

matrices

orders

one

of n e w o r d e r s ,

of c o n s t r u c t e d

2.1.

Williamson


This

method

method

is b a s e d

the

This

of

and
allo-

concept

the W i l l i a m s o n
arrays

matof n e w

infinite

of o r d e r

matrices,


method

method.

Wallis-Whiteman

for e x a m p l e

and

of

an u n i f i e d m e t h o d

of c o n s t r u c t i o n

can p r o d u c e

Williamson

of c o n s -

of c o n s t r u c t i o n

the W i l l i a m s o n

and presents

way


methods

I). N a m e l y ,

A new concept

Goethals-Seidel,

in t u r n

of b a s i c

Paley-Wallis-Whiteman

a recurrent

rices,

mard

the

matrices

of B a u m e r t - H a l l - G o e t h a l s - S e i -

It c o m b i n e s

wing


MATRICES

(see d e f i n i t i o n

methods.

of B a u m e r t - H a l l - G o e t h a l s - S e i d e l

gives

review

its m o d i f i c a t i o n s ,

that

to

the

matrices

Paley-Wallis-Whiteman

Hadamard

HADA~RD

c l a s s e s of H a d a m.

4n H(nil) , n, n i are
i

m. > 0.
l

its m o d i f i c a t i o n s

on a t h e o r e m

has

been

proved

by W i l l i a m s o n

in

1944.
THEOREM
der

2.1

[120].Let

square


(-I,+I)

matrices

Wi,

i=I,2,3,4,

of or-

m are
I. c i r c u l a n t ,

that

m-1
is W. = ~ v ! i ) u j,
1
j=0
3

2.

that

is V (i)• = V (i), , j = 1 , 2 , . . . , m - 1 ,
m-3
3

symmetric,


i=I,2,3,4

(2.0)

i=I,2,3,4

(2.1)

and meet
4

3.

I
i=1

Then
order

(2.2)

W ~ = 4mI
l
m

a Williamson

array


W[WI,

W2,

W3,

W4]

is an H a d a m a r d

matrix

of

4m.

This

theorem

shows

that

the p r o b l e m

of c o n s t r u c t i o n

of H a d a m a r d


mat-


www.pdfgrip.com

12

rices

of o r d e r

matrices

WI,

4 m c a n be r e d u c e d

i=I,2,3,4

Now consider
the

conditions
We

of o r d e r

m with

the c o n s t r u c t i o n


of T h e o r e m

conditions

of m a t r i c e s

WI,

of

square

(2.0),

(-I,+I)

(2.1),

i=1,2,3,4

(2.2).

satisfying

2.1.

denote
V. = P W P*,
l

l

where

to the c o n s t r u c t i o n

P is an u n i t a r y

matrix

i=

1,2,3,4

satisfying

(2.4)

the p r o p e r t y

2. We h a v e

from

(2.1)

V

m-1
E

V (i)DJ
j=1
3

=
l

From

(2.5)

the m a t r i c e s

Vi,

i=

?
V7 = 4mI

4
[

l

, i:

1,2,3,4

1,2,3,4


are

(2.5)

in p a r t i c u l a r

diagonal

and

(2.6)

m

i=I
that

is
4

m-1

2

E
Z
i=lj=0

Note


is

that

relation

(2.7)

V

(i)
3

Y

is t r u e

4

m-1

5-

E

i:I

j:0


(2.7)

=4m

for e v e r y

Yk h e n c e ,

for ¥k=I

namely,

2

V, (i)
3

= 4m

(2.8;

true.
Now we have

the d i f f e r e n c e
sum,

that

from relation


v(i) 6 { - 1 , + 1 } e v e r y b r a c k e t is a s q u a r e of
3
the p o s i t i v e (pi) a n d n e g a t i v e (n i) t e r m s of the

between

is
4

2

E
i=I
On the o t h e r
number

hand

Lagrange

is r e p r e s e n t a b l e

if m is odd,

then

(Pi-ni)

as the


(2.9)

: 4m

theorem

[120]shows

s u m of 4 s q u a r e s

4m is r e p r e s e n t a b l e

as the

of

that every

positive

integers;

moreover

4 squares

of o d d

numbers,



www.pdfgrip.com

13

that

is

4m

So,

we

have

from

(2.8),

2
2
2
2
= ql + q2 + q3 + q4

(2.9)


and

m-1
E
j=0
Further,

from

Now
verify

we

b)

for

for

Note

(i)

S--I

4
V~it,' = E
3
i=I


symmetry

(Pi-ni)

of W i m a t r i c e s

(2.11)

: + gi

we

have

V (1)
O

+ 2

(m-l) /2
(1)
Z
V
j=1
J

: + ql
-


V (2)
o

+ 2

(m-l) /2 V!2)
I
j:1
3

= + q2
-

V (3)
o

+ 2

(m-l) /2 V!3)
E
9= I
3

= + q3
-

V (4)
o

+ 2


(m-l)/2
E
j=1

= + q4
-

(2.12)

V(4)
3

discuss

the

choice

m~3(mod

4),

s=(m-1)/2

v (i)
o

tive


(2.10)

of

sign

for

qi'

i=I,2,3,4,

it

is e a s y

to

that

a)

and

(2.10)

m~1(mod

4),


s
l
j=1

that

expressions

4)

can

negative
are

-qi'

v(i)
3

not

1

[ q i - V ~ i~] /2

is o d d

if


(i)I
[qi+Vo
j /2

is o d d

: { -qi'
qi'

'

if

[ q i + V ~ i)] /2

if

[qi-Vo

[q +V (i)I /2,
i- o ]

be e v e n

elements
i! I)

if

={


(2.13)

s=(m-1)/2

+ 2

_ (i))

' MS

qi'

v! i)
3

V (i)
o

m-=1 (mod
and

s
z
j=1

+ 2

L (2)
i


and

i:I

odd

consisting

'

(i)]

2,3

j /2

'

4 for

respectively,
the

respectively

'

collection
where


is e v e n ,

(2.14)
is e v e n

both
and

m-=3(mod
number

4)

of p o s i -

(VI i) ,V~ i) .....


www.pdfgrip.com

14
a) for m~3(mod 4)
a 1) if ~
V (i)] /2
[qi- o

is odd, then

1 (I) = [m+ qi- V o(i) -I] /4 1 (2) [

"
i
' i = m-qi +V(1)-1]
o
a 2) if [qi +V o(i) ]/2

/4

is odd, then

1!I)i = [m-qi-V(i)-1]o

/4, L(2)=i [m+qi+V(i)-1]o

/4

b) for m~1(mod 4)
b 1) if [q -V (i) ] /2
i o

is even, then

1! I) = [m+qi-V(i)-1]
l
o
b 2) if [qir+v(i)
]o

/2


1 (2)= [m-qi+V(i)
i
o

'

-I] /4

is even, then

l! I) = [m-qi-V(i)-l]
1

/4

/4

O

1 (2) = [m-qi+V(i)-1]
'

i

/4

O

Now we will show the solution of the system for the following example.
EXAMPLE 2.1. Let m=7 hence,


4-7 = 12+32+32+32 .

Now suppose that v(i)=1, i=I,2,3,4.
o
Then we can rewrite the system (2.12) as
I + 2V~I)+

Hence, we have from

2V~I)+

2V~I)

(2.13) and

(2.14

V~ I) + V~I)

+ V~I

V~ 2) + V~ 2) + V~ 2

= + I

= -I,
= I,

~2.15)


V~ 3) + V2(3) + V~ 3) = I,

V~ 4) + V~ 4) + V~ 4) = 1.
It is easy to see that all kinds of solutions for systems

(2.15)

in


www.pdfgrip.com

15

field

(-I.,+I)

are

following

V~1) V~1) V~1)
II

-I

-1


1

-1

-1

--li]
-1

1

values

VI 2) V2(2) V~2)

VI 3)

V~ 3)

V~ 3)

-I

1

1

-1

1


1

I

-1

1

I

-1

1

-I__]

11

11

I

-1]
(2.16)

The

values


So,

the

V,1

1

-I

1

I

I

-I

in b r a c k e t s

from

(2.16)

satisfy

also

W2 = W3 = I + U
W4 = I - U


ly

Williamson

matrices

The

(2.12)

system

solvable
Let

ons

of

proof

us

even
prove

system
of


used.

and

convenient

We

of
and

means

2.1

will

order

of

2.1

reducing

the

idea

further


show

that

for

large

m

and

allowing

to

study

the

m by
of

means

proof

in m o r e


of

for

a computer.

Williamson

informative

it

is h a r d -

form

Note

Lemma

simple

solutithat

for

14.2.11120]

for


proof

investigations

Let

m be

an

odd

the

conditions

if V ( 1 ) + V ( 2o ) + V ( 3 o) + V ( 4 )o= { - o

number,
of

suppose

theorem

+ 4,

then

0

2.

,

a computer.

small

it

+ U5 - U6

,

7.

example

for

give

for

2.2.

sytisfying

I.


(2.3).

,

+ U2 - U3 - U4 + U5 + U6

+ U2 + U3 + U4

a theorem

theorem

THEOREM

by

(2.12)

was

rices

condition

matrices

W I = I + U - U2 - U3 - U4 - U5 + U6

are


the

if V ( 1 ) + V ( 2 ) + V ( 3 ) + V ( 4 ) = ~ 2 '
o
o
o
o

then

4
~
i=I

2.1.
Z4
i=I
V ~i)"

W i,

i=1,2,3,4,

are

mat-

Then
_
v k(i)=


_+ 2

(2 . 17)

k=1,2,...,m-1
4
0

, k=1,2,...,m-1

(2.18)


www.pdfgrip.com

16

PROOF.

We d e n o t e

by Pi'

i:I,2,3,4,

= I (J+Wi)

Pi


=

a matrix

Uk

Z

(2.19)

v(i): I
k
that

is m a t r i x

ments;

denote

constructed

f r o m W i by r e p l a c e m e n t

by P. n u m b e r

of n o n - z e r o

elements


-I e l e m e n t s
in f i r s t

by 0 e l e -

r o w of

1

we h a v e

1

by c i r c u l a r i t y

of Wi,

i=I,2,3,4,

P.J
1
N o w we get

from

relations

= p.J
1


(2.3),

4
X
i=I

P..Then

(2.15)

4
(2Pi-J) 2 = 4

(2.20)
and

(2.20)

4

X
i=I

P~~ - 4 X P.J
l
i=I ~

+ 4mJ

(2.21


= 4mI
m

Hence,

4
E
i:I
From

( E Pi)J
i=I

+ m(I-J)

(2.19)

p2 =
1
Now

4

-)

P~ :
1

let us r e p l a c e


denote

the

sum

can be r e w r i t t e n

E

(U k) 2

(mod 2)

(uk) 2 by U s in a c c o r d e n c e

(2.23)

(2.23

Vk(i) =I

with new

indexation

with

property


by E'U s. The

(2.2)

relation

and
(2.23)

as

P2~[E'uS]

(mod 2)

(2.24

l

So,

from

(2.22)

4
E
i=I


According
P.)
1

and

[I'U s]

(2.24)

(mod 2)

to s y m m e t r y

we have

=

4
( E Pi)J(mod
i:I

of m a t r i c e s

Wi,

2)

+


i=1,2,3,4,

(I-J)(mod

(hence,

2)

(2.25}

of m a t r i c e s


www.pdfgrip.com

17

4

4

E
i=I

[E'U s]

(mod 2) =[ E p~i)]" J ( m o d
%2
i=I


2) + (I-J)(mod

2)

(2.26)

with

p(i)
o
N o w we c o n s i d e r
CASE
positive

I,

if V (i) :1

o
0, if v (i)=-1
o

e a c h of 2 c a s e s of the t h e o r e m .

I. It f o l l o w s
elements

a l s o even,

: {


from assumptions

consisting

the sum

of the t h e o r e m

4 v(i)
E
o
i=I

that n u m b e r

is e v e n hence,

4

of

(i)

E Po
i=I

is

so,

4

Z p~ij___'
' 0(mod
i=I o
Then,
peats

2)

4
E
[E'U s] (mod 2) = (I-J) (mod 2). It f o l l o w s
i=I
o d d n u m b e r t i m e s hence, for an a r b i t r a r y k h o l d s

we have

that U s re-

Vk(1) + VZ(2) + Vk(3) + V(4)n" = +- 2

Case

I is p r o v e d .
4
E v~i)t = + 2, t h e n it f o l l o w s f r o m r e l a t i o n
i:I o
that 3 items of this sum have the same signs hence,


C A S E 2. Let
V o(i)6{-I,+I}

4
E p~i;~'
~ I (rood 2),
o
i:I

so, we have,

from

(2.26)

4

E [E'uS]---0(mod 2)
i=I
that

is U k, k = 1 , 2 , . . . , m - 1

repeats

2 or 4 times.

Hence,

we have


shown

that r e l a t i o n

Vk(1) + Vk(2) + Vk(3) + Vk(4) =#+
4 ~0

is true,

that

is the t h e o r e m

As a c o r o l l a r y

is c o m p l e t e l y

of t h i s t h e o r e m

proved.

follows Williamson

theorem

[39] na-


www.pdfgrip.com


18

mely,

if m is od d a n d c i r c u l a n t

satisfy

(2.3)

precisely

and t a k e n w i t h

t h r e e of V k

,

and s y m m e t r i c

matrices

such signs that v ( i ) = 1 ,
o

k

, V


, V

have

Wi,i=I,2,3,4,

i=1.2.3.4,

then

same sign for e a c h k.

It a l s o h o l d s
THEOREM
1,2,3,4,

of o r d e r m s a t i s f y

v(i)
_ (i)
j =Vm_j,
Then

2.3. Let m be an o d d n u m b e r

m-1
W = E v!i)uJ,i =
i 9= I V31)
-'
(1) '

(2.1), (2.3) and
3 -- V m-j

and m a t r i c e s

the c o n d i t i o n s

i=2,3,4, j=I,2, . . .,m-1 .

if
4

a) V ( 1 ) + V ( 2 ) + V ( 3 ) + V ( 4 ) = { ~ 4 o
o
o
o
u

, then

b) V ( 1 ) + V ( 2 ) + V ( 3 ) + V ( 4 )
+2 t h e n
o
o
o
o
= -

~2 w i t h m ~ 1 ( m o d 4)
+4 or 0 w i t h m ~ 3 ( m o d


E
i=I V i)={

4
Z _ (i) ={ -+4 or 0 w i t h m ~ 1 ( m o d
i=I vk
~2 w i t h m ~ 3 ( m o d 4 .

4)
4)

for e v e r y k, k=I,2, ....(m-I)/2.
N o w we will c o n s i d e r
to

(2.12)

denote

the T h e o r e m

s y s t e m of e q u a t i o n s

2.2 and will o b t a i n

with a simpler

form.


an e q u i v a l e n t

To do this let us

[39]:
LI(11,12,13,14

= -11+12+13+14

L2(11,12,13,14)

= 11-12+13+14

L3(!1,12,13,14)

= 11+12-13+14

(2.27)

L4(11,12,13,14)

= 11+12+13-14

(2.28)

ti,k=~1 Li(V~I),v(2),V(3)k
k
'V(4)k , i = I , 2 , 3 , 4 ,

M k = { t l , k , t 2 , k , t 3 , k , t 4 , k}


~i = I+

(m-I)/2
E
k:1

for the v a l u e s

ty of the r e l a t i o n s

follows

above

from

(m-l)
2

1,2, ....

t i k(yk+¥m-k),

X i = Li(~I,~2,~3,~4),

Some r e l a t i o n s

, k=


k = I , 2 , . . !m~1)

(2.29)

i=I,2,3,4

(2.30)

i=I,2,3,4

are g i v e n

(2.12),

(2.31)

in L e m m a

(2.27)

2 .I. The v a l i d i -

and t h e o r e m

2.2.


www.pdfgrip.com

19


LEMMA

2.1.

Let m be an odd number
V(1)
o

+ V(2)
o

and

+ V(3)
o

+ V(4)
o

={_+4

Then:
I. F o r

2

"

Xi/2


an a r b i t r a r y

=

_ (i)

4
4
3. Z X 2 =
I
i= I i
i=I

COROLLARY

I+2

(m-!)/2
Z
~=1

and

(2.12)
Note

chine

that


3

for Y =

I

(2.32)

(2.34)

= ~ qi

'

i=

(2.35)

that

owing

. Then

solutions

of

system


1,2:3,4

(2.35)

system

for the

(2.12)[120].It

following

47 W i l l i a m s o n
Baumert,
27,

29

to p r o p e r t i e s

orders

Golomb,

Baumert

Yamada[145].

(p+I)/2,


7. m = p ( p + 1 ) / 2 ,
Let us define
Baumert,Golomb
result

p~1(mod

4)

p~1(mod

have

in H a d a m a r d

92 = 7 2 + 5 2 + 3 2 + 3 2

of

does

not

investigations

solution

of


m:

found

of

all

solutions

[28].

is the o r d e r

of a p r i m e

(Turyn,

is t h e o r d e r

of a p r i m e

(Whiteman,

emphasized

matrices

92 = 9 2 + 3 2 + 1 2 + I 2 r e s u l t s


Further

4)

has

b y L I a set of o r d e r s

and Hall

the

[28].

5. m = 29,37,
6. m =

is k n o w n

for m a -

H a l l [29].

Baumert

41

ti, k is e a s i e r

[120].


4. m = 3 , 5 , . . . , 2 3

sumption

i=I,2,3,4

'

2
2
2
2
4m = q1+q2+q3+q4

Let

system

(2.35)

3. m = 25,

on

zero.

are e q u a v a l e n t .

2. m = 23


on

is n o t

v(i)

j=1

t i , k (Yk+Ym-k)

I. m = 37,

(2.10)

of ~

2
~i = 4 m

2.1.

processing

equation

(m-l)/2
~

+ 2


v°

k only one element

m from
that

not

[120]. F o r

in H a d a m a r d

items

1-7.Note

also

1971)
that

all of p r e s e n t a t i o n s

example,

matrix

1972).


the p r e s e n t a t i -

whereas

the p r e s e n t a t i -

[120].
system

(2.10)

were

carried

out

o n the

as-


www.pdfgrip.com

20

4m :

So,


it w a s

result
type

out

proved

in

in H a d a m a r d
has

Generalization

of

two

4m

= x

of

m=29,

12


+ y

2

+ x

37,

+ x2 + y2

2

+ y

2

the

order

+ y

2

+ y

2

+ y


2
2

presentation
104

of

whereas

the

first

type

does

presentation

of

not
thi~

41.

Williamson


of

conditions

- alteration

of

number

said

2.1

t,q e o r e m

to

be

AA T

(2.1),

of

[ 295].

has


been

generally

carried

(2.2}.

matrices.

Square

Williamson

I. M N T = N M T
2.

2

that

- alteration

m are

+

directions:

DEFINITION


and

= x

matrix
for

in

4m

[145]

solution

12

[-I,+I)

matrices

matrices

A,

B,

C,


D of

order

provided

M,N6{A,B,C,D}

+ BB T

+ CC T ~

[2.36)

DD T = 4mI

(2.371
m

Note

that

with

conditions

automatically
In
can

B,

1974

be
C,

those

and

D and
of

cnndition

7.Wallis

satisfied
has

(2.11

[ 288]

both

noted

such


matrices

that

7

condition

12.36)

holds

12.3) .
conditions

and

matrices

(item

the

becomes

non-circulant

constructed


Wi]!iamson

(2.2)

(2.37)
has

for

and

of

) with

(2.36)

non-syn~etric
orders
have

and

matrices

coinciding
been

(2.37~
A.


with

constructed

by

9~iteman.
At

present

the

Wil]iamson

matrices

of

following

orders

have

been

constructed:
1. m ~


100

2.

9k

3.

m(4m+3)

4.

93

5.

2m,

6.

(m+11 (m+2),

symmetric

k

with

exception


is a n a t u r a l

number

. m(4m-1),

mC{1,3,5

(Wa]lis
m

the

is

[311 ]
.... , 2 3 , 2 5 }

(Wallis

1975) .

[311 ]~

the

Hadamard

35,39,47,53,67,71,73,83,89,941295]


order

of

existing

m~1(mod

4)

is

matrix

[295 ].

Wil]iamson

a prime

and

m+3

matrices
is

the


(Wallis[
order

of

311])
some


www.pdfgrip.com

21

7. 2.39,

2.203,

6a I

8.

10 a 2

a. > 0, a r e

2.303,

- 14 a 3

•


non-negative

2.333,

2.669,

18 a 4

22a5

from where

2.1603

• 26 a 6

(Wa]lis

. m,

in p a r t i c u l a r

[295]).

mEL 1 ,

i=1,2,.

Williamson


.,6,

matrices

of

l-

order

2.35,

2.65,

9. m k ( m + 1 ) ,

2.77

are

m~1(mod

obtained

4)

is the

(Sarukhanian,


order

1978)

of a p r i m e

number,

k~0

Spence,

m satisfying

the

items

1977).
10.

3k

7.3 k, k>0

11. L e t u s d e f i n e

(Mucho~adhyay


[327])

b y L 2 a set of n u m b e r s

I-I0.
1

12. m ~i()2,n

, where

m,nEL,~ i are

arbitrary

non-negative

integers

1

L=LIUL 2
In

(Agaian,

Sarukhanian

1965 C o e t h a l s


trictions

(2.0)

(Such m a t r i c e s

and

and

Seidel

(2 37}

have

been

called

in c o n s t r u c t i n g

matrices

with

such properties

(a,b,c


of n o n - c o m m u t a b i l i t y

hals-Seidel
analogu~

array

of T h e o r e m
2.4

THEOREM

del matrices
der

instead
2.1.

have

m.

the

later

conditions

of


with

(2.1),

res-

(2.2).

ones.)

They

succe-

m, m E { 3 , 5 , . . . , 6 1 , 2 a . 1 0 b . 2 6 c + 1 }

are n o n - n e g a t i v e
of

the m a t r i c e s

Goethals-Seidel

of o r d e r

such matrices

integers

authors


t h a t of W i l l i a m s o n

[111-113]).

have

Be-

to u s e G o e t -

for ~ r e s e r v a t i o n

the

It h o l d s

(Goethals-Seidel

of o r d e r

discussed

discarding

eded

cause

[~I]) .


Then

[111]).

array

GZ

Let A,B,C,D

[4]

be Goethals-Sei-

is an H a d a m a r d

matrix

of o r -

4m.
In

[297]

Theorem
taken

2.4.


Wallis
So,

and Whiteman

matrices

back-circulant,

An
Wallis
(number

A,

instead

generalisation

in

Instead

of c o n s t r u c t e d
matrices)

Williamson

and Goethals-Seidel


generalized

and matrix

[4] t h e y

discussed

BY[4].

Williamson

that

as

used
large

array

is a r r a y

were

was proposed

were


times

of W i l l i a m s o n

matrices

method

matrices

is t h r e e

ones,

modifications

circulant

of W i l l i a m s o n

instead

other

taken

of W i l l i a m s o n

Williamson


called

of GZ

F-matrices

and

obtained

B, D w e r e

important
[299].

have

WA

analyzed

C was

by

F-mafrices
as t h a t

synthesized
[4].

in

of

[6,

of
from

Finally,
167,

so

208]


www.pdfgrip.com

22

(The g e n e r a l i z a t i o n
replaced
ralized

Williamson
where

m6L,


number

From
logues

of

analysis

where

analoques

and construct
- find
Williamson

m6L1,

matrices

Now we

turn our
that

in

DEFINITION


we c o m e

are matural

which

formulae
permit

numbers.

find

matrices

matrix

give

with

2.1.

those
-

gene-

that
n the


and theorems,

and ana-

questions:

a notation

containing

investigate

to c o n s t r u c t

to the

modifications

2.2.

of c o n s t r u c t i n g

A set of

solution

of

a notation


(-1,+I)

(0,+I)

matrices

matrices
matrix

infinite

classes

decomposition

of W i l l i a m s o n

of Williamson

is a s q u a r e

i.e.

of n e w g e n e r a l i z e d

questions

stated


of W i l l i a m s o n

s W W~
ill

The

notation

above.

families

con-

matrices.
{W i} i=II

of o r d e r

(s 1 , s 2 , . . . , s l , B m , m )

B m of o r d e r

m will

provided

m, B m ~ 0 s u c h t h a t


(2.38)

1
= M X
s I
i= I i m

of

(2.39)

family

of w i l l i a m s o n

matrices

of
matrices

of

holds

1
X
i=I

Williamson


of H a d a -

into product

w.swT
w.swT
i m 3
3 m I

NOTE

Note

for a g i v e n

to s t u d y of f o l l o w i n g

factorisation,

i,j=1,2,...l,i@j

2.

The

known.

of W i l l i a m s o n

matrices


[5 ] w a s p r o p o s e d

a family

for e v e r y

ar~

is a n a l y z e d :

Williamson

attention

all known

I. T h e r e

matrix-blocks).

are

matrices.

of W i l l i a m s o n

allowing

multipliers.


be called

a,b,c

problem

theorem

such recurrence

sparse

taining

orders

matrices

them.

mard matrices

Note

following

of a l l m o d i f i c a t i o n s

- for n e w g e n e r a l i z e d

all known

from circulant

of W i l l i a m s o n

of Williamson

symmetric

n 6 {3,5,...,59,61}

in f a c t a f o l l o w i n g
of all k i n d s

that circulant

ones

matrices

(2a10b26c+1)m,

in[145]

here

by block-circulant

-mn,


-

means

for

1=4,

s1=s2=s3=s4=1,

Bm=I m

coincides