Hadamard Matrices: Difference between revisions

From tehowiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
History
3D model
Line 1: Line 1:
In the last chapter of Ian Stewart's book "The Great Mathematical Problems" (ISBN 978-1846683374), there is a section about [[wikipedia:Hadamard_matrix|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. Apart from the 2 x 2 matrix, the edge lengths of all Hadamard matrices must be divisible by 4. The first few matrices are:   
In the last chapter of Ian Stewart's book "The Great Mathematical Problems" (ISBN 978-1846683374), there is a section about [[wikipedia:Hadamard_matrix|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
  2x2      4x4            8x8                  12x12
Line 17: Line 17:
Hadamard matrices have many applications, among them error-correcting codes.
Hadamard matrices have many applications, among them error-correcting codes.
====The conjecture====
====The conjecture====
[https://en.wikipedia.org/wiki/Jacques_Hadamard 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<sup>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.  
[[wikipedia:Jacques_Hadamard|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<sup>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.
Mathematicians believe, but still cannot prove, that Hadamard matrices of all orders 4*n can be constructed.
====The 3D model ====
====The [https://teherba.org/threejs/hapyramid.html 3D model] ====
That inspired me to develop a 3D model for the 11 matrices with  4, 8, 12, ... 44 = 4*n for n = 1..11.  
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  4, 8, 12, ... 44 = 4*n for n = 1..11.  
 
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 
 
c d                            1 0


==== Technical details ====
==== Technical details ====
Line 27: Line 33:


<code>from sage.combinat.matrices.hadamard_matrix import hadamard_matrix, skew_hadamard_matrix</code>
<code>from sage.combinat.matrices.hadamard_matrix import hadamard_matrix, skew_hadamard_matrix</code>
  for i in range(1,12):
  for i in range(1,11):
   H = hadamard_matrix(4*i)
   H = hadamard_matrix(4*i)
   print(i, "========")
   print(i, "========")
   print(H.str())
   print(H.str())
The output can be  reduced with:
perl -pe "s{\-1}{\.}g; s{[\[\]\|\+\-]}{}g; s{\A\s+\Z}{};"  infile > outfile
===3D Design===
Since the edge lengths increase by 4, solid blocks of bxwxh = 1x1x2 will be used to represent a one in a matrix plane, and empty space for a zero (resp. -1). The matrix planes will be stacked as a pyramid, with the 44x44 matrix at the bottom and the 4x4 at the top. Maybe the 2x2 matrix becomes the real top, maybe with blocks 1x1x1?

Revision as of 08:17, 9 August 2025

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 2k, 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 4, 8, 12, ... 44 = 4*n for n = 1..11.

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

c d 1 0

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())
Retrieved from "http://teherba.org/tehowiki/index.php?title=Hadamard_Matrices&oldid=848"