Hadamard matrices

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

1a. Hadamard matrices

We will be mainly interested in this book in the complex Hadamard matrices, but let us start with some beautiful pure mathematics, regarding the real case. The definition that we need, going back to 19th century work of Sylvester , on topics such as tessellated pavements and ornamental tile-work, is as follows:

Definition

An Hadamard matrix is a square binary matrix,

[[math]] H\in M_N(\pm1) [[/math]]

whose rows are pairwise orthogonal, with respect to the scalar product on [math]\mathbb R^N[/math].

There are many examples of such matrices, and we will discuss this, in what follows. To start with, here is an example, which is a particularly beautiful one:

[[math]] K_4=\begin{pmatrix} -1&1&1&1\\ 1&-1&1&1\\ 1&1&-1&1\\ 1&1&1&-1 \end{pmatrix} [[/math]]

Observe that this matrix has many interesting extra features, such as being symmetric, bistochastic, and circulant. Here is another example, also at [math]N=4[/math], which is interesting too, because it reminds the combinatorics of the Klein group [math]\mathbb Z_2\times\mathbb Z_2[/math]:

[[math]] W_4=\begin{pmatrix} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{pmatrix} [[/math]]

Summarizing, we have examples of Hadamard matrices, usually coming from certain interesting algebraic and combinatorial properties of [math]\mathbb R^N[/math], which are waiting to be explored. In general now, as a first theoretical observation, we do not really need real numbers in order to talk about the Hadamard matrices, because we have:

Proposition

A binary matrix [math]H\in M_N(\pm1)[/math] is Hadamard when its rows have the property that, when comparing any two of them,

[[math]] \begin{matrix} e_1&\ldots&e_N\\ f_1&\ldots&f_N \end{matrix} [[/math]]

the number of matchings [math](e_i=f_i)[/math] equals the number of mismatchings [math](e_i\neq f_i)[/math].

Show Proof

This is clear from definitions. Indeed, the scalar product on [math]\mathbb R^N[/math] is given by:

[[math]] \lt x,y \gt =\sum_ix_iy_i [[/math]]

Thus, when computing the scalar product between two rows, the matchings contribute with [math]1[/math] factors, and the mismatchings with [math]-1[/math] factors, and this gives the result.

■

As a consequence of the above result, we can replace if we want the [math]1,-1[/math] entries of our matrix by any two symbols, of our choice. Here is an example of an Hadamard matrix, and to be more precise, the above matrix [math]W_4[/math], written with this convention:

[[math]] \begin{matrix} \heartsuit&\heartsuit&\heartsuit&\heartsuit\\ \heartsuit&\clubsuit&\heartsuit&\clubsuit\\ \heartsuit&\heartsuit&\clubsuit&\clubsuit\\ \heartsuit&\clubsuit&\clubsuit&\heartsuit \end{matrix} [[/math]]

However, it is probably better to run away from this, and use real numbers instead, as in Definition 1.1, with the idea in mind of connecting the Hadamard matrices to the foundations of modern mathematics, namely Calculus 1 and Calculus 2. So, getting back now to the real numbers, here is our first result:

Proposition

For a square matrix [math]H\in M_N(\pm1)[/math], the following are equivalent:

• The rows of [math]H[/math] are pairwise orthogonal, and so [math]H[/math] is Hadamard.
• The columns of [math]H[/math] are pairwise orthogonal, and so [math]H^t[/math] is Hadamard.
• The rescaled matrix [math]U=H/\sqrt{N}[/math] is orthogonal, [math]U\in O_N[/math].

Show Proof

The idea here is that the equivalence between (1) and (2) is not exactly obvious, but both these conditions can be shown to be equivalent to (3), as follows:

[math](1)\iff(3)[/math] Since the rows of [math]U=H/\sqrt{N}[/math] have norm 1, this matrix is orthogonal precisely when its rows are pairwise orthogonal. But this latter condition is equivalent to the fact that the rows of [math]H=\sqrt{N}U[/math] are pairwise orthogonal, as desired.

[math](2)\iff(3)[/math] The same argument as above shows that [math]H^t[/math] is Hadamard precisely when its rescaling [math]U^t=H^t/\sqrt{N}[/math] is orthogonal. But since a matrix [math]U\in M_N(\mathbb R)[/math] is orthogonal precisely when its transpose [math]U^t\in M_N(\mathbb R)[/math] is orthogonal, this gives the result.

■

As an abstract consequence of the above result, let us record:

Theorem

The set of the [math]N\times N[/math] Hadamard matrices is

[[math]] Y_N=M_N(\pm 1)\cap\sqrt{N}O_N [[/math]]

where [math]O_N[/math] is the orthogonal group, the intersection being taken inside [math]M_N(\mathbb R)[/math].

Show Proof

This follows from the equivalence [math](1)\iff(3)[/math] in Proposition 1.3, which tells us that an arbitrary [math]H\in M_N(\pm1)[/math] belongs to [math]Y_N[/math] if and only if it belongs to [math]\sqrt{N}O_N[/math].

■

As a conclusion to what we have so far, the set [math]Y_N[/math] that we are interested in appears as a kind of set of “special rational points” of the real algebraic manifold [math]\sqrt{N}O_N[/math]. Thus, we are doing some kind of algebraic geometry here, of precise type to be determined. In the simplest case, [math]N=2[/math], the Hadamard matrices are elementary to compute, and the set [math]Y_2[/math] consists precisely of the rational points of [math]\sqrt{2}O_2[/math], the result being as follows:

Theorem

The binary matrices [math]H\in M_2(\pm1)[/math] are split [math]50[/math]-[math]50[/math] between Hadamard and non-Hadamard, the Hadamard ones being as follows,

[[math]] \begin{pmatrix}1&1\\1&-1\end{pmatrix}\ \ \qquad \begin{pmatrix}1&1\\-1&1\end{pmatrix}\ \ \qquad \begin{pmatrix}1&-1\\1&1\end{pmatrix}\ \ \qquad \begin{pmatrix}-1&1\\1&1\end{pmatrix} [[/math]]

[[math]] \begin{pmatrix}1&-1\\-1&-1\end{pmatrix}\qquad \begin{pmatrix}-1&1\\-1&-1\end{pmatrix}\qquad \begin{pmatrix}-1&-1\\1&-1\end{pmatrix}\qquad \begin{pmatrix}-1&-1\\-1&1\end{pmatrix} [[/math]]

and the non-Hadamard ones being the remaining ones. Also, we have [math]Y_2=M_2(\mathbb Q)\cap\sqrt{2}O_2[/math], with the intersection being taken inside [math]M_N(\mathbb R)[/math].

Show Proof

We have two assertions to be proved, which are both elementary:

(1) In what regards the classification, this is best done by using the Hadamard matrix criterion from Proposition 1.2, which at [math]N=2[/math] simply tells us that, once the first row is chosen, the choices for the second row, as for our matrix to be Hadamard, are exactly [math]50\%[/math]. The solutions are those in the statement, listed according to the lexicographic order, with respect to the standard way of reading, left to right, and top to bottom.

