Hadamard Matrices #2: An Introduction

Inês Guimarães
Inês Guimarães Author
David Carvalho
David Carvalho Editor

Hadamard train departed from Motivation station here. We are now ready to make headway into Introduction Land. Cruising at a pleasant speed, you will now get ready to dive a bit deeper into Hadamard matrices as mathematical objects and understand their algebraic properties and what makes them so special.

As we alluded to before, you will hopefully be fascinated by how such simple ideas translate to such hard problems. Needless to say, you should always keep in mind we are headed to Machine Learning Land, where opportunities to solving these challenges thrive!

All on board!

Hadamard Matrices #2: An Introduction

Basic properties

We begin by introducing some notation. Given the order (or size), an integer \(n \geq 1\), let us denote by \(M_{n \times n}(\{ \pm 1 \})\) the set of all \(n \times n\) (square) matrices whose entries are either \(1\) or \(-1\). This set grows extremely fast - for an order \(n\), there are \(2^{n^2}\) such matrices.

Let us also think of the \(i\)-th row of these matrices as a \(n\)-dimensional vector \(R_i\). Out of all matrices \(H_n \in M_{n \times n}(\{ \pm 1 \})\), Hadamard matrices are those ones for which \(R_i \cdot R_j = 0\), for all pairs of different rows \(R_1, \dots, R_n\).

Here, \(\cdot\) is the usual dot product \(\mathbf{u} \cdot \mathbf{v} = \sum_{i=1}^{n}u_i v_i\) for vectors with \(n\) components.
This condition simply means different rows of \(H_n\) are pairwise orthogonal.
For the remaining case when both rows are the same, a simple computation gives

\[R_i \cdot R_i = \underbrace{1^2 + ... + 1^2}_{n \ \rm{times}} = n \ ,\]

since the square of each entry is \(1\) regardless of their value.

We can summarize these conditions in a neat expression - and this will be useful. If we transpose \(H_n\), we simply convert the rows to columns. Multiplying both matrices together thus reduces to applying the orthogonality conditions.
This is depicted in Fig. 1, where we see that the resulting matrix must be 0 everywhere except on the diagonal entries where, by the calculation above, must be \(n\).


\[H_n H_n^T = nI_n \ ,\]

where \(I_n\) is the \(n \ \times n\) identity matrix.

Fig. 1: A matrix representation of the orthogonality conditions of Hadamard matrices. This relation has deep consequences for their determinant. Credits: David Carvalho / Inductiva

Two useful facts arise from this equality. Firstly, we now know that Hadamard matrices are invertible (namely \(H_n^{-1} = H_n^T/n\)). As a consequence, the columns of \(H\) are also pairwise orthogonal.

Secondly we can obtain a bound for their determinants. From Linear Algebra 101, we know that \(\det(A) \det(B) = \det(AB)\) and \(\det(A) = \det(A^{T})\) for matrices \(A\) and \(B\). Now, since \(\det{n I_n} = \underbrace{n \times \dots \times n}_{n \ \rm{times}}\), one obtains \(\det(H_n)^2 = n^n\) i.e. \(|\det(H_n)| = n^{\frac{n}{2}}\).

Hadamard himself generalized this result by proving that, for a matrix \(A\) whose entries are real-valued and bounded i.e. with \(|a_{ij}| \leq M\), the following inequality holds:

\[|\det(A)| \leq M^n n^{\frac{n}{2}}\]

By taking \(M = 1\), we see that indeed Hadamard matrices attain the maximum determinant value among all matrices whose entries lie between \(-1\) and \(1\). In fact, they are the only ones which maximize the determinant, a property that is exploited in many problems (as we shall see in future instalments).

Not all Hadamard matrices are the same

So far, we have managed to disentangle Hadamard matrices from other matrices in \(M_{n \times n}(\{ \pm 1 \})\). Can we devise a way to distinguish different Hadamard matrices among themselves?

