Chapter 10: Processes of Perception and Analysis

Section 6: Irreversible Data Compression

Hadamard matrices

Hadamard matrices are n × n matrices with elements -1 and +1, whose rows are orthogonal, so that m . Transpose[m] == n IdentityMatrix[n]. The matrices used in Walsh transforms are special cases with n=2s. There are thought to be Hadamard matrices with every size n=4k (and for n>2 no other sizes are possible); the number of distinct such matrices for each k up to 7 is 1, 1, 1, 5, 3, 60, 487. The so-called Paley family of Hadamard matrices for n=4k=p+1 with p prime are given by

PadLeft[Array[JacobiSymbol[#2-#1,n-1]&,{n,n}-1]- IdentityMatrix[n-1],{n,n},1]

Originally introduced by Jacques Hadamard in 1893 as the matrices with elements Abs[a]<=1 which attain the maximal possible determinant ±n^(n/2), Hadamard matrices appear in various combinatorial problems, particularly design of exhaustive combinations of experiments and Reed–Muller error-correcting codes.

From Stephen Wolfram: A New Kind of Science [citation]