(2) In order to prove the second assertion, we use the fact that [math]O_2[/math] consists of 2 types of matrices, namely rotations [math]R_t[/math] and symmetries [math]S_t[/math]. To be more precise, we first have the rotation of angle [math]t\in\mathbb R[/math], which is given by the following formula:

[[math]] R_t=\begin{pmatrix}\cos t&-\sin t\\ \sin t&\cos t\end{pmatrix} [[/math]]

We also have the symmetry with respect to the [math]Ox[/math] axis rotated by [math]t/2\in\mathbb R[/math]:

[[math]] S_t=\begin{pmatrix}\cos t&\sin t\\ \sin t&-\cos t\end{pmatrix} [[/math]]

Now by multiplying everything by [math]\sqrt{2}[/math], we are led to the following formula:

[[math]] \sqrt{2}O_2=\left\{\begin{pmatrix}c&-s\\s&c\end{pmatrix}\,,\ \begin{pmatrix}c&s\\s&-c\end{pmatrix}\Big|c^2+s^2=2\right\} [[/math]]

In order to find now the matrices from [math]\sqrt{2}O_2[/math] having rational entries, we must solve the following equation, over the integers:

[[math]] x^2+y^2=2z^2 [[/math]]

But this is equivalent to [math]y^2-z^2=z^2-x^2[/math], which is impossible for obvious reasons, unless we have [math]x^2=y^2=z^2[/math]. Thus, the rational points come from [math]c^2=s^2=1[/math], and so we have a total of [math]2\times2\times 2=8[/math] rational points, which can only be the points of [math]Y_2[/math].

■

At higher values of [math]N[/math], we cannot expect [math]Y_N[/math] to consist of the rational points of [math]\sqrt{N}O_N[/math]. As a basic counterexample, we have the following matrix, which is not Hadamard:

[[math]] \begin{pmatrix} 2&0&0&0\\ 0&2&0&0\\ 0&0&2&0\\ 0&0&0&2 \end{pmatrix}\in 2O_4 [[/math]]

Summarizing, it is quite unclear what [math]Y_N[/math] is, geometrically speaking. We can, however, solve this question by using complex numbers, in the following way:

Theorem

The Hadamard matrices appear as the real points,

[[math]] Y_N=M_N(\mathbb R)\cap X_N [[/math]]

of the complex Hadamard matrix manifold, which is given by:

[[math]] X_N=M_N(\mathbb T)\cap\sqrt{N}U_N [[/math]]

Thus, [math]Y_N[/math] is the real part of an intersection of smooth real algebraic manifolds.

Show Proof

This is a version of Theorem 1.4, which can be established in two ways:

(1) We can either define a complex Hadamard matrix to be a matrix [math]H\in M_N(\mathbb T)[/math], with [math]\mathbb T[/math] standing as usual for the unit circle in the complex plane, whose rows are pairwise orthogonal, with respect to the scalar product of [math]\mathbb C^N[/math], then work out a straightforward complex analogue of Proposition 1.3, which gives the formula of [math]X_N[/math] in the statement, and then observe that the real points of [math]X_N[/math] are the real Hadamard matrices.

(2) Or, we can directly use Theorem 1.4, which formally gives the result, as follows:

[[math]] \begin{eqnarray*} Y_N &=&M_N(\pm1)\cap\sqrt{N}O_N\\ &=&\big[M_N(\mathbb R)\cap M_N(\mathbb T)\big]\cap\big[M_N(\mathbb R)\cap\sqrt{N}U_N\big]\\ &=&M_N(\mathbb R)\cap\big[M_N(\mathbb T)\cap\sqrt{N}U_N\big]\\ &=&M_N(\mathbb R)\cap X_N \end{eqnarray*} [[/math]]

We will be back to this, and more precisely with full details regarding (1), starting from chapter 5 below, when studying the complex Hadamard matrices.

■

Summarizing, the Hadamard matrices do belong to real algebraic geometry, but in a quite subtle way. We will be back to all this, gradually, in what follows.

1b. Walsh matrices

Let us discuss now the examples of Hadamard matrices, with a systematic study at [math]N=4,6,8,10[/math] and so on, continuing the study from Theorem 1.5. In order to cut a bit from complexity, we can use the following notion:

Definition

Two Hadamard matrices are called equivalent, and we write [math]H\sim K[/math], when it is possible to pass from [math]H[/math] to [math]K[/math] via the following operations:

• Permuting the rows, or the columns.
• Multiplying the rows or columns by [math]-1[/math].

Observe that we do not include the transposition operation [math]H\to H^t[/math] in our list of allowed operations. This is because Proposition 1.3, while looking quite elementary, rests however on a deep linear algebra fact, namely that the transpose of an orthogonal matrix is orthogonal as well, and this can produce complications later on.

As another comment, there is of course a certain group [math]G[/math] acting there, made of two copies of [math]S_N[/math], one for the rows and one for the columns, and of two copies of [math]\mathbb Z_2^N[/math], once again one for the rows, and one for the columns. The equivalence classes of the Hadamard matrices are then the orbits of the action [math]G\curvearrowright Y_N[/math]. It is possible to be a bit more explicit here, with a formula for [math]G[/math] and so on, but we will not need this.

Given an Hadamard matrix [math]H\in M_N(\pm1)[/math], we can use the above two operations in order to put [math]H[/math] in a “nice” form. Although there is no clear definition for what “nice” should mean, for the Hadamard matrices, with this being actually a quite subtle problem, that we will discuss later on, here is something that we can look for:

Definition

An Hadamard matrix is called dephased when it is of the form

[[math]] H=\begin{pmatrix} 1&\ldots&1\\ \vdots&*\\ 1 \end{pmatrix} [[/math]]

that is, when the first row and the first column consist of [math]1[/math] entries only.

Here the terminology comes from the complex Hadamard matrices, introduced in Theorem 1.6 and its proof. Indeed, when regarding [math]H\in M_N(\pm1)[/math] as a complex matrix, [math]H\in M_N(\mathbb T)[/math], the [math]-1[/math] entries have “phases”, equal to [math]\pi[/math], and assuming that [math]H[/math] is dephased means to assume that we have no phases, on the first row and the first column.

Observe that, up to the equivalence relation, any Hadamard matrix [math]H\in M_N(\pm1)[/math] can be put in dephased form. Moreover, the dephasing operation is unique, if we use only the operations (2) in Definition 1.7, namely row and column multiplications by [math]-1[/math]. The point now is that, with these notions in hand, we can formulate a nice classification result:

Theorem

There is only one Hadamard matrix at [math]N=2[/math], namely

[[math]] W_2=\begin{pmatrix}1&1\\ 1&-1\end{pmatrix} [[/math]]

up to the above equivalence relation for such matrices.

Show Proof

The matrix in the statement [math]W_2[/math], called Walsh matrix, is clearly Hadamard. Conversely, given [math]H\in M_N(\pm1)[/math] Hadamard, we can dephase it, as follows:

[[math]] \begin{pmatrix}a&b\\c&d\end{pmatrix} \to\begin{pmatrix}1&1\\ac&bd\end{pmatrix} \to\begin{pmatrix}1&1\\1&abcd\end{pmatrix} [[/math]]

Now since the dephasing operation preserves the class of the Hadamard matrices, we must have [math]abcd=-1[/math], and so we obtain by dephasing the matrix [math]W_2[/math].

