Williamson conjecture

In combinatorial mathematics, specifically in combinatorial design theory and combinatorial matrix theory, the Williamson conjecture is that Williamson matrices of order n exist for all positive integers n.

Four symmetric and circulant matrices A, B, C, D are called Williamson matrices if their entries are \pm1 and they satisfy the relationship

:A^2 + B^2 + C^2 + D^2 = 4n\, I

where I is the identity matrix of order n. John Williamson showed that if A, B, C, D are Williamson matrices then

:\begin{bmatrix}

A & B & C & D \\

-B & A & -D & C \\

-C & D & A & -B \\

-D & -C & B & A

\end{bmatrix}

is an Hadamard matrix of order 4n.{{cite journal

|last=Williamson

|first=John

|title=Hadamard's determinant theorem and the sum of four squares

|journal=Duke Mathematical Journal

|volume=11

|issue=1

|pages=65–81

|year=1944

|doi=10.1215/S0012-7094-44-01108-7

|mr=0009590}}

It was once considered likely that Williamson matrices exist for all orders n

and that the structure of Williamson matrices could provide a route to proving the Hadamard conjecture that Hadamard matrices exist for all orders 4n.{{cite journal

|last1=Golomb

|first1=Solomon W.

|last2=Baumert

|first2=Leonard D.

|title=The Search for Hadamard Matrices

|journal=American Mathematical Monthly

|volume=70

|issue=1

|pages=12–17

|year=1963

|doi=10.2307/2312777

|jstor=2312777

|mr=0146195}}

However, in 1993 the Williamson conjecture was shown to be false via an exhaustive computer search by Dragomir Ž. Ðoković, who showed that Williamson matrices do not exist in order n=35.{{cite journal

|last = Ðoković

|first = Dragomir Ž.

|title = Williamson matrices of order 4n for n = 33, 35, 39

|journal = Discrete Mathematics

|volume = 115

|issue = 1

|pages = 267–271

|year = 1993

|doi = 10.1016/0012-365X(93)90495-F

|mr=1217635

|doi-access = free

}} In 2008, the counterexamples 47, 53, and 59 were additionally discovered.{{cite journal

|last1 = Holzmann

|first1 = W. H.

|last2 = Kharaghani

|first2 = H.

|last3 = Tayfeh-Rezaie

|first3 = B.

|title = Williamson matrices up to order 59

|journal = Designs, Codes and Cryptography

|volume = 46

|issue = 3

|pages = 343–352

|year = 2008

|doi = 10.1007/s10623-007-9163-5

|mr=2372843

}}

References