It turns out we can solidify this notion mathematically. Think of operations which can be performed on to a Hadamard matrix \(H\), resulting in an output matrix \(H'\).
Since \(\mathbf{R_i} \cdot \mathbf{R_j} = \mathbf{R_j} \cdot \mathbf{R_i}\), it is obvious that if we permute a row or column of \(H\), the resulting matrix \(H'\) still is a Hadamard matrix.

The same occurs whenever we negate the rows or columns i.e. multiply by \(-1\). The Hadamard conditions are still observed since, by replacing \(\mathbf{R_{i}} \rightarrow -\mathbf{R}_{i}\):

  • Orthogonality is retained for any different rows \(i\) and \(j\) since \((-\mathbf{R_i}) \cdot \mathbf{R_j} = - (\mathbf{R_i} \cdot \mathbf{R_j}) = 0\)
  • Each row still satisfies \((-\mathbf{R_i}) \cdot (-\mathbf{R_i}) = \mathbf{R_i} \cdot \mathbf{R_i} = n\).

Note that the reasoning used to both permutations and negations may be applied to both rows and columns alike due to the orthogonality relation we discussed in Fig. 1.

With these two classes of operations, \(H\) and \(H'\) share a similar structure and we say these Hadamard matrices are equivalent. This equivalence relation allows us to bin a bunch of equivalent matrices into a subset termed an equivalence class.

A single matrix is enough to define an equivalence class and we are thus granted some freedom to choose its class representative. We can find somewhat “canonical” matrix forms which suit this task.

For instance, whenever we set all entries along the first column to \(1\), we say that the resulting matrix is seminormalized. For that to happen, it is enough to multiply by \(-1\) every row whose first entry is equal to \(-1\). Similarly, we can also set all entries along the first row to \(1\), requiring every column whose first entry is equal to \(-1\) to be multiplied by \(-1\), obtaining a normalized form of the matrix.

Take the following examples of Hadamard matrices of orders \(1\), \(2\) and \(4\), respectively:

\[\begin{align*} H_1 = \begin{pmatrix} 1 \end{pmatrix}, \quad H_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \quad H_4 = \begin{pmatrix} 1 & -1 & 1 & 1 \\ 1 & 1 & 1 & -1 \\ -1 & 1 & 1 & 1 \\ -1 & -1 & 1 & -1 \end{pmatrix}. \end{align*}\]

An example of a normalized matrix equivalent to the \(4 \times 4\) matrix shown above is:

\[\begin{align*} H'_4 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}. \end{align*}\]

It’s all good in the neighborhood. But what are these notions good for, I heard you ask. Well: when we bunch together Hadamard matrices based on whether they are equivalent or not, we partition the total set of Hadamard matrices of a given order \(n\) into, say, \(m\) chunks. A natural question thus arises:

How many equivalence classes of Hadamard matrices are there for a given order?

Again, this is a question simple enough to understand but is still unsolved. We can’t simply solve it generally for all orders and thus we must resort to working for particular cases.

Fig. 2: Applying row (or column) permutations and negations to a Hadamard matrix results in an equivalent Hadamard matrix. These belong to the same equivalence class, one of \(m\) subsets contained in the set of all Hadamard matrices of a given order \(n\). Credits: David Carvalho / Inductiva

The case \(n=1\) is trivial: there are only \(2\) possible matrices, namely \(\begin{pmatrix} 1 \end{pmatrix}\) and \(\begin{pmatrix} -1 \end{pmatrix}\), and we can generate either by negating the other one - hence only a single class exists i.e. \(m=1\). As for \(n=2\), the same holds: a single equivalence class exists (and we showed you a possible representative \(H_2\)), although we now need both permutations and negations to generate any other case.
In fact, a single equivalence class is still found for orders \(n=4\) and \(n=8\).

However, things start to get interesting as we go to higher orders: the order \(n=16\) admits \(m=3\) classes and for \(n=28\), \(m=294\) classes exist. And we can go on. Unfortunately, not for so long: as of now, this classification has been fully completed only up to order \(n=32\) where at least a whopping number of \(m=3,578,006\) classes exist.
Let that sink for a moment. This is a colossal classification task among \(2^{32^2} \approx 1.7 \times 10^{308}\) matrices. For reference: there are about \(10^{80}\) particles in the known Universe…

Yet an order of 32 feels small. Can we do better?

The big question

Do you remember the question we asked in the first post?

Is there a \(10 \times 10\) board with a “half-match” pattern?

We can now reframe this innocent question in a concrete mathematical way:

Is there at least one equivalence class in the space of all \(10 \times 10\) Hadamard matrices?

In order to answer it positively, we need to only find a single Hadamard matrix. Let us consider a more general scenario. We already know that there are Hadamard matrices of order \(n=1\) and \(n=2\) - but which are other admissible orders \(n > 2\)?

We will start with this result: that there is a Hadamard matrix of order \(n\) if and only if there is a normalized Hadamard matrix of order \(n\). So let us look at its first \(3\) rows:

\[\begin{align*} \begin{pmatrix} 1 & 1 & \cdots & 1 & 1 \\ a_1 & a_2 & \cdots & a_{n-1} & a_n \\ b_1 & b_2 & \cdots & b_{n-1} & b_n \end{pmatrix} \end{align*}\]

Since all entries in the first row equal \(1\), there must be exactly \(\frac{n}{2}\) entries equal to \(1\) and \(\frac{n}{2}\) entries equal to \(-1\) in the remaining rows. This shows that \(n\) must be even, i.e. there can only be nontrivial Hadamard matrices of even order. So do not bother trying to come up with a”half-match” pattern on a \(73 \times 73\) board just because \(73\) is your favourite number!

If \(n > 2\) is even though: is there necessarily a \(n \times n\) Hadamard matrix? Let us analyze with more care our prototype matrix above. In order to establish a relation between all pairs \((a_i, b_i)\), let us keep a count of their occurrences: for instance, let \(p_{+}^{+}\) count the number of occurrences of all positive pairs \((1,1)\) (and likewise for all combinations \(p_{+/-}^{+/-}\)).

Since there are \(\frac{n}{2}\) positive entries in the second row, we get \(p_{+}^{+} + p_{-}^{+} = \frac{n}{2}\) and similarly, there are \(\frac{n}{2}\) negative entries in the third row, so \(p_{-}^{+} + p_{-}^{-} = \frac{n}{2}\).
These two equalities mean that \(p_{+}^{+} = p_{-}^{-}\). We know that \(p_{+}^{+} + p_{-}^{-} = \frac{n}{2}\) - as exactly \(\frac{n}{2}\) entries are matched in this pair of rows. We thus conclude that \(p_{+}^{+} = p_{-}^{-} = \frac{n}{4}\), which shows that \(n>2\) must be a multiple of \(4\).

Therefore, the order of a Hadamard matrix must be \(n = 1\), \(n = 2\) or, more surprisingly, a multiple of \(4\) (say \(n = 4k\) for some integer \(k \geq 1\)).

We are in the position to answer our question: there can be no Hadamard matrix of order \(10\)! (and hence no “half-match” pattern on a \(10 \times 10\) board can exist).

Doesn’t it feel nice when we can get to a definitive answer?

Fig. 3: A failed attempt at finding a “half-pattern” on a \(10 \times 10\) chessboard. Don’t try to find one - none of the \(1.6 \times 10^{30}\) possible combinations will work. Credits: David Carvalho / Inductiva

We also asked ourselves the same question regarding a \(1000 \times 1000\) board. Now, since \(1000 = 4 \times 250\), there is hope in finding a Hadamard matrix of order \(1000\).

However, this is not guaranteed. Were you expecting things to go this smoothly?

A Conjecture

The hope this guarantee is there reflects yet another simple statement:

There is a Hadamard matrix of order \(n =4k\) for every integer \(k \geq 1\).

Hadamard proposed this eponymous conjecture. As usual in Mathematics, this statement is easier conjectured than proved (just like Fermat’s Last Theorem).

Nobody has been able to prove it or refute it yet. For instance, no Hadamard matrix of order \(n= 4 \times 167 = 668\) is known. The lack of an example is certainly not proof (or disproof) of the underlying assertion. It could certainly exist and yet we cannot find a sound reasoning as to why it ought to.

Curiously, a \(1000 \times 1000\) Hadamard matrix has already been found. We would love to show it to you but the margin of this webpage is too narrow for the purpose. Take our word for it.

Finding Hadamard matrices is no easy task but luckily, as we approach Construction Land, we can devise promising ways to construct trials which can allow us to hopefully catch some of these creatures.

So, next up: tune in for Hadamard Matrices #3: It’s Construction Time.


[1] An academic but approachable presentation outlying the fundamentals of Hadamard matrices.
[2] If you want to have a go at finding Hadamard matrices yourself, try Magma - a software package designed for computations in Algebraic Combinatorics.

Recent posts from our blog

Rúben Dhanaraju

Rúben Dhanaraju

David Carvalho

David Carvalho

Fábio Cruz

Fábio Cruz

Luís Sarmento

Luís Sarmento

In this 4th post of the series, we benchmark the performance of a Constraint Programming solver on its own for finding Hadamard matrices.

Fábio Cruz

Fábio Cruz

Maria Castro

Maria Castro

Luís Sarmento

Luís Sarmento

David Carvalho

David Carvalho

Do GPUs solve sparse eigenproblems faster than CPUs? In this post, we answer this question by comparing the SciPy and CuPy eigensolvers.