By Kshitija Vaidya, Monash University
The Hadamard conjecture is one of those problems that are straightforward to state but tremendously difficult to solve; it is among the longest-standing open problems in mathematics. To understand what it says, we first look at Hadamard matrices.
A matrix is an array of numbers. For our purposes, we need only worry about square matrices composed of ±1s. We can think of these as n by n grids made from black and white boxes, where the black boxes represent 1s and the white boxes -1s. The size of the square grid, n, is called the order of the matrix. An n by n grid of black and white boxes is Hadamard if upon comparing any two distinct rows in the grid, we find that the number of positions in which the colouring differs is equal to the number of positions in it is the same. Hadamard matrices have incited interest since the nineteenth century when they were first studied by James Sylvester and later by Jacques Hadamard. The Hadamard conjecture states that a Hadamard grid exists for every order 4n.
Mathematicians have constructed various infinite families of Hadamard matrices. We briefly explore the Sylvester construction [3, p.11]. This comprises the following sequence of Hadamard matrices whose orders cover all powers of 2:
At each step, the new grid is obtained by pasting three versions of the previous grid together with an ‘inverted’ version of the previous grid (where ‘inverting’ refers to interchanging the black and white boxes). Since we started with a Hadamard grid, the grids generated via this repeated pasting process are always Hadamard. You can check this yourself for the first few steps!
The Sylvester construction is one of many families of Hadamard matrices. Our AMSI project focused on a particularly significant family, called cocyclic Hadamard matrices [2]. Most classical constructions of Hadamard matrices (including Sylvester’s) are known to be cocyclic [3]. This strongly suggests that cocyclic Hadamard matrices may provide a uniform approach to the Hadamard conjecture. Certain algebraic objects called cocycles are at the core of cocyclic Hadamard matrices; 2-cocycles are naturally represented as matrices. This provides a link between Hadamard matrices and cocycles. In our project, we studied Dane Flannery’s work on computing cocycles and their associated matrices [1].
Throughout our project, we were able to appreciate how rich the mathematics relating to Hadamard matrices really is. The applications of Hadamard matrices in the real world are equally so. Hadamard matrices are used extensively in coding theory and cryptography [3]. The Mariner and Voyager probes which were launched into space to study the planets of our solar system use codes based on a Sylvester Hadamard matrix to transmit images to Earth [4, p. 432]. Indeed, while the Hadamard Conjecture is central to the pure mathematician’s interest in research about Hadamard matrices, the wide-ranging applications of this research render its scope truly astronomical.
[1] Flannery, D. L. (1996). Calculation of cocyclic matrices. Journal of Pure and Applied Algebra, 112(2), 181-190.
[2] Horadam, K. J., & de Launey, W. (1993). Cocyclic development of designs. Journal of Algebraic Combinatorics, 2(3), 267-290.
[3] Horadam, K. J. (2012). Hadamard matrices and their applications. Princeton university press.
[4] Seberry, J., & Yamada, M. (1992). Hadamard matrices, sequences, and block designs. Contemporary design theory: a collection of surveys, 431-560.
Image of Jupiter: https://voyager.jpl.nasa.gov/galleries/images-voyager-took/jupiter/#gallery-6 (Courtesy NASA/JPL-Caltech)
Kshitija Vaidya was a recipient of a 2018/19 AMSI Vacation Research Scholarship.