guide:300e2b94e8

[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.

Getting away now from all the above arithmetic difficulties, let us discuss, following , the classification of the regular complex Hadamard matrices of small order. The definition here, which already appeared in the above, is as follows:

Definition

A complex Hadamard matrix [math]H\in M_N(\mathbb T)[/math] is called regular if the scalar products between rows decompose as sums of cycles.

We should mention that there is some terminology clash here, with the word “regular” being sometimes used in order to designate the bistochastic matrices. In this book we use the above notion of regularity, and we call bistochastic the bistochastic matrices.

Our purpose in what follows will be that of showing that the notion of regularity can lead to full classification results at [math]N\leq6[/math], and perhaps at [math]N=7[/math] too, and all this while covering most of the interesting complex Hadamard matrices that we met, so far. As a first observation, supporting this last claim, we have the following result:

Proposition

The following complex Hadamard matrices are regular:

• The matrices at [math]N\leq5[/math], namely [math]F_2,F_3,F_4^s,F_5[/math].
• The main examples at [math]N=6[/math], namely [math]F_6^{(rs)},F_6^{(^r_s)},H_6^q,T_6[/math].
• The main examples at [math]N=7[/math], namely [math]F_7,P_7^q[/math].

Show Proof

The Fourier matrices [math]F_N[/math] are all regular, with the scalar products between rows appearing as certain sums of full sums of [math]l[/math]-th roots of unity, with [math]l|N[/math]. As for the other matrices appearing in the statement, with the convention that “cycle structure” means the lengths of the cycles in the regularity property, the situation is as follows:

(1) [math]F_4^s[/math] has cycle structure [math]2+2[/math], and this because the verification of the Hadamard condition is always based on the formula [math]1+(-1)=0[/math], rotated by scalars.

(2) [math]F_6^{(rs)},F_6^{(^r_s)}[/math] have mixed cycle structure [math]2+2+2/3+3[/math], in the sense that both cases appear, [math]H_6^q[/math] has cycle structure [math]2+2+2[/math], and [math]T_6[/math] has cycle structure [math]3+3[/math].

(3) [math]P_7^q[/math] has cycle structure [math]3+2+2[/math], its Hadamard property coming from [math]1+w+w^2=0[/math], with [math]w=e^{2\pi i/3}[/math], and from [math]1+(-1)=0[/math], applied twice, rotated by scalars.

■

Let us discuss now the classification of regular matrices. We first have:

Theorem

The regular Hadamard matrices at [math]N\leq 5[/math] are

[[math]] F_2,F_3,F_4^s,F_5 [[/math]]

up to the equivalence relation for the complex Hadamard matrices.

Show Proof

This is something that we already know, coming from the classification results from chapter 5, and from Proposition 6.13 (1). However, and here comes our point, proving this result does not need in fact all this, the situation being as follows:

(1) At [math]N=2[/math] the cycle structure can be only 2, and we obtain [math]F_2[/math].

(2) At [math]N=3[/math] the cycle structure can be only 3, and we obtain [math]F_3[/math].

(3) At [math]N=4[/math] the cycle structure can be only [math]2+2[/math], and we obtain [math]F_4^s[/math].

(4) At [math]N=5[/math] some elementary combinatorics shows that the cycle structure [math]3+2[/math] is excluded. Thus we are left with the cycle structure [math]5[/math], and we obtain [math]F_5[/math].

■

Let us discuss now the classification at [math]N=6[/math]. The result here, from , states that the matrices [math]F_6^{(rs)},F_6^{(^r_s)},H_6^q,T_6[/math] are the only solutions. The proof is quite long and technical, but we will present here its main ideas. Let us start with:

Proposition

The regular Hadamard matrices at [math]N=6[/math] fall into [math]3[/math] classes:

• Cycle structure [math]3+3[/math], with [math]T_6[/math] being an example.
• Cycle structure [math]2+2+2[/math], with [math]H_6^q[/math] being an example.
• Mixed cycle structure [math]3+3/2+2+2[/math], with [math]F_6^{(rs)},F_6^{(^r_s)}[/math] being examples.

Show Proof

This is a bit of an empty statement, with the above (1,2,3) possibilities being the only ones, and with the various examples coming from Proposition 6.13 (2).

■

In order to do the classification, we must prove that the examples in (1,2,3) are the only ones. Let us start with the Tao matrix. The result here is as follows:

Proposition

The Tao matrix, namely

[[math]] T_6=\begin{pmatrix} 1&1&1&1&1&1\\ 1&1&w&w&w^2&w^2\\ 1&w&1&w^2&w^2&w\\ 1&w&w^2&1&w&w^2\\ 1&w^2&w^2&w&1&w\\ 1&w^2&w&w^2&w&1 \end{pmatrix} [[/math]]

with [math]w=e^{2\pi i/3}[/math] is the only one with cycle structure [math]3+3[/math].

Show Proof

The proof of this fact, from , is quite long and technical, the idea being that of studying first the [math]3\times 6[/math] case, then the [math]4\times6[/math] case, and finally the [math]6\times6[/math] case:

(1) Consider first a partial Hadamard matrix [math]A\in M_{3\times 6}(\mathbb T)[/math], with the scalar products between rows assumed to be all of type [math]3+3[/math]. By doing some elementary combinatorics, explained in , we can see that, modulo equivalence, either all entries of [math]A[/math] belong to [math]\mathbb Z_3=\{1,w,w^2\}[/math], or [math]A[/math] has the following special form, for certain parameters [math]r,s\in\mathbb T[/math]:

[[math]] A=\begin{pmatrix} 1&1&1&1&1&1\\ 1&w&w^2&r&wr&w^2r\\ 1&w^2&w&s&w^2s&ws \end{pmatrix} [[/math]]

(2) With this result in hand, we can now investigate the [math]4\times6[/math] case. Assume indeed that we have a partial Hadamard matrix [math]B\in M_{4\times 6}(\mathbb T)[/math], with the scalar products between rows assumed to be all of type [math]3+3[/math]. By looking at the 4 submatrices [math]A^{(1)},A^{(2)},A^{(3)},A^{(4)}[/math] obtained from [math]B[/math] by deleting one row, and applying the above [math]3\times 6[/math] result, we see that all the possible parameters dissapear. Thus, our matrix must be of the following type:

[[math]] B\in M_{4\times 6}(\mathbb Z_3) [[/math]]

(3) With this, we can now go for the general case. Indeed, an Hadamard matrix [math]M\in M_6(\mathbb T)[/math] having cycle structure [math]3+3[/math] must be of the form [math]M\in M_6(\mathbb Z_3)[/math]. But the study of such matrices is elementary, with [math]T_6[/math] as the only solution. See .

■

Regarding now the Haagerup matrix, the result is similar, as follows:

Proposition

The Haagerup matrix, namely

[[math]] H_6^q=\begin{pmatrix} 1&1&1&1&1&1\\ 1&-1&i&i&-i&-i\\ 1&i&-1&-i&q&-q\\ 1&i&-i&-1&-q&q\\ 1&-i&\bar{q}&-\bar{q}&i&-1\\ 1&-i&-\bar{q}&\bar{q}&-1&i \end{pmatrix} [[/math]]

with [math]q\in\mathbb T[/math] is the only one with cycle structure [math]2+2+2[/math].

Show Proof

The proof here, from , uses the same idea as in the proof of Proposition 6.16, namely a detailed combinatorial study, by increasing the number of rows. First of all, the study of the [math]3\times 6[/math] partial Hadamard matrices with cycle structure [math]2+2+2[/math] leads, up to equivalence, to the following 4 solutions, with [math]q\in\mathbb T[/math] being a parameter:

[[math]] A_1=\begin{pmatrix} 1&1&1&1&1&1\\ 1&-i&1&i&-1&-1\\ 1&-1&i&-i&q&-q \end{pmatrix} [[/math]]

[[math]] A_2=\begin{pmatrix} 1&1&1&1&1&1\\ 1&1&-1&i&-1&-i\\ 1&-1&q&-q&iq&-iq \end{pmatrix} [[/math]]

[[math]] A_3=\begin{pmatrix} 1&1&1&1&1&1\\ 1&-1&i&-i&q&-q\\ 1&-i&i&-1&-q&q \end{pmatrix} [[/math]]

[[math]] A_4=\begin{pmatrix} 1&1&1&1&1&1\\ 1&-i&-1&i&q&-q\\ 1&-1&-q&-iq&iq&q \end{pmatrix} [[/math]]

With this result in hand, we can go directly for the [math]6\times6[/math] case. Indeed, a careful examination of the [math]3\times6[/math] submatrices, and of the way that different parameters can overlap vertically, shows that our matrix must have a [math]3\times 3[/math] block decomposition as follows:

[[math]] M=\begin{pmatrix} A&B&C\\ D&xE&yF\\ G&zH&tI \end{pmatrix} [[/math]]

Here [math]A,\ldots,I[/math] are [math]2\times 2[/math] matrices over [math]\{\pm 1,\pm i\}[/math], and [math]x,y,z,t[/math] are in [math]\{1,q\}[/math]. A more careful examination shows that the solution must be of the following form:

[[math]] M=\begin{pmatrix} A&B&C\\ D&E&qF\\ G&qH&qI \end{pmatrix} [[/math]]

More precisely, the matrix must be as follows:

[[math]] M=\begin{pmatrix} 1&1&1&1&1&1\\ 1&1&-i&i&-1&-1\\ 1&i&-1&-i&-q&q\\ 1&-i&i&-1&-iq&iq\\ 1&-1&q&-iq&iq&-q\\ 1&-1&-q&iq&q&-iq \end{pmatrix} [[/math]]

But this matrix is equivalent to [math]H_6^q[/math], and we are done. See .

■

Regarding now the mixed case, where both [math]2+2+2[/math] and [math]3+3[/math] situations can appear, this is a bit more complicated. We can associate to any mixed Hadamard matrix [math]M\in M_6(\mathbb C)[/math] its “row graph”, having the 6 rows as vertices, and with each edge being called “binary” or “ternary”, depending on whether the corresponding scalar product is of type [math]2+2+2[/math] or [math]3+3[/math]. With this convention, we have the following result:

Proposition

The row graph of a mixed matrix [math]M\in M_6(\mathbb C)[/math] can be:

• Either the bipartite graph having [math]3[/math] binary edges.
• Or the bipartite graph having [math]2[/math] ternary triangles.

Show Proof

Let [math]X[/math] be the row graph in the statement. By doing some combinatorics, of rather elementary type, we are led to the following conclusions about [math]X[/math]:

-- [math]X[/math] has no binary triangle.

-- [math]X[/math] has no ternary square.

-- [math]X[/math] has at least one ternary triangle.

With these results in hand, we see that there are only two types of squares in our graph [math]X[/math], namely those having 1 binary edge and 5 ternary edges, and those consisting of a ternary triangle, connected to the 4-th point with 3 binary edges. By looking at pentagons, then hexagons that can be built with these squares, we see that the above two types of squares cannot appear at the same time, at that at the level of hexagons, we have the two solutions in the statement. For details regarding all this, we refer to .

■

We can now complete our classification results at [math]N=6[/math] with:

Proposition

The deformed Fourier matrices, namely

[[math]] F_6^{(rs)}=\begin{pmatrix} 1&1&1&&1&1&1\\ 1&w&w^2&&1&w&w^2\\ 1&w^2&w&&1&w^2&w\\ \\ 1&r&s&&-1&-r&-s\\ 1&wr&w^2s&&-1&-wr&-w^2s\\ 1&w^2r&ws&&-1&-w^2r&-ws \end{pmatrix} [[/math]]

[[math]] F_6^{(^r_s)} =\begin{pmatrix} 1&1&&1&1&&1&1\\ 1&-1&&1&-1&&1&-1\\ \\ 1&r&&w&wr&&w^2&w^2r\\ 1&-r&&w&-wr&&w^2&-w^2r\\ \\ 1&s&&w^2&w^2s&&w&ws\\ 1&-s&&w^2&-w^2s&&w&-ws \end{pmatrix} [[/math]]

with [math]r,s\in\mathbb T[/math] are the only ones with mixed cycle structure.

Show Proof

According to Proposition 6.18, we have two cases:

(1) Assume first that the row graph is the bipartite one with 3 binary edges. By permuting the rows, the upper [math]4\times6[/math] submatrix of our matrix must be as follows:

[[math]] B=\begin{pmatrix} 1&1&1&1&1&1\\ 1&w&w^2&r&wr&w^2r\\ 1&w^2&w&s&w^2s&ws\\ 1&1&1&t&t&t \end{pmatrix} [[/math]]

Now since the scalar product between the first and the fourth row is binary, we must have [math]t=-1[/math], so the solution is:

[[math]] B=\begin{pmatrix} 1&1&1&1&1&1\\ 1&w&w^2&r&wr&w^2r\\ 1&w^2&w&s&w^2s&ws\\ 1&1&1&-1&-1&-1 \end{pmatrix} [[/math]]

We can use the same argument for finding the fifth and sixth row, by arranging the matrix formed by the first three rows such as the second, respectively third row consist only of 1's. This will make appear some parameters of the form [math]w,w^2,r,s[/math] in the extra row, and we obtain in this way a matrix which is equivalent to [math]F_6^{(rs)}[/math]. See .

(2) Assume now that the row graph is the bipartite one with 2 ternary triangles. By permuting the rows, the upper [math]4\times6[/math] submatrix of our matrix must be as follows:

[[math]] B=\begin{pmatrix} 1&1&1&1&1&1\\ 1&1&w&w&w^2&w^2\\ 1&1&w^2&w^2&w&w\\ 1&-1&r&-r&s&-s \end{pmatrix} [[/math]]

We can use the same argument for finding the fifth and sixth row, and we conclude that the matrix is of the following type:

[[math]] M=\begin{pmatrix} 1&1&1&1&1&1\\ 1&1&w&w&w^2&w^2\\ 1&1&w^2&w^2&w&w\\ 1&-1&r&-r&s&-s\\ 1&-1&a&-a&b&-b\\ 1&-1&c&-c&d&-d \end{pmatrix} [[/math]]

Now since the last three rows must form a ternary triangle, we conclude that the matrix must be of the following form:

[[math]] M=\begin{pmatrix} 1&1&1&1&1&1\\ 1&1&w&w&w^2&w^2\\ 1&1&w^2&w^2&w&w\\ 1&-1&r&-r&s&-s\\ 1&-1&wr&-wr&w^2s&-w^2s\\ 1&-1&w^2r&-w^2r&ws&-ws \end{pmatrix} [[/math]]

But this matrix is equivalent to [math]F_6^{(^r_s)}[/math], and we are done. See .

■

All this was quite technical, but good news, we are done with our study. Indeed, summing up all the above, we have proved the following theorem, from :

Theorem

The regular complex Hadamard matrices at [math]N=6[/math] are:

• The deformations [math]F_6^{(rs)},F_6^{(^r_s)}[/math] of the Fourier matrix [math]F_6[/math].
• The Haagerup matrix [math]H_6^q[/math].
• The Tao matrix [math]T_6[/math].

Show Proof

This follows indeed from the trichotomy from Proposition 6.15, and from the results in Proposition 6.16, Proposition 6.17 and Proposition 6.19. See .

■

All this is quite nice, bringing some fresh air into the classification question for the complex Hadamard matrices at [math]N=6[/math], which is stuck, as explained in chapter 5. As a continuation of this, our belief is that the [math]N=7[/math] classification is doable as well. Here we have 3 possible cycle structures, namely [math]3+2+2[/math], [math]5+2[/math], [math]7[/math], and our first job is that of understanding what cycle structures are indeed possible, in practice.

In order to deal with this latter question, we use the same idea as at [math]N=6[/math], namely looking at [math]3\times N[/math] submatrices. Let us start with the following definition:

Definition

Given numbers [math]p_i,q_i,r_i[/math] with [math]\sum p_i=\sum q_i=\sum r_i[/math], we write

[[math]] (p_1+\ldots+p_k)\perp_{(r_1+\ldots+r_s)}(q_1+\ldots+q_l) [[/math]]

if there exist sums of cycles [math]P,Q[/math] having cycle structure [math]\sum p_i,\sum q_i[/math], such that the scalar product [math]R= \lt P,Q \gt [/math] vanishes, and has [math]\sum r_i[/math] as cycle structure. Otherwise, we write:

[[math]] (p_1+\ldots+p_k)\not\perp_{(r_1+\ldots+r_s)}(q_1+\ldots+q_l) [[/math]]

If there are no numbers [math]r_i[/math] such that [math]\sum p_i\perp_{\sum r_i}\sum q_i[/math] holds, we write [math]\sum p_i\not\perp\sum q_i[/math].

In other words, we write [math]\sum p_i\perp_{\sum r_i}\sum q_i[/math] if there exist complex numbers [math]a_k,b_k,c_k\in\mathbb T[/math] such that [math]\sum a_k,\sum b_k,\sum c_k[/math] have cycle structure [math]\sum p_i,\sum q_i,\sum r_i[/math] respectively, and such that [math]a_k\bar{b}_k=c_k[/math] for any [math]k[/math], and we use as well the related notations [math]\sum p_i\not\perp_{\sum r_i}\sum q_i[/math] and [math]\sum p_i\not\perp\sum q_i[/math], taken in an obvious sense. Now with these notions in hand, we have:

Proposition

Assume that [math]p,q\geq 3[/math] are primes.

• If [math]p=q+2[/math] we have [math]p\not\perp(q+2)[/math].
• If [math]p=q+2[/math] then [math](p+2)\not\perp_{(q+2+2)}(p+2)[/math].
• We have [math](p+2)\not\perp_{(p+2)}(p+2)[/math].
• If [math]p=q+4[/math] then [math](q+2+2)\not\perp_p(q+2+2)[/math].
• If [math]p=q+2[/math] then [math](q+2+2)\not\perp_{(p+2)}(q+2+2)[/math].

Show Proof

All this follows from some basic number theory, the idea being as follows:

(1) By multiplying by scalars and permuting columns, we can assume that the [math]2\times p[/math] matrix formed by our sums is as follows, with [math]w=e^{2\pi i/q}[/math] and [math]\xi=e^{2\pi i/p}[/math]:

[[math]] \begin{pmatrix} 1&w&\ldots&w^{q-1}&a&-a\\ 1&\xi^{r_1}&\ldots&\xi^{r_{q-1}}&\xi^s&\xi^t \end{pmatrix} [[/math]]

Now since the scalar product between rows vanishes, we obtain:

[[math]] a=\frac{1+w\xi^{-r_1}+\ldots+w^{q-1}\xi^{-r_{q-1}}}{\xi^{-t}-\xi^{-s}} [[/math]]

On the other hand we have [math]|a|=1[/math], and the equation [math]a=\bar{a}^{-1}[/math] reads:

[[math]] \frac{1+w\xi^{-r_1}+\ldots+w^{q-1}\xi^{-r_{q-1}}}{\xi^{-t}-\xi^{-s}} =\frac{\xi^t-\xi^s}{1+w^{-1}\xi^{r_1}+\ldots+w^{-q+1}\xi^{r_{q-1}}} [[/math]]

Now by developing, we obtain a formula of type [math](q-2)+S=0[/math], where [math]S[/math] is a certain sum of [math]q^2-q+2[/math] roots of unity of order [math]pq[/math]. Now since [math]pq[/math] has [math]k=2[/math] prime factors, Theorem 6.9 (2) applies, and shows that [math](q-2)+S[/math] must be a sum of cycles. But since [math]q\geq 3[/math], some of the terms of [math]S[/math] must be roots of unity of order [math]p[/math], or of order [math]q[/math], and this shows that [math]\xi[/math] is a power of [math]w[/math] or vice versa, which is a contradiction, as desired.

(2-5) Here the study goes along the same lines, with the needed technical ingredient being the well-known Galois theory fact that a number [math]\lambda\in\mathbb Z[w][/math], where [math]w=e^{2\pi i/n}[/math], satisfies [math]|\lambda|=1[/math] precisely when it is of the form [math]\lambda=\pm w^k[/math], for some [math]k\in\mathbb N[/math].

■

Getting back now to our [math]N=7[/math] questions, we have the following result:

Proposition

We have the following obstructions:

• [math]7\not\perp(5+2)[/math].
• [math](5+2)\not\perp(5+2)[/math].
• [math]7\not\perp(3+2+2)[/math].
• [math](5+2)\not\perp(3+2+2)[/math].

Show Proof

This follows from Proposition 6.22, as follows:

(1) This follows from Proposition 6.22 (1), at [math]p=7[/math].

(2) We have indeed [math](5+2)\not\perp_7(5+2)[/math] from Proposition 6.22 (1), [math](5+2)\not\perp_{(5+2)}(5+2)[/math] from Proposition 6.22 (2), and [math](5+2)\not\perp_{(3+2+2)}(5+2)[/math] from Proposition 6.22 (3).

(3) First, [math]7\not\perp_7(3+2+2)[/math] is clear. Also, we have [math]7\not\perp_{(5+2)}(3+2+2)[/math] from Proposition 6.22 (1) and [math]7\not\perp_{(3+2+2)}(3+2+2)[/math] from Proposition 6.22 (4), and this gives the result.

(4) We have [math](5+2)\not\perp_7(3+2+2)[/math] from Proposition 6.22, [math](5+2)\not\perp_{(5+2)}(3+2+2)[/math] from Proposition 6.22 (3), and [math](5+2)\not\perp_{(3+2+2)}(3+2+2)[/math] from Proposition 6.22 (5).

■

In the context of the regular complex Hadamard matrices [math]H\in M_7(\mathbb T)[/math], the above result shows that the cycle structure [math]5+2[/math] is excluded, and that the cases [math]3+2+2[/math] and [math]7[/math] cannot interact. Thus we have a dichotomy, and our conjecture is as follows: \begin{conjecture} The regular complex Hadamard matrices at [math]N=7[/math] are:

• The Fourier matrix [math]F_7[/math].
• The Petrescu matrix [math]P_7^q[/math].

\end{conjecture}

Regarding (1), one can show indeed that [math]F_7[/math] is the only matrix having cycle structure 7, with this being related to more general results of Hiranandani-Schlenker . As for (2), the problem is that of proving that [math]P_7^q[/math] is the only matrix having cycle structure [math]3+2+2[/math]. The computations here are unfortunately far more involved than those at [math]N=6[/math], briefly presented above, and finishing the classification work here is not an easy question.

Besides the classification questions, there are as well a number of theoretical questions in relation with the notion of regularity, that we believe to be very interesting. We have for instance the following conjecture, going back to :

\begin{conjecture}[Regularity Conjecture] The following hold:

• Any Butson matrix [math]H\in M_N(\mathbb C)[/math] is regular.
• Any regular matrix [math]H\in M_N(\mathbb C)[/math] is an affine deformation of a Butson matrix.

\end{conjecture} In order to comment on the first conjecture, let us recall from Theorem 6.9 that in the case where the level of the Butson matrix has at most 2 prime factors, [math]l=p^a[/math] or [math]l=p^aq^b[/math], any vanishing sum of roots of unity, and in particular the various scalar products between rows, decompose as a sum of cycles. Thus, in this case, the conjecture holds.

The problem appears when the level [math]l[/math] has at least 3 prime factors, for instance when [math]l=30[/math]. Here we have “exotic” vanishing sums of roots of unity, such as the following one, with [math]w=e^{2\pi i/30}[/math], discussed after Definition 6.8:

[[math]] w^5+w^6+w^{12}+w^{18}+w^{24}+w^{25}=0 [[/math]]

To be more precise, our above conjecture (1) says that such an exotic vanishing sum of roots of unity cannot be used in order to construct a complex Hadamard matrix, as part of the arithmetics leading to the vanishing of the various scalar products between rows. This looks like a quite difficult question, coming however with substantial computer evidence. We have no idea on how to approach it, abstractly. See .

As for the second conjecture, (2) above, this simply comes from the known examples of regular Hadamard matrices, which all appear from certain Butson matrices, by inserting parameters, in an affine way. We will further discuss the notion of affine deformation, with some general results on the subject, in chapters 7-8 below.

General references

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