What is a Hadamard Matrix?

A Hadamard matrix is a matrix with all elements equal to $+1$ or $-1$, and for which the rows are mutually orthogonal. If you pick two rows from the matrix and write it as vectors $\bf x$ and $\bf y$, then these are orthogonal if their dot product is zero, written as ${\bf x}\cdot{\bf y}=0$. For a Hadamard matrix, this is true for each combination of two rows. The dot product itself is defined using the elements of the vector. With ${\bf x}=(x_1,\ldots,x_n)$ and ${\bf y}=(y_1,\ldots,y_n)$, it is given by

$${\bf x}\cdot{\bf y}=\sum_{i=1}^n\,x_iy_i.$$

An example of a $4\times 4$ Hadamard matrix is

$$\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1\end{pmatrix}.$$

Any two rows of this matrix orthogonal. For example, the dot product of the third and fourth row is

$$1\!\cdot\!1\,+\,1\!\cdot\!(-1)\,+\,(-1)\!\cdot\!(-1)\,+\,(-1)\!\cdot\!1=0.$$

How to construct a Hadamard matrix?

Defining what a Hadamard matrix is, is one thing. However, constructing one is not necessarily trivial. There is one particularly straightforward method that constructs Hadamard matrices of size $2^n\times 2^n$ for $n\in\mathbb{N}_{>0}$. This method is called Sylverster’s construction. Incidentally, Sylvester is the person who actually discoverd Hadamard matrices in 1867, 26 years before Hadamard started working with them. The method works as follows. You start with the basic Hadamard matrix

$${\bf H}_1= \begin{pmatrix} 1 \end{pmatrix}.$$

The $2\times 2$ matrix is then given by

$${\bf H}_2= \begin{pmatrix} {\bf H}_1 & {\bf H}_1 \\ {\bf H}_1 & -{\bf H}_1 \end{pmatrix}= \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.$$

If you apply the same step again and write it out, this method produces exactly the $4\times 4$ example that is given above. In general, Sylvester’s construction is given by

$${\bf H}_{2^n}= \begin{pmatrix} {\bf H}_{2^{n-1}} & {\bf H}_{2^{n-1}} \\ {\bf H}_{2^{n-1}} & -{\bf H}_{2^{n-1}} \end{pmatrix}.$$

Of course, this method only constructs the $2^n\times 2^n$ Hadamard matrices. There are many different methods for other sizes, but there is no known general method that creates all sizes. And, moreover, there is the point of the next section.

Which sizes of Hadamard Matrices Exist?

This is an open question. The Hadamard conjecture states that a Hadamard matrix exists for matrices of size $4n\times 4n$ with $n\in\mathbb{N}_{>0}$. Currently, the smallest $n$ for which no Hadamard matrix is known, is $668$. This happens to be the house number of the neighbor of the beast, but that must be a coincidence. It is known that an $n\times n$ Hadamard matrix must have $n=1$, $2$, or a multiple of 4.