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 22 matrices with order 4, 8, 12, ... 88.

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 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. The cubes inside the pyramid are omitted since from outside they cannot be seen anyway.

The model turns slowly by itself. It can be rotated with the mouse cursor, and with the mouse wheel the user can zoom in or out.

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())

The model uses mainly the following programs on github.com/gfis/fasces:

• hapyramid.html
• hapyramid_world.js
• hapyramid_blocks.js (generated by hapy_blocks.pl)

There is a makefile that controls the whole generation process.