Hadamard Matrices

[poster]

I have just returned from the ICIAM2019 conference in Valencia, Spain. It was a huge conference -- 4,000+ attendees, dozens of prize and invited talks, hundreds of parallel minisympsia. I gave a talk in a two-part minisymposium organized by Nick Higham and Rob Corless. I outlined the first part of the talk in this blog a month ago. This post outlines the second part, which was about Hadamard matrices. Some of it is taken from a post in this blog five years ago.

Contents

• Hadamard Matrices
• Existence
• Generation
• Baumert92
• References
• code

Hadamard Matrices

The determinant of any matrix cannot be larger than the product of the length of its rows. This leads to Hadamard's inequality, for any $n$ by $n$ matrix, $A$, with elements +1 or -1,

$|\mbox{det}(A)| \le n^{n/2}$

A Hadamard Matrix is a square matrix $H$ with elements +1 or -1 whose rows (or columns) are mutually orthogonal, that is

$H^T H = nI$

A Hadamard matrix achieves equality in the Hadamard inequality. Conversely, any matrix achieving equality must be a Hadamard matrix.

A 2-by-2 Hadamard matrix is

$$ H = \left( \begin{array}{rr} 1 & 1 \\ 1 & -1 \\ \end{array} \right) $$

Notice that

$|\mbox{det}(H)| = 2 = 2^{2/2}$

A direct search of all 3-by-3 matrices shows

$$ A = \left( \begin{array}{rrr} 1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & 1 & -1 \end{array} \right) $$

and its permutations have the largest determinant.

But the rows of $A$ are not mutually orthogonal and

$|\mbox{det}(A)| = 4 < 3^{3/2} = 5.196$

We conclude no 3-by-3 Hadamard matrices exist.

A 4-by-4 Hadamard is

$$ H = \left( \begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{array} \right) $$

Notice

$|\mbox{det}(H)| = 16 = 4^{4/2}$

Existence

These three examples are special cases of this important fact: The order of a Hadamard matrix must be 1, 2, or a multiple of 4. But what about the reverse question, does a Hadamard matrix of order $n = 4k$ exist for every $k$? Nobody knows for sure. This is an important open mathematical problem.

Generation

It is easy to create Hadamard matrices of some sizes. If $H$ is any Hadamard matrix, then so is the block matrix

$$ \left( \begin{array}{rr} H & H \\ H & -H \\ \end{array} \right) $$

You can start a recursion with the 1-by-1 matrix $H = 1$ and generate Hadamard matrices whose orders are powers of two. The MATLAB function hadamard can also start with a 12-by-12 or a 20-by-20 $H$. Here is what you get. Yellow is +1 and blue is -1.



Baumert92

I was present at a milestone in the history of Hadamard matrices, By 1961 it was known how to construct Hadamard matrices for all orders $n \le 100$ that are multiples of four, except $n = 92$. In 1961 I had a summer job at JPL, Caltech's Jet Propulsion Lab. My office was in a temporary trailer and my trailer mate was an algebraist named Len Baumert. Len proudly showed me a color graphic that he had just made with an hour-long computation on JPL's main-frame and that he was proposing for the cover of Scientific American. It was a 92-by-92 matrix made up from 23-by-23 blocks of alternating light and dark cells representing +1 and -1. The graphic didn't make the cover of Scientific American, but I kept my copy for a long time.

Len had filled in the last value of $n$ less than 100. His paper with his colleagues Sol Golomb, a professor at USC, and Marshall Hall, Jr., a professor at Caltech, was published in the prestigious Bulletin of the AMS. It turns out that I had taken a course on difference sets, the mathematics involved in generating the matrix, from Hall at Caltech.

Here is a MATLAB picture and code for Baumert92.



References

Leonard Baumert, S. W. Golomb, and Marshall Hall, Jr, "Discovery of an Hadamard Matrix of Order 92", , Bulletin of the American Mathematical Society 68 (1962), 237-238.

code

type Baumert92.mfunction H = Baumert92% Baumert92 Hadamard matrix of order 92.% H = Baumert92 % Baumert, Golomb, and Hall, Bulletin AMS 68, 1962, 237-238. % http://dx.doi.org/10.1090%2FS0002-9904-1962-10761-7 % First row of 23-by-23 circulants. M = [ '+ + - - - + - - - + - + + - + - - - + - - - +' '+ - + + - + + - - + + + + + + - - + + - + + -' '+ + + - - - + + - + - + + - + - + + - - - + +' '+ + + - + + + - + - - - - - - + - + + + - + +' ]; M = 2*(M(:,1:2:end)=='+')-1; A = toeplitz([1 M(1,end:-1:2)],M(1,:)); B = toeplitz([1 M(2,end:-1:2)],M(2,:)); C = toeplitz([1 M(3,end:-1:2)],M(3,:)); D = toeplitz([1 M(4,end:-1:2)],M(4,:)); H = [A B C D; -B A -D C; -C D A -B; -D -C B A];
Get the MATLAB code

Published with MATLAB® R2018b




更多...