The first post in the recent series of posts on Hadamard matrices describes a way of constructing new Hadamard matrices from two other Hadamard matrices by taking their Kronecker product.

Starting with a Hadamard matrix H₀ and a Hadamard matrix G, you can construct a sequence of Hadamard matrices by

H_n+1 = G ⊗ H_n

for  positive integers n. This is known as the generalized Sylvester method.

Let p_n be the proportion of 1s in H_n and let q be the proportion of 1s in G. Then you can show that the recurrence holds

p_n+1 = q p_n + (1 − q)(1 − p_n).

You can solve the recurrence to show that

lim_{n → ∞} p_n = ½

and so as the iterations proceed, the ratio of number of 1s to the number of −1s approaches 1.

This doesn’t say anything Hadamard matrices in general, but it does apply to all Hadamard matrices created by repeatedly applying the generalized Sylvester method.

If you set G and H equal to the matrix

then p₀ = q = ¾. Then for n = 1, 2, 3, …, 8 the values of p_n are

0.625
0.5625
0.53125
0.515625
0.5078125
0.50390625
0.501953125
0.5009765625.

Hadamard matrices are in the news following the recent announcement of a newly discovered Hadamard matrix. I’ve written three posts on Hadamard matrices recently, one as a sort of introduction and two on applications: the error correcting code used in the Mariner 9 probe and constructing sphere packings.

A Hadamard matrix is an orthogonal matrix with all entries equal to ±1. Jacques Hadamard conjectured that there exist Hadamard matrices of order 4n for all positive integers n. It’s necessary that the order be divisible by 4, and Hadamard conjectured that this is sufficient [1].

How could you compactly represent a Hadamard matrix? Since the entries are all either 1 or − 1 each entry could be represented by a single bit, and n² bits could store an n × n Hadamard matrix. But we can do better.

Methodical matrices

If the matrix can be produced by an algorithm, you only need to store the name of the algorithm and the argument to the algorithm. So, for a 1024 × 1024 matrix applied by iterating Sylvester’s algorithm could be stored by saying “Apply Sylvester’s algorithm 10 times” rather than storing a megabyte of data.

Paley’s method can create a Hadamard matrix corresponding to every prime power. So you could determine a Paley type matrix by storing the prime and the exponent.

Next in complexity would be hybrid algorithms, such as start with the Paley method applied to 37⁶ and then apply Sylvester’s method 3 times.

There are more methods of creating Hadamard matrices than Sylvester’s method and Paley’s method, though they’re harder to describe and parameterize.

Sporadic matrices

If a Hadamard matrix cannot be constructed using an algorithm, you can still store the matrix in fewer than n² bits. Since the rows are orthogonal, the last row of the matrix is determined by all the previous rows, up to sign. So you could store a Hadamard matrix using n(n − 1) + 1 bits.

Some Hadamard matrices are symmetric or skew. A symmetric matrix is determined by its diagonal and the elements above the diagonal. So a symmetric Hadamard matrix could be represented by n(n + 1)/2 bits.

A skew Hadamard matrix isn’t quite skew-symmetric. A matrix M is skew symmetric if

M^T = −M.

This implies the diagonal elements are 0, and Hadamard matrices cannot contain 0s. A Hadamard matrix H is called skew if

H + H^T = 2I.

This implies the diagonal elements are all 1s and the elements below the diagonal have the opposite sign of the elements above the diagonal. Since the elements on the diagonal are determined, a skew Hadamard matrix can be sorted using n(n − 1)/2 bits.

Incidentally, there is a conjecture that there exist skew Hadamard matrices of order 4n for all positive n.

[1] There are Hadamard matrices of order 1 and 2, but larger orders must be divisible by 4.

A Hadamard matrix is an orthogonal matrix whose entries are all either 1 or − 1. For example

is a Hadamard matrix of order 2. True to Stigler’s law of eponymy, James Joseph Sylvester investigated Hadamard matrices before Jacques Hadamard. Sylvester saw how to bootstrap the example above into more examples. If H is a Hadamard matrix, then the partitioned matrix

Sylvester’s construction can be generalized as follows. If H_m is a Hadamard matrix of order m and H_n is a Hadamard matrix of order n, the the Kronecker product H_m⊗H_n is a Hadamard matrix of order mn. That is, you can form a new Hadamard matrix by taking the matrix H_m and replacing ±1 with the matrix ±H_n.

Let S be the set of all possible Hadamard matrix orders. By the construction above, this set is closed under multiplication. Since 2 is in S, every power of 2 is in S. Hadamard proved that all n ≥ 4 in S are multiples of 4. That is, the condition 4 | n is necessary. He conjectured that it was also sufficient, though that has not been proven.

So the big question is what is the set S. Is there some multiple of 4 not in S? Until that question is answered, what is the smallest multiple of 4 not known to be in S? Hadamard matrices are useful in applications, so constructing Hadamard matrices of various orders is useful even while Hadamard’s conjecture remains open. For example, see the next post for how NASA used Hadamard matrices to transmit photographic images back from Mars.

Paley’s method

Raymond Paley came up with a way of constructing Hadamard matrices of size q + 1 if q is a prime power congruent to 3 mod 4, and of size 2(q + 1) if q is a prime power congruent to 1 mod 4. Let’s see what we can squeeze out of this.

If p is a prime congruent to 1 mod 4, every power of p is also congruent to 1 mod 4, and so there exist Hadamard matrices of order 2(p^k + 1) for every k.

If p is a prime with p = 3 mod 4, then even powers of p are congruent to 1 mod 4 and odd powers of p are congruent to 3 mod 4. So there are Hadamard matrices of order 2(p^2k + 1) and of order p^2k+1 + 1.

Let’s run a script to see what we can learn from this.

from sympy import primerange

s = set()

for p in primerange(20):
    if p % 4 == 1:
        s.update([2*(p**k + 1) for k in range(1, 10)])
    if p % 4 == 3:
        s.update([2*(p**(2*k) + 1) for k in range(1, 6)])
        s.update([p**(2*k + 1) + 1 for k in range(1, 6)])
print(sorted(s)[:20])

This prints

12, 20, 28, 36, 52, 100, 164, 244, 252, 340]

We can add 16 to the list because it’s a power of 2, and we can add 24 because it’s 2 × 12, etc. But there doesn’t seem to be any way to get 44. There is a way to create a Hadamard matrix of order 44, but it doesn’t follow from anything we’ve seen so far.

New records

I have a book published in 1996 that says Hadamard’s conjecture had been verified for n up to 428. Until yesterday, the smallest multiple of 4 for which nobody had found a corresponding Hadamard matrix was 668. Then Levent Alpöge announced that he and his and collaborators found an example of size 668 and filled in all remaining gaps below 2000.

So now the set S is known to contain {1, 2, 4, 8, 12, 16, …, 2000}. It also contains all orders that can be obtained by Paley’s method and other methods. And it contains all products of its elements. But it is not yet known to contain 2004.

Related posts

• Hadamard’s determinant inequality
• Hadamard’s Dirichlet energy example