# Hadamard Matrices #2: An Introduction

**Inês Guimarães**Author

**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

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\).

Therefore,

\[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:

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.

## References

[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

David Carvalho

Fábio Cruz

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

Maria Castro

Luís Sarmento

David Carvalho

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