Hadamard Matrices

In the last chapter of Ian Stewart's book "The Great Mathematical Problems" (ISBN 978-1846683374), there is a section about Hadamard matrices. These are square arrays whose entries are either 1 or 0 (Hadamard's original definition used −1 of 0). Each row in the matrix, when compared with some different row, must have exactly one half of the entries matching and one half non-matching. The first 4 matrices are:

2x2      4x4            8x8                  12x12
1 1    1 1 1 1    1 1 1 1 1 1 1 1    1 1 1 1 1 1 1 1 1 1 1 1
1 0    1 0 1 0    1 0 1 0 1 0 1 0    1 0 0 1 0 1 0 1 0 1 0 1
       1 1 0 0    1 1 0 0 1 1 0 0    1 0 1 0 1 1 0 0 0 0 1 1
       1 0 0 1    1 0 0 1 1 0 0 1    1 1 0 0 1 0 0 1 0 1 1 0
                  1 1 1 1 0 0 0 0    1 0 1 1 1 0 1 1 0 0 0 0
                  1 0 1 0 0 1 0 1    1 1 1 0 0 0 1 0 0 1 0 1
                  1 1 0 0 0 0 1 1    1 0 0 0 1 1 1 0 1 1 0 0
                  1 0 0 1 0 1 1 0    1 1 0 1 1 0 0 0 1 0 0 1
                                     1 0 0 0 0 0 1 1 1 0 1 1
                                     1 1 0 1 0 1 1 0 0 0 1 0
                                     1 0 1 1 0 0 0 0 1 1 1 0
                                     1 1 1 0 0 1 0 1 1 0 0 0

Hadamard matrices have many applications, among them error-correcting codes.

The conjecture

Jacques Hadamard (1865 - 1963) himself proved that, apart from the 2 x 2 matrix, the edge lengths of all Hadamard matrices must be divisible by 4. In 1867 Sylvester gave a construction for all Hadamard matrices of order 2^{k, k >= 2. Paley published two construction methods for two special clases of orders in 1933. The smallest order that could not be constructed by a combination of Sylvester's and Paley's methods was 92. Several other authors published specialized constructions and raised the minimal unknown order to 428, and since 2005 that order is 668.}

Mathematicians believe, but still cannot prove, that Hadamard matrices of all orders 4*n can be constructed.

The 3D model

Since the 0/1-entries of the matrices quickly appear as random noise, I tried to visualize the inner structure of the matrices in a better way, and one result is a 3D model for the 11 matrices with order 4, 8, 12, ... 44.

As one can see in the examples above, there basic building blocks of 2x2 entries. In a first step, the two rows are encoded as binary values:

a b  ->  a b c d           1 1  -> 1 1 1 0  -> e
c d                        1 0 

The resulting 4-bit pattern is encoded as a hexadecimal digit 0-9a-f. Now it is much easier to recognize the structure in the 4 example matrices above:

e    ee    eeee    eddddd
     e1    e1e1    b8e11e
           ee11    be8e11
           e11e    b1e8e1
                   b11e8e
                   be11e8

The 3D model was developped with the great Javascript package threejs.org. The 11 matrices are represented by little cubes whose opacities resp. colors are given by the hexadecimal encoding described above. The matrices are then stacked as a pyramid.

Technical details

The article https://arxiv.org/html/2411.18897v1 describes in detail how to compute the matrices with SageMath. Online you can run https://sagecell.sagemath.org/ with the following program:

from sage.combinat.matrices.hadamard_matrix import hadamard_matrix, skew_hadamard_matrix

for i in range(1,11):
  H = hadamard_matrix(4*i)
  print(i, "========")
  print(H.str())