■

At [math]N=3[/math] we cannot have examples, due to the orthogonality condition between the rows, which forces [math]N[/math] to be even, for obvious reasons. At [math]N=4[/math] now, we have several examples. In order to discuss them, let us start with:

Proposition

If [math]H\in M_M(\pm1)[/math] and [math]K\in M_N(\pm1)[/math] are Hadamard matrices, then so is their tensor product, constructed in double index notation as follows:

[[math]] H\otimes K\in M_{MN}(\pm1)\quad,\quad (H\otimes K)_{ia,jb}=H_{ij}K_{ab} [[/math]]

In particular the Walsh matrices, [math]W_N=W_2^{\otimes n}[/math] with [math]N=2^n[/math], are all Hadamard.

Show Proof

The matrix in the statement [math]H\otimes K[/math] has indeed [math]\pm1[/math] entries, and its rows [math]R_{ia}[/math] are pairwise orthogonal, as shown by the following computation:

[[math]] \begin{eqnarray*} \lt R_{ia},R_{kc} \gt &=&\sum_{jb}H_{ij}K_{ab}\cdot H_{kj}K_{cb}\\ &=&\sum_jH_{ij}H_{kj}\sum_bK_{ab}K_{cb}\\ &=&M\delta_{ik}\cdot N\delta_{ac}\\ &=&MN\delta_{ia,kc} \end{eqnarray*} [[/math]]

As for the second assertion, this follows from this, [math]W_2[/math] being Hadamard.

■

Before going further, we should clarify a bit our tensor product notations. In order to write [math]H\in M_N(\pm1)[/math] the indices of [math]H[/math] must belong to [math]\{1,\ldots,N\}[/math], or at least to an ordered set [math]\{\alpha_1,\ldots,\alpha_N\}[/math]. But with double indices we are indeed in this latter situation, because we can use the lexicographic order on these indices. To be more precise, by using the lexicographic order on the double indices, we have the following result:

Proposition

Given [math]H\in M_M(\pm1)[/math] and [math]K\in M_N(\pm1)[/math], we have

[[math]] H\otimes K=\begin{pmatrix} H_{11}K&\ldots&H_{1M}K\\ \vdots&&\vdots\\ H_{M1}K&\ldots&H_{MM}K \end{pmatrix} [[/math]]

with respect to the lexicographic order on the double indices.

Show Proof

We recall that the tensor product is given by [math](H\otimes K)_{ia,jb}=H_{ij}K_{ab}[/math]. Now by using the lexicographic order on the double indices, we obtain:

[[math]] \begin{eqnarray*} H\otimes K &=&\begin{pmatrix} (H\otimes K)_{11,11}&(H\otimes K)_{11,12}&\ldots&(H\otimes K)_{11,MN}\\ (H\otimes K)_{12,11}&(H\otimes K)_{12,12}&\ldots&(H\otimes K)_{12,MN}\\ \vdots&\vdots&&\vdots\\ \vdots&\vdots&&\vdots\\ (H\otimes K)_{MN,11}&(H\otimes K)_{MN,12}&\ldots&(H\otimes K)_{MN,MN} \end{pmatrix}\\ &&\\ &=&\begin{pmatrix} H_{11}K_{11}&H_{11}K_{12}&\ldots&H_{1M}K_{MN}\\ H_{11}K_{21}&H_{11}K_{22}&\ldots&H_{1M}K_{2N}\\ \vdots&\vdots&&\vdots\\ \vdots&\vdots&&\vdots\\ H_{M1}K_{N1}&H_{M1}K_{N2}&\ldots&H_{MM}K_{NN} \end{pmatrix} \end{eqnarray*} [[/math]]

Thus, by making blocks, we are led to the formula in the statement.

■

As a basic example for the tensor product construction, the matrix [math]W_4[/math], obtained by tensoring the matrix [math]W_2[/math] with itself, is given by:

[[math]] W_4 =\begin{pmatrix}W_2&W_2\\ W_2&-W_2\end{pmatrix} =\begin{pmatrix}1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1\end{pmatrix} [[/math]]

Getting back now to our classification work, here is the result at [math]N=4[/math]:

Theorem

There is only one Hadamard matrix at [math]N=4[/math], namely

[[math]] W_4=W_2\otimes W_2 [[/math]]

up to the standard equivalence relation for such matrices.

Show Proof

Consider an Hadamard matrix [math]H\in M_4(\pm1)[/math], assumed to be dephased:

[[math]] H=\begin{pmatrix}1&1&1&1\\ 1&a&b&c\\ 1&d&e&f\\ 1&g&h&i\end{pmatrix} [[/math]]

By orthogonality of the first 2 rows, we must have [math]\{a,b,c\}=\{-1,-1,1\}[/math]. Thus by permuting the last 3 columns, we can assume that our matrix is as follows:

[[math]] H=\begin{pmatrix}1&1&1&1\\ 1&-1&1&-1\\ 1&m&n&o\\ 1&p&q&r\end{pmatrix} [[/math]]

Now by orthogonality of the first 2 columns, we must have [math]\{m,p\}=\{-1,1\}[/math]. Thus by permuting the last 2 rows, we can further assume that our matrix is as follows:

[[math]] H=\begin{pmatrix}1&1&1&1\\ 1&-1&1&-1\\ 1&1&x&y\\ 1&-1&z&t\end{pmatrix} [[/math]]

But this gives the result, because the orthogonality of the rows gives [math]x=y=-1[/math]. Indeed, with these values of [math]x,y[/math] plugged in, our matrix becomes:

[[math]] H=\begin{pmatrix}1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&z&t\end{pmatrix} [[/math]]

Now from the orthogonality of the columns we obtain:

[[math]] z=-1\ ,\ t=1 [[/math]]

Thus, up to equivalence of Hadamard matrices we have [math]H=W_4[/math], as claimed.

■

The case [math]N=5[/math] is excluded, because the orthogonality condition between the rows forces [math]N\in 2\mathbb N[/math]. The point now is that [math]N=6[/math] is excluded as well, because we have:

Theorem

The size of an Hadamard matrix [math]H\in M_N(\pm1)[/math] must satisfy

[[math]] N\in\{2\}\cup 4\mathbb N [[/math]]

with this coming from the orthogonality condition between the first [math]3[/math] rows.

Show Proof

By permuting the rows and columns or by multiplying them by [math]-1[/math], as to rearrange the first 3 rows, we can always assume that our matrix looks as follows:

[[math]] H=\begin{pmatrix} 1\ldots\ldots 1&1\ldots\ldots 1&1\ldots\ldots 1&1\ldots\ldots 1\\ 1\ldots\ldots 1&1\ldots\ldots 1&-1\ldots -1&-1\ldots -1\\ 1\ldots\ldots 1&-1\ldots -1&1\ldots\ldots 1&-1\ldots -1\\ \underbrace{\ldots\ldots\ldots}_x&\underbrace{\ldots\ldots\ldots}_y&\underbrace{\ldots\ldots\ldots}_z&\underbrace{\ldots\ldots\ldots}_t \end{pmatrix} [[/math]]

Now if we denote by [math]x,y,z,t[/math] the sizes of the block columns, as indicated, the orthogonality conditions between the first 3 rows give the following system of equations:

[[math]] (1\perp 2)\quad:\quad x+y=z+t [[/math]]

[[math]] (1\perp 3)\quad:\quad x+z=y+t [[/math]]

[[math]] (2\perp 3)\quad:\quad x+t=y+z [[/math]]

The numbers [math]x,y,z,t[/math] being such that the average of any two equals the average of the other two, and so equals the global average, the solution of our system is:

[[math]] x=y=z=t [[/math]]

We therefore conclude that the size of our Hadamard matrix, which is the number [math]N=x+y+z+t[/math], must be a multiple of 4, as claimed.

■

The above result is something very interesting, and we should mention that a similar analysis with 4 rows or more does not give any further restriction on the possible values of the size [math]N\in\mathbb N[/math]. In fact, the celebrated Hadamard Conjecture (HC), that we will discuss in a moment, states that there should be an Hadamard matrix at any [math]N\in 4\mathbb N[/math].

Now back to our small [math]N[/math] study, the case [math]N=6[/math] being excluded by Theorem 1.13, we have to discuss the case [math]N=8[/math]. Here we have as basic example the Walsh matrix [math]W_8[/math], and we will prove that, up to equivalence, this is the only Hadamard matrix at [math]N=8[/math]. In order to prove this, we will use the [math]3\times N[/math] matrix analysis from the proof of Theorem 1.13. To be more precise, we will first improve this into a [math]4\times N[/math] matrix result, and then, by assuming [math]N=8[/math], we will discuss the case where we have 5 rows or more. Let us start by giving a name to the rectangular matrices that we are interested in:

Definition

A partial Hadamard matrix (PHM) is a rectangular matrix

[[math]] H\in M_{M\times N}(\pm1) [[/math]]

whose rows are pairwise orthogonal, with respect to the scalar product of [math]\mathbb R^N[/math].

We refer to Hall , Ito and Verheiden for a number of results regarding the PHM. In what follows we will just develop some basic theory, useful in connection with our [math]N=8[/math] questions, but we will be back to the PHM, later. We first have:

Definition

Two PHM are called equivalent when we can pass from one to the other by permuting rows or columns, or multiplying the rows or columns by [math]-1[/math]. Also:

• We say that a PHM is in dephased form when its first row and its first column consist of [math]1[/math] entries.
• We say that a PHM is in standard form when it is dephased, with the [math]1[/math] entries moved to the left as much as possible, by proceeding from top to bottom.

With these notions in hand, let us go back now to the proof of Theorem 1.13. The study there concerns the [math]3\times N[/math] case, and we can improve this, as follows:

Proposition

The standard form of the dephased PHM at [math]M=2,3,4[/math] is as follows, with [math]\pm[/math] standing respectively for various horizontal vectors filled with [math]\pm1[/math],

[[math]] H=\begin{pmatrix}+&+\\\underbrace{+}_{N/2}&\underbrace{-}_{N/2}\end{pmatrix} [[/math]]

[[math]] H=\begin{pmatrix}+&+&+&+\\+&+&-&-\\\underbrace{+}_{N/4}&\underbrace{-}_{N/4}&\underbrace{+}_{N/4}&\underbrace{-}_{N/4}\end{pmatrix} [[/math]]

[[math]] H=\begin{pmatrix} +&+&+&+&+&+&+&+\\ +&+&+&+&-&-&-&-\\ +&+&-&-&+&+&-&-\\ \underbrace{+}_a&\underbrace{-}_b&\underbrace{+}_b&\underbrace{-}_a&\underbrace{+}_b&\underbrace{-}_a&\underbrace{+}_a&\underbrace{-}_b \end{pmatrix} [[/math]]

and with [math]a,b\in\mathbb N[/math] being subject to the condition [math]a+b=N/4[/math].

Show Proof

Here the [math]2\times N[/math] assertion is clear, and the [math]3\times N[/math] assertion is something that we already know. Let us pick now an arbitrary partial Hadamard matrix [math]H\in M_{4\times N}(\pm1)[/math], assumed to be in standard form, as in Definition 1.15 (2). According to the [math]3\times N[/math] result, applied to the upper [math]3\times N[/math] part of our matrix, our matrix must look as follows:

[[math]] H=\begin{pmatrix} +&+&+&+&+&+&+&+\\ +&+&+&+&-&-&-&-\\ +&+&-&-&+&+&-&-\\ \underbrace{+}_x&\underbrace{-}_{x'}&\underbrace{+}_{y'}&\underbrace{-}_y&\underbrace{+}_{z'}&\underbrace{-}_z&\underbrace{+}_t&\underbrace{-}_{t'} \end{pmatrix} [[/math]]

To be more precise, our matrix must be indeed of the above form, with [math]x,y,z,t[/math] and [math]x',y',z',t'[/math] being certain integers, subject to the following relations:

[[math]] x+x'=y+y'=z+z'=t+t'=\frac{N}{4} [[/math]]

In terms of these parameters, the missing orthogonality conditions are:

[[math]] (1\perp 4)\quad:\quad x+y'+z'+t=x'+y+z+t' [[/math]]

[[math]] (2\perp 4)\quad:\quad x+y'+z+t'=x'+y+z'+t [[/math]]

[[math]] (3\perp 4)\quad:\quad x+y+z'+t'=x'+y'+z+t [[/math]]

Now observe that these orthogonality conditions can be written as follows:

[[math]] (x-x')-(y-y')-(z-z')+(t-t')=0 [[/math]]

[[math]] (x-x')-(y-y')+(z-z')-(t-t')=0 [[/math]]

[[math]] (x-x')+(y-y')-(z-z')-(t-t')=0 [[/math]]

But this latter system can be solved by using the basic averaging argument from the proof of Theorem 1.13, the solution being as follows:

[[math]] x-x'=y-y'=z-z'=t-t' [[/math]]

Now by putting everything together, the conditions to be satisfied by the block lengths are as follows, with [math]a,b\in\mathbb N[/math] being subject to the condition [math]a+b=N/4[/math]:

[[math]] x=y=z=t=a [[/math]]

[[math]] x'=y'=z'=t'=b [[/math]]

Thus, we are led to the conclusion in the statement.

■

In the case [math]N=8[/math], that we are interested in here, in view of our classification program from the square matrix case, we have the following more precise result:

Proposition

There are exactly two [math]4\times 8[/math] partial Hadamard matrices, namely

[[math]] I=(W_4\ W_4) [[/math]]

[[math]] J=(W_4\ K_4) [[/math]]

us to the standard equivalence relation for such matrices.

Show Proof

We use the last assertion in Proposition 1.16, regarding the [math]4\times N[/math] partial Hadamard matrices, at [math]N=8[/math]. In the case [math]a=2,b=0[/math], the solution is:

[[math]] P=\begin{pmatrix} +&+&+&+&&+&+&+&+\\ +&+&+&+&&-&-&-&-\\ +&+&-&-&&+&+&-&-\\ +&+&-&-&&-&-&+&+ \end{pmatrix} [[/math]]

In the case [math]a=1,b=1[/math], the solution is:

