PROFILPELAJAR.COM

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 known as Williamson matrices if their entries are $\pm 1$ and they satisfy the relationship

A^{2}+B^{2}+C^{2}+D^{2}=4nI

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$ .^[1] 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$ .^[2] 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$ .^[3] In 2008, the counterexamples 47, 53, and 59 were additionally discovered.^[4]

References

^ 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.
^ 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.
^ Ðoković, Dragomir Ž. (1993). "Williamson matrices of order $4n$ for $n=33,35,39$ ". Discrete Mathematics. 115 (1): 267–271. doi:10.1016/0012-365X(93)90495-F. MR 1217635.
^ 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.