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 $\backslash pm1$ and they satisfy the relationship

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

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

:$\backslash 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

}}