[[math]] Q=\begin{pmatrix} +&+&+&+&&+&+&+&+\\ +&+&+&+&&-&-&-&-\\ +&+&-&-&&+&+&-&-\\ +&-&+&-&&+&-&+&- \end{pmatrix} [[/math]]

Finally, in the case [math]a=0,b=2[/math], the solution is:

[[math]] R=\begin{pmatrix} +&+&+&+&&+&+&+&+\\ +&+&+&+&&-&-&-&-\\ +&+&-&-&&+&+&-&-\\ -&-&+&+&&+&+&-&- \end{pmatrix} [[/math]]

Now observe that, by permuting the columns of [math]P[/math], we can obtain the following matrix, which is precisely the matrix [math]I=(W_4\ W_4)[/math] from the statement:

[[math]] I=\begin{pmatrix} +&+&+&+&&+&+&+&+\\ +&-&+&-&&+&-&+&-\\ +&+&-&-&&+&+&-&-\\ +&-&-&+&&+&-&-&+ \end{pmatrix} [[/math]]

Also, by permuting the columns of [math]Q[/math], we can obtain the following matrix, which is equivalent to the matrix [math]J=(W_4\ K_4)[/math] from the statement:

[[math]] J'=\begin{pmatrix} +&+&+&+&&+&+&+&+\\ +&-&+&-&&-&-&+&+\\ +&+&-&-&&-&+&-&+\\ +&-&-&+&&-&+&+&- \end{pmatrix} [[/math]]

Finally, regarding the last solution, [math]R[/math], by switching the sign on the last row we obtain [math]R\sim P[/math], and so we have [math]R\sim P\sim I[/math], which finishes the proof.

■

We can now go back to the classification problems for the usual, square Hadamard matrices at [math]N=8[/math], and we have here the following result:

Theorem

The third Walsh matrix, namely

[[math]] W_8=\begin{pmatrix}W_4&W_4\\W_4&-W_4\end{pmatrix} [[/math]]

is the unique Hadamard matrix at [math]N=8[/math], up to equivalence.

Show Proof

We use Proposition 1.17, which splits the discussion into two cases:

\underline{Case 1}. We must look here for completions of the following matrix [math]I[/math]:

[[math]] I=\begin{pmatrix} 1&1&1&1&&1&1&1&1\\ 1&-1&1&-1&&1&-1&1&-1\\ 1&1&-1&-1&&1&1&-1&-1\\ 1&-1&-1&1&&1&-1&-1&1 \end{pmatrix} [[/math]]

This is something quite technical, which can be basically done in 3 steps, as follows:

(1) Let us first try to complete this partial [math]4\times 8[/math] Hadamard matrix into a partial [math]5\times 8[/math] Hadamard matrix. The completion must look as follows:

[[math]] I'=\begin{pmatrix} 1&1&1&1&&1&1&1&1\\ 1&-1&1&-1&&1&-1&1&-1\\ 1&1&-1&-1&&1&1&-1&-1\\ 1&-1&-1&1&&1&-1&-1&1\\ a&b&c&d&&a'&b'&c'&d' \end{pmatrix} [[/math]]

The system of equations for the orthogonality conditions is as follows:

[[math]] (1\perp 5)\quad:\quad a+b+c+d+a'+b'+c'+d'=0 [[/math]]

[[math]] (2\perp 5)\quad:\quad a-b+c-d+a'-b'+c'-d'=0 [[/math]]

[[math]] (3\perp 5)\quad:\quad a+b-c-d+a'+b'-c'-d'=0 [[/math]]

[[math]] (4\perp 5)\quad:\quad a-b-c+d+a'-b'-c'+d'=0 [[/math]]

Now observe that this system of equations can be written as follows:

[[math]] (a+a')+(b+b')+(c+c')+(d+d')=0 [[/math]]

[[math]] (a+a')-(b+b')+(c+c')-(d+d')=0 [[/math]]

[[math]] (a+a')+(b+b')-(c+c')-(d+d')=0 [[/math]]

[[math]] (a+a')-(b+b')-(c+c')+(d+d')=0 [[/math]]

Since the matrix of this latter system is the Walsh [math]W_4[/math], which is Hadamard, and so rescaled orthogonal, and in particular invertible, the solution is:

[[math]] (a',b',c',d')=-(a,b,c,d) [[/math]]

Thus, in order to complete [math]I[/math] into a partial [math]5\times 8[/math] Hadamard matrix, we can pick any vector [math](a,b,c,d)\in(\pm1)^4[/math], and then set [math](a',b',c',d')=-(a,b,c,d)[/math].

(2) Now let us try to complete [math]I[/math] into a full Hadamard matrix [math]H\in M_8(\pm1)[/math]. By using the above observation, applied to each of the 4 lower rows of [math]H[/math], we conclude that [math]H[/math] must be of the following special form, with [math]L\in M_4(\pm1)[/math] being a certain matrix:

[[math]] H=\begin{pmatrix}W_4&W_4\\L&-L\end{pmatrix} [[/math]]

Now observe that, in order for [math]H[/math] to be Hadamard, [math]L[/math] must be Hadamard. Thus, the solutions are those above, with [math]L\in M_4(\pm1)[/math] being Hadamard.

(3) As a third step now, let us recall from Theorem 1.12 that we must have [math]L\sim W_4[/math]. However, in relation with our problem, we cannot really use this in order to conclude directly that we have [math]H\sim W_8[/math]. To be more precise, in order not to mess up the structure of [math]I=(W_4\ W_4)[/math], we are allowed now to use only operations on the rows. And the conclusion here is that, up to equivalence, we have 2 solutions, as follows:

[[math]] P=\begin{pmatrix}W_4&W_4\\W_4&-W_4\end{pmatrix}\quad,\quad Q=\begin{pmatrix}W_4&W_4\\K_4&-K_4\end{pmatrix} [[/math]]

We will see in moment that these two solutions are actually equivalent, but let us pause now our study of Case 1, after all this work done, and discuss Case 2.

\underline{Case 2}. Here we must look for completions of the following matrix [math]J[/math]:

[[math]] J=\begin{pmatrix} 1&1&1&1&&-1&1&1&1\\ 1&-1&1&-1&&1&-1&1&1\\ 1&1&-1&-1&&1&1&-1&1\\ 1&-1&-1&1&&1&1&1&-1 \end{pmatrix} [[/math]]

Let us first try to complete this partial [math]4\times 8[/math] Hadamard matrix into a partial [math]5\times 8[/math] Hadamard matrix. The completion must look as follows:

[[math]] J'=\begin{pmatrix} 1&1&1&1&&-1&1&1&1\\ 1&-1&1&-1&&1&-1&1&1\\ 1&1&-1&-1&&1&1&-1&1\\ 1&-1&-1&1&&1&1&1&-1\\ a&b&c&d&&x&y&z&t \end{pmatrix} [[/math]]

The system of equations for the orthogonality conditions is as follows:

[[math]] (1\perp 5)\quad:\quad a+b+c+d-x+y+z+t=0 [[/math]]

[[math]] (2\perp 5)\quad:\quad a-b+c-d+x-y+z+t=0 [[/math]]

[[math]] (3\perp 5)\quad:\quad a+b-c-d+x+y-z+t=0 [[/math]]

