In combinatorial mathematics, specifically in combinatorial design theory and combinatorial matrix theory, the Williamson conjecture is that Williamson matrices of order n {\displaystyle n} exist for all positive integers n {\displaystyle n} . Four symmetric and circulant matrices A {\displaystyle A} , B {\displaystyle B} , C {\displaystyle C} , D {\displaystyle D} are called Williamson matrices if their entries are ± 1 {\displaystyle \pm 1} and they satisfy the relationship
A 2 + B 2 + C 2 + D 2 = 4 n I {\displaystyle A^{2}+B^{2}+C^{2}+D^{2}=4n\,I}
where I {\displaystyle I} is the identity matrix of order n {\displaystyle n} . John Williamson showed that if A {\displaystyle A} , B {\displaystyle B} , C {\displaystyle C} , D {\displaystyle D} are Williamson matrices then
[ A B C D − B A − D C − C D A − B − D − C B A ] {\displaystyle {\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 4 n {\displaystyle 4n} . It was once considered likely that Williamson matrices exist for all orders n {\displaystyle n}
and that the structure of Williamson matrices could provide a route to proving the Hadamard conjecture that Hadamard matrices exist for all orders 4 n {\displaystyle 4n} . However, in 1993 the Williamson conjecture was shown to be false by Dragomir Ž. Ðoković through an exhaustive computer search, which demonstrated that Williamson matrices do not exist of order n = 35 {\displaystyle n=35} . In 2008, the counterexamples 47, 53, and 59 were additionally discovered. Following the negative result of Ðoković, which ruled out the existence of Williamson matrices of order n = 35 {\displaystyle n=35} , it was shown in 2019 that relaxing the symmetry and circulant requirements nevertheless permits a Hadamard matrix of this block form to exist for that order. One such instance is given by the sequences
with the associated matrices defined by
References