Williamson conjecture
In combinatorial mathematics, specifically in combinatorial design theory and combinatorial matrix theory, the Williamson conjecture is that Williamson matrices of order exist for all positive integers .
Four symmetric and circulant matrices , , , are called Williamson matrices if their entries are and they satisfy the relationship
:
where is the identity matrix of order . John Williamson showed that if , , , are Williamson matrices then
:
A & B & C & D \\
-B & A & -D & C \\
-C & D & A & -B \\
-D & -C & B & A
\end{bmatrix}
is an Hadamard matrix of order .{{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
and that the structure of Williamson matrices could provide a route to proving the Hadamard conjecture that Hadamard matrices exist for all orders .{{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 .{{cite journal
|last = Ðoković
|first = Dragomir Ž.
|title = Williamson matrices of order for
|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
}}