[[math]] (4\perp 5)\quad:\quad a-b-c+d+x+y+z-t=0 [[/math]]

When regarded as a system in [math]x,y,z,t[/math], the matrix of the system is [math]K_4[/math], which is invertible. Thus, the vector [math](x,y,z,t)[/math] is uniquely determined by the vector [math](a,b,c,d)[/math]:

[[math]] (a,b,c,d)\to(x,y,z,t) [[/math]]

We have 16 vectors [math](a,b,c,d)\in(\pm1)^4[/math] to be tried, and the first case, covering 8 of them, is that of the row vectors of [math]\pm W_4[/math]. Here we have an obvious solution, with [math](x,y,z,t)[/math] appearing at right of [math](a,b,c,d)[/math] inside the following matrices, which are Hadamard:

[[math]] R=\begin{pmatrix}W_4&K_4\\W_4&-K_4\end{pmatrix}\quad,\quad S=\begin{pmatrix}W_4&K_4\\-W_4&K_4\end{pmatrix} [[/math]]

As for the second situation, this is that of the 8 binary vectors [math](a,b,c,d)\in(\pm1)^4[/math] which are not row vectors of [math]\pm W_4[/math]. But this is the same as saying that, up to permutations, we have [math](a,b,c,d)=\pm(-1,1,1,1)[/math]. In this latter case, and with [math]+[/math] sign, the system is:

[[math]] -x+y+z+t=-2 [[/math]]

[[math]] x-y+z+t=2 [[/math]]

[[math]] x+y-z+t=2 [[/math]]

[[math]] x+y+z-t=2 [[/math]]

By summing the first equation with the other ones we obtain the following system, whose solution is [math]y=z=t=0[/math], not corresponding to an Hadamard matrix:

[[math]] y+z=y+t=z+t=0 [[/math]]

Summarizing, we are done with the [math]5\times 8[/math] completion problem in Case 2, the solutions coming from the rows of the matrices [math]R,S[/math] above. Now when using this, as for getting up to full [math]8\times8[/math] completions, the [math]R,S[/math] cases obviously cannot mix, and so we are left with the Hadamard matrices [math]R,S[/math], as being the only solutions. In order to conclude now, observe that we have [math]R=Q^t[/math] and [math]R\sim S[/math]. Also, we have [math]P\sim Q[/math], and this finishes the proof.

■

The above proof was of course quite long. It is possible to improve a bit things, with various algebraic tricks, but basically this is how the situation is, with each classification result for the Hadamard matrices needing a lot of routine row-by-row study.

1c. Paley matrices

We have seen that the Hadamard matrices can be classified up to order [math]N=8[/math], with the Walsh matrices being the only ones. We discuss now the case [math]N\geq12[/math], where new phenomena appear. At [math]N=12[/math] there is no Walsh matrix, but we can use a construction due to Paley . Let [math]q=p^r[/math] be an odd prime power, consider the associated finite field [math]\mathbb F_q[/math], and then consider the quadratic character [math]\chi:\mathbb F_q\to\{-1,0,1\}[/math], given by:

[[math]] \chi(a)=\begin{cases} 0&{\rm if}\ a=0\\ 1&{\rm if}\ a=b^2,b\neq0\\ -1&{\rm otherwise} \end{cases} [[/math]]

We can construct then the following matrix, with indices in [math]\mathbb F_q[/math]:

[[math]] Q_{ab}=\chi(b-a) [[/math]]

With these conventions, the Paley construction of Hadamard matrices, which works at [math]N=12[/math] and at many other values of [math]N\in4\mathbb N[/math], is as follows:

Theorem

Given an odd prime power [math]q=p^r[/math], construct [math]Q_{ab}=\chi(b-a)[/math] as above. We have then constructions of Hadamard matrices, as follows:

• Paley [math]1[/math]: if [math]q=3(4)[/math] we have a matrix of size [math]N=q+1[/math], as follows:
  [[math]] P_N^1=1+\begin{pmatrix} 0&1&\ldots&1\\ -1\\ \vdots&&Q\\ -1 \end{pmatrix} [[/math]]
• Paley [math]2[/math]: if [math]q=1(4)[/math] we have a matrix of size [math]N=2q+2[/math], as follows:
  [[math]] P_N^2=\begin{pmatrix} 0&1&\ldots&1\\ 1\\ \vdots&&Q\\ 1 \end{pmatrix}\quad:\quad 0\to\begin{pmatrix}1&-1\\ -1&-1\end{pmatrix}\quad,\quad\pm1\to\pm\begin{pmatrix}1&1\\1&-1\end{pmatrix} [[/math]]

These matrices are skew-symmetric [math](H+H^t=2)[/math], respectively symmetric [math](H=H^t)[/math].

Show Proof

In order to simplify the presentation, we will denote by [math]1[/math] all the identity matrices, of any size, and by [math]\mathbb I[/math] all the rectangular all-one matrices, of any size as well. It is elementary to check that the matrix [math]Q_{ab}=\chi(a-b)[/math] has the following properties:

[[math]] QQ^t=q1-\mathbb I [[/math]]

[[math]] Q\mathbb I=\mathbb IQ=0 [[/math]]

In addition, we have the following formulae, which are elementary as well, coming from the fact that [math]-1[/math] is a square in [math]\mathbb F_q[/math] precisely when [math]q=1(4)[/math]:

[[math]] q=1(4)\implies Q=Q^t\ \ \, [[/math]]

[[math]] q=3(4)\implies Q=-Q^t [[/math]]

With these observations in hand, the proof goes as follows:

(1) With our conventions for the symbols [math]1[/math] and [math]\mathbb I[/math], explained above, the matrix in the statement is as follows:

[[math]] P_N^1=\begin{pmatrix}1&\mathbb I\\ -\mathbb I&1+Q\end{pmatrix} [[/math]]

With this formula in hand, the Hadamard matrix condition follows from:

[[math]] \begin{eqnarray*} P_N^1(P_N^1)^t &=&\begin{pmatrix}1&\mathbb I\\ -\mathbb I&1+Q\end{pmatrix}\begin{pmatrix}1&-\mathbb I\\ \mathbb I&1-Q\end{pmatrix}\\ &=&\begin{pmatrix}N&0\\ 0&\mathbb I+1-Q^2\end{pmatrix}\\ &=&\begin{pmatrix}N&0\\ 0&N\end{pmatrix} \end{eqnarray*} [[/math]]

(2) If we denote by [math]G,F[/math] the matrices in the statement, which replace respectively the [math]0,1[/math] entries, then we have the following formula for our matrix:

[[math]] P_N^2=\begin{pmatrix}0&\mathbb I\\ \mathbb I&Q\end{pmatrix}\otimes F+1\otimes G [[/math]]

With this formula in hand, the Hadamard matrix condition follows from:

[[math]] \begin{eqnarray*} (P_N^2)^2 &=&\begin{pmatrix}0&\mathbb I\\ \mathbb I&Q\end{pmatrix}^2\otimes F^2+\begin{pmatrix}1&0\\ 0&1\end{pmatrix}\otimes G^2+\begin{pmatrix}0&\mathbb I\\ \mathbb I&Q\end{pmatrix}\otimes(FG+GF)\\ &=&\begin{pmatrix}q&0\\ 0&q\end{pmatrix}\otimes 2+\begin{pmatrix}1&0\\ 0&1\end{pmatrix}\otimes 2+\begin{pmatrix}0&\mathbb I\\ \mathbb I&Q\end{pmatrix}\otimes0\\ &=&\begin{pmatrix}N&0\\ 0&N\end{pmatrix} \end{eqnarray*} [[/math]]

