Williamson conjecture

In combinatorial mathematics, specifically in combinatorial design theory and combinatorial matrix theory, the Williamson conjecture is that Williamson matrices of order ${\displaystyle n}$ exist for all positive integers ${\displaystyle n}$. Four symmetric and circulant matrices ${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$, ${\displaystyle D}$ are called Williamson matrices if their entries are ${\displaystyle \pm 1}$ and they satisfy the relationship

${\displaystyle A^{2}+B^{2}+C^{2}+D^{2}=4n\,I}$

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

${\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 ${\displaystyle 4n}$. ^[1] It was once considered likely that Williamson matrices exist for all orders ${\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 ${\displaystyle 4n}$. ^[2] 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 ${\displaystyle n=35}$. ^[3] In 2008, the counterexamples 47, 53, and 59 were additionally discovered. ^[4]

Following the negative result of Ðoković, which ruled out the existence of Williamson matrices of order ${\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. ^[5] One such instance is given by the sequences

a = --+--+--+++-+----+-+++--+--+------- b = +---+---+-++-+--+-++-+---+---++++++ c = -++---+-+--+--++--+++++-+-+++++-+-- d = +----+++-+-+--++--+-+-+++----++---+ 

with the associated matrices defined by

A = circulant(a) B = circulant(b) C = fliplr(circulant(c)) D = circulant(d) 

References

1. Williamson, John (1944). "Hadamard's determinant theorem and the sum of four squares". Duke Mathematical Journal . 11 (1): 65–81. doi:10.1215/S0012-7094-44-01108-7. MR   0009590.
2. Golomb, Solomon W.; Baumert, Leonard D. (1963). "The Search for Hadamard Matrices". American Mathematical Monthly . 70 (1): 12–17. doi:10.2307/2312777. JSTOR   2312777. MR   0146195.
3. Ðoković, Dragomir Ž. (1993). "Williamson matrices of order ${\displaystyle 4n}$ for ${\displaystyle n=33,35,39}$". Discrete Mathematics . 115 (1): 267–271. doi: 10.1016/0012-365X(93)90495-F . MR   1217635.
4. Holzmann, W. H.; Kharaghani, H.; Tayfeh-Rezaie, B. (2008). "Williamson matrices up to order 59". Designs, Codes and Cryptography. 46 (3): 343–352. doi:10.1007/s10623-007-9163-5. MR   2372843.
5. Kline, Jeffery (26 July 2019). "Geometric search for Hadamard matrices". Theoretical Computer Science. 778: 33–46. doi:10.1016/j.tcs.2019.01.025.