Finally, the last assertion is clear, from the above formulae relating [math]Q,Q^t[/math].

■

As an illustration for the above result, we have:

Theorem

We have Paley [math]1[/math] and [math]2[/math] matrices at [math]N=12[/math], which are equivalent:

[[math]] P_{12}^1\sim P_{12}^2 [[/math]]

In fact, this matrix is the unique Hadamard one at [math]N=12[/math], up to equivalence.

Show Proof

We have [math]12=11+1[/math], with [math]11=3(4)[/math] being prime, so the Paley 1 construction applies indeed, with the first row vector of [math]Q[/math] being:

[[math]] q=(0+-+++---+-) [[/math]]

Also, we have [math]12=2\times 5+2[/math], with [math]5=1(4)[/math] being prime, so the Paley 2 construction applies as well, with the first row vector of [math]Q[/math] being:

[[math]] q=(0+--+) [[/math]]

It is routine then to check that we have [math]P_{12}^1\sim P_{12}^2[/math], by some computations in the spirit of those from the end of the proof of Theorem 1.18, and with the matrix [math]P_{12}\sim P_{12}^1\sim P_{12}^2[/math] being as follows, with the [math]\pm[/math] signs standing for [math]\pm1[/math] entries:

[[math]] P_{12}=\left( \begin{array}{ccccccccccccccc} +&+&+&+&&-&+&+&+&&-&+&+&+\\ +&-&+&-&&+&-&+&+&&+&-&+&+\\ +&+&-&-&&+&+&-&+&&+&+&-&+\\ +&-&-&+&&+&+&+&-&&+&+&+&-\\ \\ -&+&-&-&&+&-&+&+&&-&+&+&-\\ -&+&+&+&&+&+&-&+&&+&-&+&-\\ -&-&-&+&&+&+&+&+&&-&-&-&+\\ +&+&+&-&&+&+&+&-&&-&-&-&-\\ \\ -&+&+&+&&+&-&+&-&&+&+&-&+\\ +&+&-&+&&+&-&-&-&&-&-&+&+\\ +&-&+&+&&+&-&-&+&&-&+&-&-\\ -&-&+&-&&+&+&-&-&&-&+&+&+ \end{array}\right) [[/math]]

As for the last assertion, regarding uniqueness, this is something quite technical, requiring some clever block decomposition techniques. Alternatively, it is possible to verify this by using a computer, although programming such things is not exactly trivial.

■

At [math]N=16[/math] now, the situation becomes fairly complicated, as follows:

Theorem

The Hadamard matrices at [math]N=16[/math] are as follows:

• We have the Walsh matrix [math]W_{16}[/math].
• There are no Paley matrices.
• Besides [math]W_{16}[/math], we have [math]4[/math] more matrices, up to equivalence.

Show Proof

Once again, this is a mixture of elementary and more advanced results:

(1) This is clear.

(2) This comes from the fact that we have [math]16=15+1[/math], with [math]15[/math] not being a prime power, and from the fact that we have [math]16=2\times 7+2[/math], with [math]7\neq1(4)[/math].

(3) This is something very technical, basically requiring a computer.

■

At [math]N=20[/math] and bigger, the situation becomes quite complicated, and the study is usually done with a mix of advanced algebraic methods, and computer techniques. The overall conclusion is that the number of Hadamard matrices of size [math]N\in4\mathbb N[/math] grows with [math]N[/math], in exponential fashion. In particular, we are led in this way into:

\begin{conjecture}[Hadamard Conjecture (HC)] There is at least one Hadamard matrix

[[math]] H\in M_N(\pm1) [[/math]]

for any integer [math]N\in 4\mathbb N[/math]. \end{conjecture} This conjecture, going back to the 19th century, is one of the most beautiful statements in combinatorics, linear algebra, and mathematics in general. Quite remarkably, the numeric verification so far goes up to the number of the beast:

[[math]] \mathfrak N=666 [[/math]]

Our purpose now will be that of gathering some evidence for this conjecture. By using the Walsh construction, we have examples at each [math]N=2^n[/math]. We can add various examples coming from the Paley 1 and Paley 2 constructions, and we are led to:

Theorem

The HC is verified at least up to [math]N=88[/math], as follows:

• At [math]N=4,8,16,32,64[/math] we have Walsh matrices.
• At [math]N=12,20,24,28,44,48,60,68,72,80,84,88[/math] we have Paley [math]1[/math] matrices.
• At [math]N=36,52,76[/math] we have Paley [math]2[/math] matrices.
• At [math]N=40,56[/math] we have Paley [math]1[/math] matrices tensored with [math]W_2[/math].

However, at [math]N=92[/math] these constructions (Walsh, Paley, tensoring) don't work.

Show Proof

First of all, the numbers in (1-4) are indeed all the multiples of 4, up to 88. As for the various assertions, the proof here goes as follows:

(1) This is clear.

(2) Here the number [math]N-1[/math] takes the following values:

[[math]] q=11,19,23,27,43,47,59,67,71,79,83,87 [[/math]]

These are all prime powers, so we can apply the Paley 1 construction.

(3) Since [math]N=4(8)[/math] here, and [math]N/2-1[/math] takes the values [math]q=17,25,37[/math], all prime powers, we can indeed apply the Paley 2 construction, in these cases.

(4) At [math]N=40[/math] we have indeed [math]P_{20}^1\otimes W_2[/math], and at [math]N=56[/math] we have [math]P_{28}^1\otimes W_2[/math].

Finally, we have [math]92-1=7\times13[/math], so the Paley 1 construction does not work, and [math]92/2=46[/math], so the Paley 2 construction, or tensoring with [math]W_2[/math], does not work either.

■

At [math]N=92[/math] now, the situation is considerably more complicated, and we have:

Theorem

Assuming that [math]A,B,C,D\in M_K(\pm1)[/math] are circulant, symmetric, pairwise commute and satisfy the condition

[[math]] A^2+B^2+C^2+D^2=4K [[/math]]

the following [math]4K\times4K[/math] matrix is Hadamard, called of Williamson type:

[[math]] H=\begin{pmatrix} A&B&C&D\\ -B&A&-D&C\\ -C&D&A&-B\\ -D&-C&B&A \end{pmatrix} [[/math]]

Moreover, matrices [math]A,B,C,D[/math] as above exist at [math]K=23[/math], where [math]4K=92[/math].

Show Proof

We use the same method as for the Paley theorem, namely tensor calculus. Consider the following matrices [math]1,i,j,k\in M_4(0,1)[/math], called the quaternion units:

[[math]] 1=\begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{pmatrix} \qquad,\qquad i=\begin{pmatrix} 0&1&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{pmatrix} [[/math]]

[[math]] j=\begin{pmatrix} 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0\\ 0&1&0&0 \end{pmatrix} \qquad,\qquad k=\begin{pmatrix} 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{pmatrix} [[/math]]

These matrices describe the positions of the [math]A,B,C,D[/math] entries in the matrix [math]H[/math] from the statement, and so this matrix can be written as follows:

[[math]] H=A\otimes 1+B\otimes i+C\otimes j+D\otimes k [[/math]]

Assuming now that [math]A,B,C,D[/math] are symmetric, we have:

[[math]] \begin{eqnarray*} HH^t &=&(A\otimes 1+B\otimes i+C\otimes j+D\otimes k)\\ &&(A\otimes 1-B\otimes i-C\otimes j-D\otimes k)\\ &=&(A^2+B^2+C^2+D^2)\otimes 1-([A,B]-[C,D])\otimes i\\ &&-([A,C]-[B,D])\otimes j-([A,D]-[B,C])\otimes k \end{eqnarray*} [[/math]]

Now assume that our matrices [math]A,B,C,D[/math] pairwise commute, and satisfy as well the condition in the statement, namely [math]A^2+B^2+C^2+D^2=4K[/math]. In this case, it follows from the above formula that we have [math]HH^t=4K[/math], so we obtain indeed an Hadamard matrix.

In general, finding such matrices is a difficult task, and this is where Williamson's extra assumption that [math]A,B,C,D[/math] should be taken circulant comes from. Finally, regarding the [math]K=23[/math] construction, which produces an Hadamard matrix of order [math]N=92[/math], this comes via a computer search. See Williamson and Baumert-Golomb-Hall .

■

Things get even worse at higher values of [math]N[/math], where more and more complicated constructions are needed. The whole subject is quite technical, and, as already mentioned, human knowledge here stops so far at [math]\mathfrak N=666[/math]. See , , , , , .

1d. Cocyclic matrices

We have seen so far that the combinatorial and algebraic theory of the Hadamard matrices, while very nice at the elementary level, ultimately leads into some difficult questions. There are at least two potential exits from this, namely:

(1) Do analysis. There are many things that can be done here, starting with the Hadamard determinant bound , and we will discuss this in chapter 2, and afterwards. Whether all this can help or not in relation with the Hadamard Conjecture remains to be seen, but at least we'll have some fun, and do some interesting mathematics.

(2) Do geometry. When allowing the entries of [math]H[/math] to be complex numbers, we reach to geometric questions, and the Hadamard Conjecture problematics dissapears, because the Fourier matrix, namely [math]F_N=(w^{ij})[/math] with [math]w=e^{2\pi i/N}[/math], is an example of such matrix at any [math]N\in\mathbb N[/math]. We will discuss this later, starting from chapter 5 below.

Getting back now to algebra and combinatorics, as a conceptual finding on the subject, however, we have the recent theory of the cocyclic Hadamard matrices, that we will briefly explain now. This theory is based on the following notion:

Definition

A cocycle on a finite group [math]G[/math] is a matrix [math]H\in M_G(\pm1)[/math] satisfying:

[[math]] H_{gh}H_{gh,k}=H_{g,hk}H_{hk} [[/math]]

[[math]] H_{11}=1 [[/math]]

If the rows of [math]H[/math] are pairwise orthogonal, we say that [math]H[/math] is a cocyclic Hadamard matrix.

Here the definition of the cocycles is the usual one, with the equations coming from the fact that [math]F=\mathbb Z_2\times G[/math] must be a group, with multiplication as follows:

[[math]] (u,g)(v,h)=(H_{gh}\cdot uv,gh) [[/math]]

As a basic illustration for the above notion, the Walsh matrix [math]H=W_{2^n}[/math] is cocyclic, coming from the group [math]G=\mathbb Z_2^n[/math], with cocycle as follows:

[[math]] H_{gh}=(-1)^{ \lt g,h \gt } [[/math]]

As explained by de Launey, Flannery and Horadam in , and in other papers, many other known examples of Hadamard matrices are cocyclic, and this leads to: \begin{conjecture}[Cocyclic Hadamard Conjecture] There is at least one cocyclic Hadamard matrix [math]H\in M_N(\pm1)[/math], for any [math]N\in 4\mathbb N[/math]. \end{conjecture}

Having such a statement formulated is certainly a big advance with respect to the HC, and this is probably the main achievement of modern Hadamard matrix theory. However, in what regards a potential proof, there is no clear strategy here, at least so far. We will be back to such questions, in relation with advanced algebra, in chapters 13-16 below, with the fact that the construction [math]\mathbb Z_2^n\to W_{2^n}[/math] can be extended as to cover all the Hadamard matrices, by replacing [math]\mathbb Z_2^n[/math] with a suitable quantum permutation group. However, in what regards the potential applications to the HC, there is no clear strategy here either.

Finally, as a last algebraic topic, let us discuss the Circulant Hadamard Conjecture. Besides analysis in a large sense, as explained above, another potential way of getting away from the difficult HC questions is that of looking at various special classes of Hadamard matrices. However, in practice, this often leads to quite complicated mathematics too.

Illustrating and famous here is the situation in the circulant case. Given a vector [math]\gamma\in(\pm 1)^N[/math], one can ask whether the corresponding circulant matrix [math]H\in M_N(\pm 1)[/math], defined by [math]H_{ij}=\gamma_{j-i}[/math], is Hadamard or not. Here is a solution to the problem:

[[math]] K_4=\begin{pmatrix}-1&1&1&1\\ 1&-1&1&1\\ 1&1&-1&1\\ 1&1&1&-1\end{pmatrix} [[/math]]

More generally, any vector [math]\gamma\in(\pm 1)^4[/math] satisfying [math]\sum\gamma_i=\pm 1[/math] is a solution to the problem, with the corresponding Hadamard matrix being equivalent to [math]K_4[/math]. The following conjecture, due to Ryser , states that there are no other solutions: \begin{conjecture}[Circulant Hadamard Conjecture (CHC)] There is no circulant Hadamard matrix of size [math]N\times N[/math], for any [math]N\neq 4[/math]. \end{conjecture} The fact that such a simple-looking problem is still open might seem quite surprising. Indeed, if we denote by [math]S\subset\{1,\ldots,N\}[/math] the set of positions of the [math]-1[/math] entries of [math]\gamma[/math], the Hadamard matrix condition is simply [math]|S\cap(S+k)|=|S|-N/4[/math], for any [math]k\neq 0[/math], taken modulo [math]N[/math]. Thus, the above conjecture simply states that at [math]N\neq 4[/math], such a set [math]S[/math] cannot exist. Let us record here this latter statement, also due to Ryser :

\begin{conjecture}[Ryser Conjecture] Given an integer [math]N \gt 4[/math], there is no set [math]S\subset\{1,\ldots,N\}[/math] satisfying the condition

[[math]] |S\cap(S+k)|=|S|-N/4 [[/math]]

for any [math]k\neq 0[/math], taken modulo [math]N[/math]. \end{conjecture} There has been a lot of work on this conjecture, starting with . However, as it was the case with the HC, all this leads to complicated combinatorics, design theory, algebra and number theory, and so on, and there is no clear idea here, at least so far.

General references

Banica, Teo (2024). "Invitation to Hadamard matrices". arXiv:1910.06911 [math.CO].